Non-Foldable Containers

Folds represent the idea of traversing a container from left to right or from right to left. Thus, intuitively, a container is foldable if it can be construed as representing a sequence of elements, if it can be flattened into a list. For lists, this is obvious. For Maybe and Identity, it was fairly trivial. And for trees, we obtained a fairly natural ordering of the elements by traversing the tree from left to right. If we had a container that stored its elements in a grid, we could still make this container foldable by traversing the container row by row or column by column. So there are many containers that are foldable. That's a good thing because this means that all of the functions in the Foldable class are applicable to them. We get a lot of operations on such containers essentially for free.

Still, there are some containers that are not foldable. Important examples are containers that are abstractions of functions. We saw one such example:

newtype Reader r a = Reader { runReader :: r -> a }

Remember, we considered Reader r to be a container that stores values of type a indexed by values of type r. Thus, if we had any hope to make Reader foldable, we would need to be able to enumerate the index values of type r in some order. That would give us the ordering of the container elements corresponding to these index values. However, in general, we should not expect that such an enumeration of values of type r exists. We can't enumerate Floats or Doubles because, at least logically, they represent real numbers, which are uncountably infinite.

The types that are enumerable are those that are instances of Enum. So we could at least hope that we could define an instance such as

instance Enum r => Foldable (Reader r) where
    ...

This doesn't work either because being an instance of Enum doesn't mean that there are only finitely many values of type r. For example, Integer is an instance of Enum, but it is logically an infinite type: it can represent arbitrarily large integers. This would make Reader Integer a container of infinite size. How would we accumulate all the values in an infinite container? So there really isn't any meaningful way to make Reader an instance of Foldable.

Incidentally, Haskell allows us to define infinite lists. They can't be folded either. We still have a Foldable instance for lists because this does make sense for finite lists, and we rather accept that the functions in the Foldable class fail on infinite lists than that we deprive finite lists of these useful functions.