Haskell Binary Tree Function (map)

Question

How can i define a Haskell function which will apply a function to every value in a binary tree? So i know that it is similar to the map function - and that its type would be:

mapT :: (a -> b) -> Tree a -> Tree b

but thats about it...

Answer 1

I'll pretend this is homework and not give away all of the answer. If I'm mistaken, my apologies.

Probably your Tree type looks something like this:

data Tree a = TreeNode a (Tree a) (Tree a) | EmptyNode

There are two cases here, and you will need to write a mapT implementation for each of them:

• An internal node, TreeNode, which carries a value of type a and has a left and a right child. What needs to be done in this case?
• A terminal node, EmptyNode. What needs to be done in this case?

Answer 2

Interesting question if the input and output are supposed to be sorted binary trees. If you just naively traverse the tree and apply the function, the output tree may no longer be sorted. For example, consider if the function is non-linear, like

f(x) = x * x - 3 * x + 2

If the input has { 1, 2, 3, 4 } then the output will have { 2, 0, 0, 2 }. Should the output tree contain only 0 and 2?

If so, you may need to iteratively build up the output tree as you strip down and process the input tree.

Answer 3

The basic format of the map function applies to both. Let's look at the definition of the map function for lists:

map f (x:xs) = f x : map f xs
map _ []     = []

We can generalize this like so:

1. You take the first value in the data structure
2. Apply the function to it
3. Recursively call your map function with the remainder of the data structure
4. Pass both the modified value and the recursive call into the constructor for your type.
5. When you reach the end, stop recursing

All you really need is to look at your constructor and the map function should fall into place.

Answer 4

You can declare an instance of class Functor. This is a standard class for data types which allow a function to be mapped over. Please note how similar the type of fmap is to your mapT's type:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Let's assume your tree is defined as

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

Then you can declare an instance of Functor this way:

instance Functor Tree where
  fmap f (Node l r) = Node (fmap f l) (fmap f r)
  fmap f (Leaf x) = Leaf (f x)

This is how you can use it:

main = do
  let t = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
  let f = show . (2^)
  putStrLn $ "Old Tree: " ++ (show t)
  putStrLn $ "New Tree: " ++ (show . fmap f $ t)

Output:

Old Tree: Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)
New Tree: Node (Node (Leaf "2") (Leaf "4")) (Leaf "8")

You can also define for convenience:

mapT = fmap

Surely, you can do it without type classes, but it makes the code more readable for the others if you use standard functions (everyone knows the usual behaviour of fmap).