Haskell Map for Trees

Question

My tree is defined by

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

I also declare a testing tree.

myTree = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)

What I want to do is create a function maptree f which will act on Leaf. To be more specifically, f x = x +1,

then maptree f myTree will return

Node (Node (Leaf 2) (Leaf 3)) (Leaf 4)

My solution is

maptree f (Leaf a)= Leaf (f a)
maptree f (Node xl xr ) = Node (maptree xl) (maptree xr)

but it will return the following error

Couldn't match expected type `Tree a'
       against inferred type `Tree t -> Tree t'
Probable cause: `maptree' is applied to too few arguments
In the first argument of `Node', namely `(maptree xl)'
In the expression: Node (maptree xl) (maptree xr)

Failed, modules loaded: none.

However, if I do

maptree (Leaf a)= Leaf ( a + 1)
maptree (Node xl xr ) = Node (maptree xl) (maptree xr)

it does work out.

I can not see the difference between the first function and the second one. How do I get error? Thanks.

Should be maptree f (Node xl xr ) = Node (maptree f xl) (maptree f xr) instead of maptree f (Node xl xr ) = Node (maptree xl) (maptree xr) — DB Tsai, Oct 02 '11 at 05:34

score 12 · Answer 1 · answered Oct 02 '11 at 05:36

You are missing the function on the recursive maptree calls:

maptree f (Leaf a)= Leaf (f a) 
maptree f (Node xl xr ) = Node (maptree xl) (maptree xr)

should be

maptree f (Leaf a)= Leaf (f a) 
maptree f (Node xl xr ) = Node (maptree f xl) (maptree f xr)

score 10 · Answer 2 · answered Oct 02 '11 at 11:51

Note that this is the obvious fmap of a Functor instance for your Tree type. You can therefore use the DeriveFunctor extension to have GHC generate it for you.

{-# LANGUAGE DeriveFunctor #-}
data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving (Functor, Show)

Let's try it.

*Main> fmap (+1) (Node (Node (Leaf 1) (Leaf 2)) (Leaf 3))
Node (Node (Leaf 2) (Leaf 3)) (Leaf 4)

score 5 · Answer 3 · answered Oct 02 '11 at 05:39

The error message basically tells you what's wrong: you are not passing maptree enough arguments. The definition maptree f (Node xl xr) says that maptree takes two arguments, a function and a tree. But when you call it like maptree xl, you're only giving it one argument (a tree).

In your second version, you've defined maptree to only take one argument (a tree), which is why it doesn't produce that error.

You can fix your problem by, for example, calling maptree f xl instead of maptree xl.

score 5 · Accepted Answer · answered Oct 03 '11 at 08:12

One dumb way to not forget to pass along the function as you recurse deeper (for this sort of higher-order function) is to use a helper:

maptree f (Leaf a)     = Leaf (f a)
maptree f (Node xl xr) = Node (go xl) (go xr)
    where go = maptree f

Or, alternatively (and perhaps more commonly):

maptree f tree = go tree                      -- or eta reduce:   maptree f = go
    where go (Leaf a)     = Leaf (f a)
          go (Node xl xr) = Node (go xl) (go xr)

In the first example, I use go sort of as a macro for maptree f. In the second example, I take advantage of the fact that maptree's input f is in scope inside the go function because go is declared in a where clause of maptree.

Haskell Map for Trees

4 Answers4

Linked