Learn You a Haskell for Great Good! - Miran Lipovaca [120]
Remember the tree data structure from Chapter 7? We defined it like this:
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)
You learned that a tree is either an empty tree that doesn’t hold any values or it’s a node that holds one value and also two other trees. After defining it, we made it an instance of Functor, and with that we gained the ability to fmap functions over it. Now we’re going to make it an instance of Foldable so we get the ability to fold it up.
One way to make a type constructor an instance of Foldable is to just directly implement foldr for it. But another, often much easier way, is to implement the foldMap function, which is also a part of the Foldable type class. The foldMap function has the following type:
foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m
Its first parameter is a function that takes a value of the type that our foldable structure contains (denoted here with a) and returns a monoid value. Its second parameter is a foldable structure that contains values of type a. It maps that function over the foldable structure, thus producing a foldable structure that contains monoid values. Then, by doing mappend between those monoid values, it joins them all into a single monoid value. This function may sound kind of odd at the moment, but you’ll see that it’s very easy to implement. And implementing this function is all it takes for our type to be made an instance of Foldable! So if we just implement foldMap for some type, we get foldr and foldl on that type for free.
This is how we make Tree an instance of Foldable:
instance F.Foldable Tree where
foldMap f EmptyTree = mempty
foldMap f (Node x l r) = F.foldMap f l `mappend`
f x `mappend`
F.foldMap f r
If we are provided with a function that takes an element of our tree and returns a monoid value, how do we reduce our whole tree down to one single monoid value? When we were using fmap over our tree, we applied the function that we were mapping to a node, and then we recursively mapped the function over the left subtree as well as the right one. Here, we’re tasked with not only mapping a function, but also with joining up the results into a single monoid value by using mappend. First, we consider the case of the empty tree—a sad, sad, lonely tree that has no values or subtrees. It doesn’t hold any value that we can give to our monoid-making function, so we just say that if our tree is empty, the monoid value it becomes is mempty.
The case of a nonempty node is a bit more interesting. It contains two subtrees as well as a value. In this case, we recursively foldMap the same function f over the left and right subtrees. Remember that our foldMap results in a single monoid value. We also apply our function f to the value in the node. Now we have three monoid values (two from our subtrees and one from applying f to the value in the node), and we just need to bang them together into a single value. For this purpose, we use mappend, and naturally the left subtree comes first, then the node value, followed by the right subtree.
Notice that we didn’t need to provide the function that takes a value and returns a monoid value. We receive that function as a parameter to foldMap, and all we need to decide is where to apply that function and how to join the resulting monoids from it.
Now that we have a Foldable instance for our tree type, we get foldr and foldl for free! Consider this tree:
testTree = Node 5
(Node 3
(Node 1 EmptyTree EmptyTree)
(Node 6 EmptyTree EmptyTree)
)
(Node 9
(Node 8 EmptyTree EmptyTree)
(Node 10 EmptyTree EmptyTree)
)
It has 5 at its root, and then its left node has 3 with 1 on the left and 6 on the right. The root’s right node has a 9 and then 8 to its left and 10 on the far right side. With a Foldable instance, we can do all of the folds that we can do on lists:
ghci> F.foldl (+) 0 testTree
42
ghci> F.foldl