Trees

I've already shown you the implementation of foldMap for trees so we could play with them before. Here it is again:

data Tree a = Empty | Node (Tree a) a (Tree a)

instance Foldable Tree where
    foldMap f = go mempty
      where
        go prod Empty        = prod
        go prod (Node l x r) = go (f x <> go prod r) l

We are required to implement a right-to-left fold, so we mimic foldr. Our initial accumulator, which I call prod for product here, is mempty. Next we need to inspect the tree elements right to left and, for each tree element x, multiply f x with the product of the elements to the right of x. For the empty tree, the final result is clearly the initial accumulator value prod, so we simply return it. For a non-empty tree consisting of a root element x, a left subtree l, and a right subtree r, we need to start by accumulating the elements in the right subtree. We do this using go prod r. Next we need to add x to the result. We do this by calling f to convert x into a monoid value and then multiplying f x with go prod r using the monoid multiplication <>. Whatever value this produces is the result of accumulating all elements to the right of the left subtree (because x and r are both to the right of l). Thus, we finish the accumulation by calling go recursively on l, with f x <> go prod r as the initial product.

The implementation of foldl does the same, but it walks the tree left to right:

instance Foldable Tree where
    foldl f = go
      where
        go accum Empty      = accum
        go accum (Node l r) = go (f (go accum l) x) r

We accumulate the left subtree l by calling go accum l. We add x to the current accumulator value, by calling f with arguments go accum l and x. And finally we finish the accumulation by recursively calling go on r with f (go accum l) x as the initial accumulator value.