Foldable and ...

Foldable and Friends

Foldable

The type class Foldable generally relies on Monoid, and it describes data structures that can be folded to a summary value, so the mappend(<>) defined on Monoid is needed to show that the containing data in Foldable can be combined:

class Foldable t where
    fold :: Monoid a => t a -> a
    foldMap :: Monoid b => (a -> b) -> t a -> b
    foldr :: (a -> b -> b) -> b -> t a -> b
    foldl :: (b -> a -> b) -> b -> t a -> b

Here is a foldMap example on lists:

foldMapList :: Monoid m => (a -> m) -> [a] -> m
foldMapList f [] = mempty
foldMapList f (x:xs) = f x <> foldMapList f xs

The minimal definition is foldMap or foldr, and using one of these two we can define them all:

fold = foldMap id
foldMap f = foldr (mappend . f) mempty
toList = foldMap (\x -> [x]) -- Here, we use the monoid of lists, which is concatenation

However, the folding directions are not absolute. For example, we can define foldl in terms of foldr (even though it is not efficient enough, it still shows some type of homomorphism):

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldl f z ys = foldr (\x g -> g . f x) id ys z

To understand the entire process, we first notice that if we want to reverse the computation order, we may leave the computation “undone”, and gradually fold other elements into the process.

So in this implementation of foldl, the type b is used as the “undone” computation, i.e. function a -> a (like (+) 1), and the initial value is the identity map. After iterations, we shall get:

id -- \x -> x
\x -> f x y0
\x -> f (f x y0) y1
...
\x -> f (... f  (f (f x y0) y1) ... yN)

When the folding process ends, we apply the “undone” computation to the initial value z, and we get the final result, in a reversed order.

---

In conclusion, “Folding” is the abstraction of sequential operations (or sequential recursion) on a data structure. Example:

map f = foldr ((:) . f) [] -- or foldMap (pure . f)

Traversable

Now let’s take a look at map.

map :: (a -> b) -> [a] -> [b]
map g [] = []
map g (x:xs) = g x : map g xs

We get the motivation of Traversable from the need of generalizing map to deal with effects brought by various functors.

class (Functor t, Foldable t) => Traversable t where
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

instance Traversable [] where
    traverse g [] = pure []
    traverse g (x:xs) = pure (:) <*> g x <*> traverse g xs

In the default definition of Traversable, another function sequenceA is introduced. It folds a series of effects into a single effect:

sequenceA :: Applicative f => t (f a) -> f (t a)
sequenceA = traverse id

--- Examples:
> sequenceA [Just 1, Just 2, Just 3]
Just [1, 2, 3]

> sequenceA [Just 1, Nothing, Just 3]
Nothing

We can also define traverse in turn:

traverse g = sequenceA . fmap g