Writing a fold for a custom data type is a fairly mechanical process. This hints that there is some common shape to a fold that we can abstract over. Since a fold is just the recursion principle for a data type, this will essentially let us decouple the recursion from the folding computation itself.

Consider the normal list data type, defined like so:

data List a = Nil | Cons a (List a)

If you replace the recursive argument with an extra type parameter, we have removed the explicit recursion from the data structure:

data ListF a b = Nil | Cons a b

How can we recover the original recursive definition from this type? If we attempt to simply substitute, we end up with something like ListF a (ListF a (ListF a ...)), continuing on infinitely. But we can’t have infinite types, so this won’t work.

newtype Fix f = MkFix { unFix :: f (Fix f) }

Fix f represents an f-wrapped value f (f (f ...)). Fix (ListF a) would give us the ListF a (ListF a (ListF a ...)) we want. Since MkFix is applied inductively, we don’t have to worry about actually constructing an infinite type.

How do we produce a f (Fix f) so that we can pass it to MkFix? In general, we can pass all of our value constructors that don’t refer to the recursive argument directly to MkFix. This coincides with the fact that they are the base cases of any recursive function on the data type. For ListF, note that Nil :: ListF a b. If we let b = Fix (ListF a), then the types work out for Fix and we can produce MkFix Nil :: Fix (ListF a). From MkFix Nil, we can construct MkFix $ Cons 1 (MkFix Nil), etc. as desired.

Exercise: Implement the two following functions and prove that they are inverses of one another:

fromListF :: Fix (ListF a) -> [a]
toListF :: [a] -> Fix (ListF a)

Exercise: What type is Fix Maybe isomorphic to?

Now that the recursive data types have been encoded using MkFix, all that’s left is to encode the recursive folds that act on them. Again, the definitions we provide won’t have any explicit recursion in them, leaving that for the generic recursion function we write later. We will make one assumption when writing our fold: the recursive argument has been replaced with the result of the recursive call already made for us.

Compare the two implementations of length on lists. The first version is the normal recursive implementation, while the second is our non-recursive version for ListF:

length :: List a -> Int
length Nil        = 0
length (Cons _ t) = 1 + length t

lengthF :: ListF a Int -> Int
lengthF Nil        = 0
lengthF (Cons _ l) = 1 + l

Our non-recursive version looks very similar, but instead of the second argument to Cons representing the tail of the list, it represents the result of lengthF applied recursively to the tail. Therefore, we can just take the value and add one to it.

Aside: For the next section, we’ll want to go ahead and make a Functor instance for ListF a. You can either implement this by hand or use GHC’s DeriveFunctor extension. Why this is necessary will become clear once we use it.

Suppose we want to run lengthF on a Fix-encoded list. We have a ListF a Int -> Int, a Fix (ListF a), and we want an Int back. Based off of that information, our function should look something like:

makeRecursive :: (ListF a Int -> Int) -> Fix (ListF a) -> Int
makeRecursive f (MkFix x) = case x of
  Nil      -> f Nil
  Cons h t -> f $ Cons h (makeRecursive f x)

Since there is only one constructor for Fix f, we only have one case to pattern match on. However, once we’ve unpacked the MkFix constructor, we have two cases: one for each in ListF a b. In the Nil case, we don’t have any extra information, so we can just apply f to Nil. Note that the Nil we are applying f to has a different type from what we matched on. In the Cons case, we have an a and a Fix (ListF a). This is where the recursion comes in, so naturally the only thing we can do is a call to makeRecursive.

How can this be generalized? Looking at the argument we are passing to f, it’s clear that we are mapping x, which is a ListF a (Fix (ListF a)), to a ListF a Int. We are doing this using a function Fix (ListF a) -> Int, so this is really just an fmap operation.

makeRecursive :: (ListF a Int -> Int) -> Fix (ListF a) -> Int
makeRecursive f (MkFix x) = f $ fmap (makeRecursive f) x

But this definition isn’t relying on anything specific about Int or ListF — it only assumes that we have a Functor instance. Generalizing the type, we have:

makeRecursive :: Functor f => (f b -> b) -> Fix f -> b
makeRecursive f (MkFix x) = f $ fmap (makeRecursive f) x

This function is usually called cata (for “catamorphism”). After renaming and conversion to point-free form, we end up with the final definition:

cata :: Functor f => (f b -> b) -> Fix f -> b
cata f = f . fmap (cata f) . unFix

Exercise: Convert the following data type to one usable by Fix:

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

Exercise: Write a function using cata on the data type from the previous exercise called depth that computes the depth of the tree.