Book Image

Haskell Data Analysis Cookbook

By : Nishant Shukla
Book Image

Haskell Data Analysis Cookbook

By: Nishant Shukla

Overview of this book

Table of Contents (19 chapters)
Haskell Data Analysis Cookbook
Credits
About the Author
About the Reviewers
www.PacktPub.com
Preface
Index

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