Lists

Having discussed the long list of functions provided by the Foldable type class, let's implement Foldable instances for a bunch of containers to understand better how folds work. We need to implement

foldl :: (b -> a -> b) -> b -> t a -> b

or

foldMap :: Monoid m => (a -> m) -> t a -> m

The former needs to fold up the container left to right. The latter needs to go in the opposite direction, from right to left. While it is sufficient to implement only one of them, we'll discuss implementations of both, for practice.

We've seen the implementation of foldl for lists before:

foldl f = go
  where
    go accum []     = accum
    go accum (x:xs) = go (f accum x) xs

Here's foldMap. Since it needs to fold the list right-to-left, its implementation is similar to that of foldr:

foldMap f = go
  where
    go []     = mempty
    go (x:xs) = f x <> go xs

For the empty list, the result has to be the unit of the monoid, mempty. For the non-empty list x:xs, we fold up the tail xs of the list recursively and then combine the monoid element f x with the result of go xs using the monoid multiplication <>.

Thus, we can define a Foldable instance for lists as

instance Foldable [] where
    foldl f = go
      where
        go accum []     = accum
        go accum (x:xs) = go (f accum x) xs

or

instance Foldable [] where
    foldMap f = go
      where
        go []     = mempty
        go (x:xs) = f x <> go xs