Foldable

(Not updated very recently)

class Foldable_ t where
    foldr   :: (a -> b -> b) -> b -> t a -> b
    foldMap :: Monoid m => (a -> m) -> t a -> m
    fold    :: Monoid m => t m -> m
    ...

Minimal complete definition is foldr or foldMap. Why can’t fold possibly be a minimal complete definition? Because it doesn’t work for all t a, only those where a is a Monoid.

Default definitions:

foldMap =
  foldr (\a acc -> f a <> acc) mempty

foldr f b ta =
  appEndo (foldMap (\a -> Endo (f a)) ta) b

fold =
  foldMap id

Data.Foldable, exposed by Prelude, contains additional members.

Example: Binary Tree

data Tree a
    = Empty
    | Node (Tree a) a (Tree a)

instance Foldable_ Tree where
 -- foldMap :: Monoid m => (a -> m) -> Tree a -> m
    foldMap f Empty        = mempty
    foldMap f (Node l a r) = foldMap f l <> f a <> foldMap f r

If Tree is a Functor…

instance Functor Tree where
 -- fmap :: (a -> b) -> Tree a -> Tree b
    fmap f Empty        = Empty
    fmap f (Node l a r) = Node (fmap f l) (f a) (fmap f r)

… then the Foldable can be written yet more concisely via fold:

instance Foldable_ Tree where
 -- foldMap :: Monoid m => (a -> m) -> Tree a -> m
    foldMap f = fold . fmap f    -- boilerplate definition with two passes

 -- fold :: Monoid m => Tree m -> m
    fold Empty        = mempty
    fold (Node l a r) = fold l <> a <> fold r

Many types which are both Functors and Foldables have even more in common…

Source Files

• Foldable_.hs