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

I think you are searching foldl one;

foldl :: (b -> a -> b) -> b -> Tree a -> b
foldl _ e Leaf = e
foldl f e (Node left a right) = foldl f (f (foldl f e left) a) right

This will work for you

Also if you need foldr ;

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

Answer 2

I came here after struggling with an exercise in Allen & Moronuki's Haskell Programming from first principles. This question sounds like the same exercise, so, for what it's worth, from one beginner to another, here's what I came up with.

I see three ways to "fold" (or catamorph) a binary tree. When folding a sequence, there are two ways to do it: fold left and fold right. One way is to start by applying the given function to (1) the head of the list and (2) the return value of the recursive call applied to the tail of the list. That's a fold right.

The other way to do a sequential fold is to start by recursively calling fold on (1) the return value of the given function applied to the head of the list and (2) the tail of the list. That's a fold left.

But in a binary tree each value can have two "subsequent" values, rather than one as in a list. So there must be two recursive calls to the fold. The call to the passed function thus can either be outside the two recursive calls, inside the two, or else between them. If I call those each left, right and center folds, I get these:

-- Fold Right for BinaryTree

foldTreer :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTreer f z Leaf = z
foldTreer f z (Node left a right) =
    f a (foldTreer f (foldTreer f z left) right)

-- Fold Left for Binary Tree

foldTreel :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTreel f z Leaf = z
foldTreel f z (Node left a right) =
    foldTreel f (foldTreel f (f a z) left) right

-- Fold Center for Binary Tree

foldTreec :: (a -> b -> b) -> b -> BinaryTree a -> b
foldTreec f z Leaf = z
foldTreec f z (Node left a right) =
    foldTreec f (f a (foldTreec f z left)) right

The first time I ever looked at Haskell was a couple weeks ago, so I could be totally wrong about everything, but that's the way it seems to me.

Answer 3

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.

Answer 4

I think you are looking for this kind of fold:

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

This is, roughly, what is being generated by the automatic deriving Foldable.

The above is a sequential fold, which first folds over the left part, then over the middle element, then over the right.

An equivalent but less efficient variant is to convert the tree to a list with an in-visit and then apply a foldr fn base over the result. One can "spread" the foldr over all the list generation, recovering the code above.

Answer 5

Thanks for the answers. I think I will just leave it as is for these reasons:

1. The type signature is given in the question so I presume that's what they want.
2. The question mentions "any traversal order is fine".
3. It works, just not in an order fashion eg. foldTree (:) [] tree will create a list of nodes but not in order. However foldTree (+) 0 tree creates a total where order is irrelevant.

Answer 6

I think you need to combine the middle point before going to the right subtree :

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