Variations of folds on Haskell Trees

Question

Given a tree defined to be:

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

I want to use the function:

foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree _ b Leaf         = b
foldTree f b (Node lt x rt) = f (foldTree f b lt) x (foldTree f b rt)

To be able to create equivalents of the normal foldr and foldl as:

foldTreeR :: (a -> b -> b) -> b -> Tree a -> b
foldTreeL :: (b -> a -> b) -> b -> Tree a -> b

I thought these would be fairly straightforward since their definitions mimic those of foldr and foldl pretty much exactly. I assumed that all I would have to do would be plug in the values analogously in a similar manner so I would write an anonymous function, an accumulator with the base state of my tree and the tree that needs to be processed. The lambda function would have to vary based on the type of fold being done.

Here is what I came up with:

foldTreeR :: (a -> b -> b) -> b -> Tree a -> b
foldTreeR f acc t =  foldTree (\x acc -> f x acc) acc t

I get the error:

Couldn't match type ‘a’ with ‘a -> b’ 
      ‘a’ is a rigid type variable bound by
        the type signature for:
          foldTreeR :: forall a b. (a -> b -> b) -> b -> Tree a -> b
        at Folds.hs:294:14
      Expected type: Tree (a -> b)
        Actual type: Tree a

I am not really sure how I should pass in the original tree in this case.

It seems the left fold will just be a variation of the same with the values within the lambda function re-ordered as well as evaluated differently.

Could someone help me understand how a solution can be reached here?

Answer 1

We can recover the linear, accumulator-passing folds from the data type-following tree-shaped folds by folding into endofunctions, like this:

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

-- foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b

foldTreeR :: (a -> r -> r) -> r -> Tree a -> r
foldTreeR cons z t = foldTree g id t z           -- b ~ r -> r
  where
  g lt a rt = lt . cons a . rt 

And the left fold:

foldTreeL :: (acc -> a -> acc) -> acc -> Tree a -> acc
foldTreeL conj z t = foldTree g id t z           -- b ~ acc -> acc
  where
  g lt a rt = rt . flip conj a . lt

---

More detailed explanations:

Both cons a and flip conj a have type r -> r (or acc -> acc, which is the same). This is the type of functions with the types of argument and result being the same.

Such functions are known as endofunctions, endo indicative of the sameness of their domain and codomain (the types on the right and left side of the arrow). As such, they compose easily: can participate in (.) operation, i.e. function composition, with the result of composition having the same type as the types of operands:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)

-- and for endofunctions,
-- ((f :: r -> r) . (g :: r -> r)) :: r -> r

For a tree with an in-order traversal of [a,b,c,...,n], the right fold turns that tree into a composition

(cons a . cons b . cons c . ..... . cons n) z

-- which is the same as
-- cons a (cons b (cons c ... (cons n z) ... ))

and the left fold turns it into

(conj' n . ..... . conj' c . conj' b . conj' a) z

where

conj' a acc = flip conj a acc = conj acc a     -- by definition of `flip`

-- so the above composition chain is the same as
-- conj (... (conj (conj (conj z a) b) c) ...) n

with some ids sprinkled around that chain, each Leaf being turned into an id, having no effect on the whole chain, because

(id . f) x = id (f x) = f x = f (id x) = (f . id) x

so

id . f = f = f . id

i.e. id serving as a 'zero' element w.r.t. to the function composition operation, just like 0 does with the + operation (this, by the way, is referred to as 'monoid' being formed by . and id, or by 0 and +).

---

Here's how we'd create that in-order traversal list for a tree:

inorder :: Tree a -> [a]
inorder t = foldTree g [] t
  where
  g lt a rt = lt ++ [a] ++ rt

So the list [a,b,...,n] is actually created as

[] ++ [a] ++ [] ++ [b] ++ [] ++ ... ++ [n] ++ []

and the right fold of that tree would be created as

(id . cons a . id . cons b . id . .... . cons n . id) z