What constitutes a fold for types other than list?

Question

Consider a single-linked list. It looks something like

data List x = Node x (List x) | End

It is natural to define a folding function such as

reduce :: (x -> y -> y) -> y -> List x -> y

In a sense, reduce f x0 replaces every Node with f and every End with x0. This is what the Prelude refers to as a fold.

Now consider a simple binary tree:

data Tree x = Leaf x | Branch (Tree x) (Tree x)

It is similarly natural to define a function such as

reduce :: (y -> y -> y) -> (x -> y) -> Tree x -> y

Notice that this reduction has a quite different character; whereas the list-based one is inherently sequential, this new tree-based one has more of a divide-and-conquer feel to it. You could even imagine throwing a few par combinators in there. (Where would you put such a thing in the list version?)

My question: Is this function still classified as a "fold", or is it something else? (And if so, what is it?)

Basically whenever anybody talks about folding, they always talk about folding lists, which is inherently sequential. I'm wondering whether "sequential" is part of the definition of what a fold is, or whether this is merely a coincidental property of the most commonly-used example of folding.

Answer 1

Tikhon's got the technical stuff down. I think I'll try to simplify down from what he said.

The term "folding" has, unfortunately, become ambiguous over the years to mean one of two things:

1. Reducing a collection sequentially in some order. In Haskell, this is what "folding" means in the Foldable class, which larsmans brings up.
2. The notion you asked for: "destructing" (opposite of constructing), "observing" or "eliminating" an algebraic data type according to its structure. Also called a catamorphism.

It is possible to define both of these notions generically so that one parametrized function is capable of doing it for a variety of types. Tikhon shows how to do in the second case.

But most often going the whole way with Fix and the algebras and such is overkill. Let's work out a simpler way of writing the fold for any algebraic data type. We'll use Maybe, pairs, lists and trees as our examples:

data Maybe a = Nothing | Just a
data Pair a b = Pair a b
data List a = Nil | Cons a (List a)
data Tree x = Leaf x | Branch (Tree x) (Tree x)
data BTree a = Empty | Node a (BTree a) (BTree a)

Note that Pair is not recursive; the procedure I'm going to show doesn't assume that the "fold" type is recursive. People don't usually call this case a "fold," but it's really the non-recursive case of the same concept.

First step: the fold for a given type will consume the folded type and produce some parameter type as its result. I like to call the latter r (for "result"). So:

foldMaybe :: ... -> Maybe a -> r
foldPair  :: ... -> Pair a b -> r
foldList  :: ... -> List a -> r
foldTree  :: ... -> Tree a -> r
foldBTree :: ... -> BTree a -> r

Second step: in addition to the last argument (the one for the structure), the fold takes as many arguments as the type has constructors. Pair has one constructor and our other examples have two, so:

foldMaybe :: nothing -> just -> Maybe a -> r
foldPair  :: pair -> Pair a b -> r 
foldList  :: nil -> cons -> List a -> r
foldTree  :: leaf -> branch -> Tree a -> r
foldBTree :: empty -> node -> BTree a -> r

Third step: each of these arguments has the same arity as the constructor it corresponds to. Let's treat the constructors as functions, and write out their types (making sure the type variables match up with the ones in the signatures we're writing):

Nothing :: Maybe a
Just    :: a -> Maybe a

Pair    :: a -> b -> Pair a b

Nil     :: List a
Cons    :: a -> List a -> List a

Leaf    :: a -> Tree a
Branch  :: Tree a -> Tree a -> Tree a

Empty   :: BTree a
Node    :: a -> BTree a -> BTree a -> BTree a

Step 4: in the signature of each constructor, we will replace all occurrences of the data type it constructs with our type variable r (that we're using in our fold signatures):

nothing := r
just    := a -> r

pair    := a -> b -> r

nil     := r
cons    := a -> r -> r

leaf    := a -> r
branch  := r -> r -> r

empty   := r
node    := a -> r -> r -> r

As you can see, I've "assigned" the resulting signatures to my dummy type variables from the second step. Now Step 5: fill those in into the earlier sketch fold signatures:

foldMaybe :: r -> (a -> r) -> Maybe a -> r
foldPair  :: (a -> b -> r) -> Pair a b -> r 
foldList  :: r -> (a -> r -> r) -> List a -> r
foldTree  :: (a -> r) -> (r -> r -> r) -> Tree a -> r
foldBTree :: r -> (a -> r -> r -> r) -> BTree a -> r

Now, these are signatures for the folds of those types. They have a funny argument order, because I did this mechanically by reading the fold type off the data declarations and constructor types, but for some reason in functional programming it's conventional to put base cases first in data definitions yet recursive case handlers first in fold definitions. No problem! Let's reshuffle them to make them more conventional:

foldMaybe :: (a -> r) -> r -> Maybe a -> r
foldPair  :: (a -> b -> r) -> Pair a b -> r 
foldList  :: (a -> r -> r) -> r -> List a -> r
foldTree  :: (r -> r -> r) -> (a -> r) -> Tree a -> r
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r

---

The definitions can also be filled in mechanically. Let's pick foldBTree and implement it step by step. The fold for a given type is the one function of the type we figured out that meets this condition: folding with the type's constructors is an identity function over that type (you get the same result as the value you started with).

We'll start like this:

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree = ???

We know it takes three arguments, so we can add variables to reflect them. I'll use long descriptive names:

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty tree = ???

Looking at the data declaration, we know BTree has two possible constructors. We can split the definition into a case for each, and fill out variables for their elements:

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty Empty = ???
foldBTree branch empty (Branch a l r) = ???
    -- Let's use comments to keep track of the types:
    -- a :: a
    -- l, r :: BTree a

Now, short of something like undefined, the only way to fill in the first equation is with empty:

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty Empty = empty
foldBTree branch empty (Branch a l r) = ???
    -- a :: a
    -- l, r :: BTree a

How do we fill in the second equation? Again, short of undefined, we have this:

branch :: a -> r -> r -> r
a      :: a
l, r   :: BTree a

If we had subfold :: BTree a -> r, we could do branch a (subfold l) (subfold r) :: r. But of course, we can write 'subfold' easily:

foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty Empty = empty
foldBTree branch empty (Branch a l r) = branch a (subfold l) (subfold r)
    where subfold = foldBTree branch empty

This is the fold for BTree, because foldBTree Branch Empty anyTree == anyTree. Note that foldBTree isn't the only function of this type; there's also this:

mangleBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
mangleBTree branch empty Empty = empty
mangleBTree branch empty (Branch a l r) = branch a (submangle r) (submangle l)
    where submangle = mangleBTree branch empty

But in general, mangleBTree doesn't have the required property; for example if we have foo = Branch 1 (Branch 2 Empty Empty) Empty, it follows that mangleBTree Branch Empty foo /= foo. So mangleBTree, though it has the correct type, is not the fold.

---

Now, let's take a step back from details, and concentrate on that last point with the mangleTree example. A fold (in the structural sense, #2 at the top of my answer) is nothing more and nothing else than the simplest, non-trivial function for an algebraic type such that, when you give pass in the type's constructors as its arguments, it becomes the identity function for that type. (By nontrivial I mean that things like foo f z xs = xs is not allowed.)

This is very significant. Two ways I like to think about it are as follows:

1. The fold for a given type can "see" all the information contained by any value of that type. (This is why it's able to perfectly "reconstruct" any value of that type from the ground up using the type's constructors.)
2. The fold is the most general "consumer" function for that type. Any function that consumes a value of the type in question can be written so that the only operations it uses from that type are the fold and the constructors. (Though the fold-only versions of some functions are hard to write and perform badly; try writing tail :: [a] -> [a] with foldr, (:) and [] as a painful exercise.)

And the second point goes even further, in that you don't even need the constructors. You can implement any algebraic type without using data declarations or constructors, using nothing but folds:

{-# LANGUAGE RankNTypes #-}

-- | A Church-encoded list is a function that takes the two 'foldr' arguments
-- and produces a result from them.
newtype ChurchList a = 
    ChurchList { runList :: forall r. 
                            (a -> r -> r)  -- ^ first arg of 'foldr'
                         -> r              -- ^ second arg of 'foldr'
                         -> r              -- ^ 'foldr' result
               }

-- | Convenience function: make a ChurchList out of a regular list
toChurchList :: [a] -> ChurchList a
toChurchList xs = ChurchList (\kons knil -> foldr kons knil xs)

-- | 'toChurchList' isn't actually needed, however, we can make do without '[]'
-- completely.
cons :: a -> ChurchList a -> ChurchList a
cons x xs = ChurchList (\f z -> f x (runlist xs f z))

nil :: ChurchList a
nil = ChurchList (\f z -> z)

foldr' :: (a -> r -> r) -> r -> ChurchList a -> r
foldr' f z xs = runList xs f z

head :: ChurchList a -> Maybe a
head = foldr' ((Just .) . const) Nothing

append :: ChurchList a -> ChurchList a -> ChurchList a
append xs ys = foldr' cons ys xs

-- | Convert a 'ChurchList' to a regular list.
fromChurchList :: ChurchList a -> [a]
fromChurchList xs = runList xs (:) []

As an exercise you can try writing other types in this way (which uses the RankNTypes extension—read this for a primer). This technique is called Church encoding, and is sometimes useful in actual programming—for example, GHC uses something called foldr/build fusion to optimize list code to remove intermediate lists; see this Haskell Wiki page, and note the type of build:

build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
build g = g (:) []

Except for the newtype, this is the same as my fromChurchList above. Basically, one of the rules that GHC uses to optimize list processing code is this:

-- Don't materialize the list if all we're going to do with it is
-- fold it right away:
foldr kons knil (fromChurchList xs) ==> runChurchList xs kons knil

By implementing the basic list functions to use Church encodings internally, inlining their definitions aggressively, and applying this rule to the inlined code, nested uses of functions like map can be fused into a tight loop.