CODEWITHSUNDEEP
haskell
user975343
user975343

Reputation:

Haskell Trees Mapping

I've been trying to write a simple mapping function using Haskell, and I came into the following problem:

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving(Show)
let g (Leaf l) = Leaf(l+1)
let map g (Leaf l) = g(l)
let lf = (Leaf 2)

For g(lf) the output is Leaf 3 as excepted, but for map g lf i'm getting the following error :

    Couldn't match type `Integer' with `Tree a0'
Expected type: Tree (Tree a0)
  Actual type: Tree Integer
In the second argument of `map', namely `lf'
In the expression: map g lf
In an equation for `it': it = map g lf

I don't know why do I get this error and I'd be grateful if anyone could point me to the solution.

Upvotes: 0

Views: 113

Answers (1)

J. Abrahamson
J. Abrahamson

Reputation: 74384

This is exactly the type system showing you the logic of your program doesn't work out. We can track the details by adding a lot of extra type information in by hand to see if our intuition matches the details of the checker.

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show)

g :: Num a => Tree a -> Tree a
g (Leaf l) = Leaf (l + 1)

map :: (a -> b) -> Tree a -> b
map g (Leaf l) = g(l)

lf :: Num a => Tree a
lf = (Leaf 2)

Now we look at the failing expression

(map :: (a -> b) -> Tree a -> b)
  (g :: Num c => Tree c -> Tree c)
  (lf :: Num d => Tree d)

We'll notice that (a -> b) has to match with (Num c => Tree c -> Tree c) giving us that a is Tree c and so is b.

(map g :: Tree (Tree c) -> Tree c)
  (lf :: Num d => Tree d)

And now we notice that d must match with Tree c giving us

map g lf :: Num (Tree c) => Tree (Tree c) -> Tree c

Now we know we're sunk now because Trees aren't numbers, but the error you got is slightly different. It's saying that Tree c isn't Integer.

This occurs because Haskell, when you don't provide type signatures, tries to be helpful and guess the concrete types you might be dealing with. When it does this, it sometimes picks less polymorphic ones than strictly possible. In this case, it decided lf :: Tree Integer instead of lf :: Num d => Tree d as the former is more concrete.

Upvotes: 1

Related Questions