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

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).