Implementing a Foldable instance for a tree

The idea of traversing a tree can be generalized by implementing a Foldable instance. Usually, folds are used on lists; for example, foldr1 (+) [1..10] traverses a list of numbers to produce a grand sum. Similarly, we can apply foldr1 (+) tree to find the sum of all nodes in a tree.

Getting ready

We will be folding through the following tree to obtain a sum of all node values.

How to do it...

1. Import the following built-in packages:

   import Data.Monoid (mempty, mappend)
   import qualified Data.Foldable as F
   import Data.Foldable (Foldable, foldMap)

2. The tree from Data.Tree already implements Foldable, so we will define our own tree data type for demonstration purposes:

   data Tree a = Node { value :: a
                      , children :: [Tree a] }
                      deriving Show

3. Implement the foldMap function for the Foldable instance. This implementation will give us a post-order traversal of the tree:

   instance Foldable Tree where
     foldMap f Null = mempty
     foldMap...