Fold on non-lists?

Question

In a recent assignment I have been asked to define fold functions for some non-list types. I'm still not quite able to wrap my head around this concept yet. Thus far, I have understood fold as performing over subsequent elements in the list. fold on Tree still do make intuitive sense, since one is able to apply some function recursively over the root's sub-trees.

However, on a datatype like:

Maybe a :: Nothing | Just a

There is no list (as it seems to me) to perform the fold action on.

I'm sure I have some issue with understanding the basic concepts here, and I would greatly appreciate some clearing up.

Answer 1

Foldable is a pretty confusing class, to be honest, because it doesn't have an awful lot of laws and it's quite possible to write quite a lot of different Foldable instances for almost any given type. Fortunately, it's possible to figure out what a Foldable instance should do in a purely mechanical way based on a Traversable instance for the same type—if there is one.

We have

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

Traversable has several different laws, but it turns out the most important one is traverse Identity = Identity. Let's see how this applies to Maybe:

traverse :: Applicative f => (a -> f b) -> Maybe a -> f (Maybe b)
traverse g Nothing = _none
traverse g (Just a) = _some

Now in the first case, you need to produce f (Maybe b), and all you have is g :: a -> f b. Since you don't have any f values, and you don't have any a values, the only thing you can produce is pure Nothing.

In the second case, you have to produce f (Maybe b) and you have g :: a -> f b and a. So the only interesting way to start is to apply g to a, getting g a :: f b. Now you have two options to consider: you could throw away this value, and just return Nothing, or you can wrap it up in Just.

By the identity law, traverse Identity (Just a) = Identity (Just a). So you're not allowed to return Nothing. The only legal definition is

traverse _ Nothing = pure Nothing
traverse g (Just a) = Just <$> g a

The Traversable instance for Maybe is completely determined by the Traversable laws and parametricity.

Now it's possible to fold using traverse:

foldMapDefault :: (Traversable t, Monoid m)
               => (a -> m) -> t a -> m
foldMapDefault f xs =
  getConst (traverse (Const . f) xs)

As this applies to Maybe,

foldMapDefault f Nothing =
  getConst (traverse (Const . f) Nothing)
foldMapDefault f (Just a) =
  getConst (traverse (Const . f) (Just a))

Expanding our definitions,

foldMapDefault f Nothing = getConst (pure Nothing)
foldMapDefault f (Just a) = getConst (Just <$> (Const (f a)))

By the definitions of pure and <$> for Const, these are

foldMapDefault f Nothing = getConst (Const mempty)
foldMapDefault f (Just a) = getConst (Const (f a))

Unwrapping the constructor,

foldMapDefault f Nothing = mempty
foldMapDefault f (Just a) = f a

And this is indeed exactly how foldMap is defined for Maybe.

Answer 2

As "basic concepts" go, this is pretty mind-bending, so don't feel too bad.

It may help to set aside your intuition about what a fold does to a list and think about what type a specific folding function (let's use foldr) should have if applied to a Maybe. Writing List a in place of [a] to make it clearer, the standard foldr on a list has type:

foldr :: (a -> b -> b) -> b -> List a -> b

Obviously, the corresponding fold on a Maybe must have type:

foldrMaybe :: (a -> b -> b) -> b -> Maybe a -> b

Think about what definition this could possibly have, given that it must be defined for all a and b without knowing anything else about the types. As a further hint, see if there's a function already defined in Data.Maybe that has a similar type -- maybe (ha ha) that'll give you some ideas.