Haskell Data Analysis Cookbook

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