Mapping over a Tree

Question

I am new to Haskell and for practice I have been implementing a bunch of functions (map, length, etc) using foldr and foldl. Now I want to move onto trees!

My tree data structure:

data Tree a = Node a [Tree a] deriving (Show) 

I have written a Haskell function to fold over trees:

treeFold :: (b->a->b) -> b -> Tree a -> b
treeFold f s (Node a []) = f s a
treeFold f s (Node a xs) = foldl f (f s a) (dFSList xs)

where dFSList is a list of all the nodes in the tree. So doing something like:

treeFold (+) 0 (Node 1 [Node 2 [], Node 3 []])

returns 6. Cool.

Now I want to write a Haskell function to map over trees but I want to use my treeFold function to do it. Here is what I have so far:

treeMap f (Node a []) = (Node (f a) [])
treeMap f (Node a (x:xs)) = (Node (f a) (a list involving foldTree somehow??))

How do I finish my treeMap function? I want to be able to do

treeMap (+1) (Node 1 [Node 2 [], Node 3 []])

and it should return

(Node 2 [Node 3 [], Node 4 []])

Answer 1

The way to take apart trees generally is with a different variety of fold (often called a catamorphism for some category-theory reason I don't know). You have data Tree a = Node a [Tree a], so to take that apart, you make

cat :: (a -> [b] -> b) -> Tree a -> b
cat f (Node root children) = f root (map (cat f) children)

Hokay? So now (using the standard Functor class instead of the specialized treeMap),

instance Functor Tree where
  fmap f = cat (Node . f)

You can also write linear folds like this. Your treeFold confuses me, but you can write, for example,

instance Foldable Tree where
  foldMap f = cat go where
    go root children = f root `mappend` fold children

Even stronger,

instance Traversable Tree where
  traverse f = cat go where
    go root children = Node <$> f root <*> sequenceA children