The Foldable Class

Now that we understand how to fold a list, let's generalize the idea of traversing a list and accumulating its elements to arbitrary containers. We want to traverse the container and accumulate its elements. This abstraction is expressed by the Foldable type class. An instance of this class needs to provide many functions.

class Foldable t where
  fold     :: Monoid m => t m -> m
  foldMap  :: Monoid m => (a -> m) -> t a -> m
  foldMap' :: Monoid m => (a -> m) -> t a -> m
  foldr    :: (a -> b -> b) -> b -> t a -> b
  foldr'   :: (a -> b -> b) -> b -> t a -> b
  foldl    :: (b -> a -> b) -> b -> t a -> b
  foldl'   :: (b -> a -> b) -> b -> t a -> b
  foldr1   :: (a -> a -> a) -> t a -> a
  foldl1   :: (a -> a -> a) -> t a -> a
  toList   :: t a -> [a]
  null     :: t a -> Bool
  length   :: t a -> Int
  elem     :: Eq a => a -> t a -> Bool
  maximum  :: Ord a => t a -> a
  minimum  :: Ord a => t a -> a
  sum      :: Num a => t a -> a
  product  :: Num a => t a -> a

Thankfully, all the methods of Foldable have default implementations. Thus, to make some container an instance of Foldable, we need to implement only one of two functions—foldl or foldMap. Foldable instances also need to satisfy some Foldable laws, just as functors need to satisfy the functor laws, but I'll skip the discussion here because specifying these laws formally gets rather technical. The spirit of these laws is that every Foldable container must have a well-defined ordering of the elements it contains, and the direction of folding has to respect this ordering. In essence, a Foldable container is one that represents a sequence of elements. For example, for lists, the sequence of elements in the list provides this ordering, and foldl and foldr do indeed traverse the list left-to-right or right-to-left, respecting the ordering. Similarly, for a binary tree, we could define that the elements in the left subtree of a node come before the node itself, which in turn comes before the elements in the right subtree. The folding operations on binary trees then have to respect this ordering.

Let's discuss the functions in the Foldable class one by one. To make this less abstract, we'll play with lists, trees, and Maybe. To do this, we need Foldable instances for all three. Lists and Maybe already have Foldable instances defined in the standard library. The Foldable instance for trees is as follows. We'll revisit it when we discuss how to make various containers instances of Foldable in the following sections.

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

In GHCi:

GHCi

>>> :{
  | 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
  | :}

Now let's look at the various methods of the Foldable class.