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.

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

Solution 2

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.

Solution 3

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.

Solution 4

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

View more solutions

Comments

[user1897830]

Unfortunately that doesn't provide the correct answer either.

[V. Semeria]

Please give an example where it fails

[user1897830]

That's great. However I would like to know how to code it myself. Just as a learning exercise.

[Benjamin Hodgson]

See the linked Documentation page for an example. (Also, I added a section to the answer.)

[V. Semeria]

Isn't foldl (\l x -> l ++ [x]) [] the identity on lists ? If so it preserves the list structure :)

[Benjamin Hodgson]

@V.Semeria Yes, but trees are not lists. They contain extra information, which foldl/foldr discard. Foldable's view of the world reduces everything to a list.

[V. Semeria]

Indeed. To me a foldable object is just something you can convert to a list. Then you use the usual foldr on lists.

[V. Semeria]

Rather, foldr f init t == foldr f init (toList t). So a fold cannot use more information about t than is contained in its list collapse.

[Kaylo]

Assume I created a Trinary (Ternary?) tree which was defined as data TriTree a = EmptyNode | TriNode a (TriTree a) (TriTree a) (TriTree a) deriving (Show) How would I create a pre-order fold for a tree like this?

[chi]

@Lombe That's not a comment, that's a question. You probably should post it as such, and clarify why you were not able to adapt the above code to your tree type.

[Kaylo]

@chi I was able to figure it out. However,I have a different haskell related question. If you have the time, I was wondering if you'd be able to help me figure it out. I just posted it here stackoverflow.com/questions/52638198/…

[user2023370]

Switching left and right on the rhs of foldTreel corresponds to foldTreer. Switching left and right on the rhs of foldTreer corresponds to foldTreel. foldTreec stays the same.