Fold Tree Function

Question

I'm trying to write a fold function for a tree:

data BinaryTree a = Leaf
                  | Node (BinaryTree a) a (BinaryTree a)
                  deriving (Eq, Ord, Show)

foldTree :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTree _ base Leaf = base
foldTree fn base (Node left a right) = fn a (foldTree fn acc right)
         where acc = foldTree fn base left

This code nearly works. However not always. For example it won't reconstruct the tree exactly the same as the original.

Answer 1

GHC is good at folding things. The very structure of your type contains enough information for your desired in-order traversal strategy to be obvious to the machine. To invoke the magic spell, utter the words "deriving Foldable!" and GHC will write your function for you.

{-# LANGUAGE DeriveFoldable #-}
data BinaryTree a = Leaf
                  | Node (BinaryTree a) a (BinaryTree a)
                  deriving Foldable

Now we have

foldTree = foldr

An interesting corollary here is that you can vary the traversal order by varying the shape of the type.

---

While we're here, a note on your requirements. You want to implement a function, using foldr, which takes a tree apart and puts it back together exactly the same, equivalent to id. This is not possible. foldr provides sequential access to the elements of the Foldable structure, erasing information like the precise position of the element within the tree. At best, you can build a list-shaped tree, with elements appearing along the right spine:

toListShapedTree = foldr (Node Leaf) Leaf

What you want is a catamorphism:

cata :: (b -> a -> b -> b) -> b -> BinaryTree a -> b
cata node leaf Leaf = leaf
cata node leaf (Node l x r) = node (cata node leaf l) x (cata node leaf r)

Note the extra parameter to the node argument! This specification gives the folding function access to the arguments of the Node constructor. Unlike Foldable, the type of a structure's catamorphism is specific to that structure. We don't lose information by viewing everything as a list. Now you can write:

cataId = cata Node Leaf

If you're dead set on using foldr for this, one strategy could be to take the positional information with you. First label each element with its position, then in the fold use that data to reconstruct the tree. Seems like hard work to me.