In an effort to publish more than one blog post a year, I’ve decided to write about smaller topics. Today I’m going to talk about the notion of a ‘base functor’, and how the popular recursion-schemes library uses base functors to make recursion schemes more elegant and ergonomic in practice.

Repeating Ourselves

Throughout this series of posts, we’ve seen the pattern of parameterizing our data types in terms of a recursive type variable. In the first installment, we went from this:

data Expr
  = Index Expr Expr
  | Call Expr [Expr]
  | Unary String Expr
  | Binary Expr String Expr
  | Paren Expr
  | Literal Int
  deriving (Show, Eq)

to this—the same data type, but of kindIf you’re not familiar with the notion of a ‘kind’, you can think (loosely) about the kind of a data type t as a measure of how many arguments it takes. Our Expr type takes no arguments, so its kind is “star”: *. A data type that takes one argument has kind ‘star to star’, * -> *. A data type that takes three arguments, like Either, has kind * -> * -> *. The high-level description of a kind is ‘the type of a type’, but you can think about them as merely providing information as to the parameters taken, if any, by a data type. (The :k) directive in GHCi provides information on the kind of any type or typeclass you provide.

* -> *, with all recursive occurrences of the Expr type replaced with the type variable a:

data ExprF a
  = Index a a
  | Call a [a]
  | Unary String a
  | Binary a String a
  | Paren a
  | Literal Int
  deriving (Show, Eq, Functor)

We then used the Term trick, a Y-combinator for the type system, to parameterize ExprF in terms of itself, yielding a data type equivalent to the original Expr but that can be mapped over with fmap and folded with cata:

newtype Term f = In { out :: f (Term f) }

type Expr = ExprF (Term ExprF)

Similarly, in part 4 we represented the natural numbers with a data type of kind * -> *:

data Nat a
    = Zero
    | Next a
    deriving Functor

And we represented the Plant type we grow with another such data type:

data Plant a
  = Root a
  | Stalk a
  | Fork a a a
  | Bloom

This is a good and fluent way to build data types. However, it has its disadvantages.

Consider the humble linked list, containing values of type a: [a].

infixr 5 :
data [] a = a : [a]
          | []

Certainly cata, the fundamental right-fold operation, should be able to support folding over this structure: after all, it’s of kind * -> *. But if we apply Term to this data type, we run into trouble quite quickly: we lose the ability to store elements in a list. The type variable a can only hold nested Term a values: there is no place we can actually store list elements. This is, as you can tell, not particularly useful.

Now, of course, we can do our standard song-and-dance routine, converting [a] into a type where its recursive element is replaced by a new type variable to represent recursive occurrences (the [a] in the (:) constructor:)

data ListF a b
  = Cons a b
  | Nil
    deriving (Show, Eq, Functor)

This looks a little different from our prior examples—it’s of kind * -> * -> *, not * -> *—but the principle is the same. We add a new type variable, here called b, to represent recursive occurrences of the List type. And now we can fold over a list:

listSum :: Num a => Algebra (ListF a) a
listSum (Cons a b) = a + b
listSum Nil = 0

But this is clumsy. There’s something fundamentally wrong if we have to write a replacement for the venerable [] type. Recursion schemes are meant to be elegant—manually creating alternate implementations for every recursive data type doesn’t strike me as particularly elegant. But I am, thankfully, not alone in feeling this way—the literature contains many ways to work around this. I’ll focus on the solution provided by the recursion-schemes package.

Base Functors to the Rescue

The first thing you see when you open up the recursion-schemes documentation is the following type family declaration:

This understandably intimidates a number of people, especially given its lack of documentation. But this is less forbidding then it appears, and the added mental overhead is worth it—the presence of the Base type family is one of the things that sets recursion-schemes apart from its competition in terms of ease-of-use.

The purpose of the Base type family is to tie together a standard Haskell data type—such as our original Expr formulation, or the humble [] list—with its parameterized, “base” representation. Its definition is very concise:

type family Base t :: * -> *

While a full-fledged tutorial on type families is beyond the scope of this post (the best such reference is the GHC wiki), we can think of type families as a way to write functions on the type-level. If we were to declare a type family, and an instance of this family (analogous to an instance of a typeclass):

type family Something t

type instance Something Foo = Bar

then anywhere we encounter the invocation Something Foo the GHC type system will resolve that to Bar. While this may seem unnecessary—if you mean Bar, why not just write Bar?—it provides us a rich facility with which to associate a type with another.

Look at the definition of Base again. The kind signature there indicates that, whenever you pass in a concrete type as the variable t, you will yield a data type parameterized with one additional variable. This corresponds to our experience with ExprF and List: Expr went from kind * to * -> *, and [a] went from kind * -> * to * -> * -> *.

The Base type family doesn’t tell us much on our own. The most illustrative path open to us is to look at an instance declared with Base.

type instance Base [a] = ListF a

This declares a type family instance. Anywhere we mean to read ListF a, we can write Base [a]. This provides important organizational meaning: there is only one sensible parameterized implementation for any recursive type, and thus (thanks to Haskell’s support for type families) there is only one implementation of Base a for any given type a.

This isn’t particularly exciting on its own. The real fireworks start here, with the definition (simplified here for pedagogical purposes) of the Recursive typeclass.

class (Functor (Base t)) => Recursive t where
  project :: t -> Base t t
  cata    :: (Base t a -> a) -> t -> a

The Recursive typeclass is similar to the Foldable typeclassAs you can see by the name of its containing module, Data.Functor.Foldable. This class was originally called Foldable, but the presence of Foldable in the standard library made the duplication unsupportable, and it was changed to Recursive.

. The analogy holds: if we define a Recursive instance for our data type t, whether that’s Expr or [a] or anything else, we can fold over this type. However, instead of providing a simple fold, we provide two functions: a project function that takes a type t and returns the same type but transformed into its Base form, and a cata function that, given an algebra from Base t a to a (to wit: Base t a -> a), and an initial t value over which to fold, yields us a folded a value.

This is, at first glance, more unwieldy than our formulation of cata, which only involved a Functor constraint, and nothing related to Base functors or a new Recursive type:

cata :: (Functor f) => Algebra f a -> Term f -> a
cata f = out >>> fmap (cata f) >>> f

But, critically, this formulation of cata forces us to work with Term List rather than the simple [a]. However, Recursive allows us to work with ordinary data types: rather than provide a Term t to cata, we give an ordinary t. Recursive instances use the project function to transform the provided type into a parameterized one, then pass that transformed data type to the cata function. As such, we can now use cata to fold over an ordinary list, without having to wrap it in Term and Cons values.

sumList :: Num a => [a] -> a
sumList = cata go where
  go Nil = 0
  go (Cons a acc) = a + acc

Recursive has further tricks up its sleeve. Thanks to a MINIMAL pragma, the Recursive class only needs an implementation of project to implement Recursive fully—we still get a universal cata function for free. The implementation looks like this, if you’re interested:

class Functor (Base t) => Recursive t where
  project :: t -> Base t t

  cata :: (Base t a -> a)  -- ^ a (Base t)-algebra
       -> t               -- ^ fixed point
       -> a               -- ^ result
  cata f = c where c = f . fmap c . project

Note that the cata function is given a default definition. If you had some magic data type that admitted a faster cata than the default implementation, you could override it—however, I struggle to think of a type which would admit a custom cata.

Contained inside the Recursive class are other useful folds—para, the paramorphism, which we discussed in part 3, and ones we haven’t covered yet—the generalized paramorphism gpara and Fokkinga’s prepromorphism prepro. (We will discuss these in a future installment).

Note that the Base type is constrained in Recursive instances: t must have a Base instance, and the Base instance for t must be a Functor. Since cata is defined in terms of a recursive invocation with fmap, we need a useful fmap function over any Base instance to have a cata that typechecks.

Thanks to the Recursive typeclass, we can deal in simple data types—[a] rather than ListF, Expr rather than ExprF—while retaining the expressive folding power granted by paramterized data types. This is cool as hell. This technique is used in other libraries, such as José Pedro Magalhães’s regular.

The implementation of Recursive for [a] follows. We convert the empty list [] into Nil, and replace : with the Cons constructor.

instance Recursive [a] where
  project (x:xs) = Cons x xs
  project [] = Nil

Another valuable instance is one for Natural—as we discussed in the previous installment, we can fold over the natural numbers, bottoming out when we hit zero. We built our own Nat data type, observing that it was equivalent in definition to Maybe—recursion-schemes just uses Maybe for its Recursive and Base instance for Natural.

type instance Base Natural = Maybe

instance Recursive Natural where
  project 0 = Nothing
  project n = Just (n - 1)

Yet More Concision

As we’ve mentioned before, given a data type t, the steps for constructing its Base instance are straightforward: add a new type variable to the definition, and for each data constructor, create a new constructor with all recursive occurrences of t replaced by the new type variable.

Thanks to the magic of Template Haskell, recursion-schemes can generate this code for us:

import Data.Functor.Foldable.TH

data Expr
  = Index Expr Expr
  | Call Expr [Expr]
  | Unary String Expr
  | Binary Expr String Expr
  | Paren Expr
  | Literal Lit
  deriving (Show, Eq)

makeBaseFunctor ''Expr

The makeBaseFunctor call generates code equivalent to the following:

data ExprF a
  = IndexF a a
  | CallF a [a]
  | UnaryF String a
  | BinaryF a String a
  | ParenF a
  | LiteralF Lit
  deriving (Show, Eq, Functor)

type instance Base Expr = ExprF

instance Recursive Expr where
  project (Index a b) = IndexF a a
  project (Call a b)  = CallF a a
  -- and so on and so forth

This is the result of applying the aforementioned algorithm to our Expr type. To avoid name collisions, constructor names are suffixed with an ‘F’. (Infix operators are suffixed with a $).

The inclusion of these Template Haskell splices means that you, the programmer, can pick up the recursion-schemes library with a minimum of fuss and boilerplate. This is, in my experience writing Haskell in production, truly invaluable when dealing with nested data types: you can fold beautifully without setting up dozens of lines of boilerplate.

Reversing the Arrows, Again

In part two of this series, we generated an unfold by ‘reversing the arrows’ in cata. As you might be able to infer from the title of this section, we can do the same for Recursive, which yields us a Corecursive typeclass for unfolds:

class Functor (Base t) => Corecursive t where
  embed :: Base t t -> t
  ana :: (a -> Base t a) -> a -> t

We’ve already reversed the arrows and generated ana from cata. The only thing left to do is reverse the arrows in project, yielding embed—rather than going from a t to a Base functor, as project does, we go from a Base functor to a t.

As with cata, ana is defined in terms of fmap and embed:

class Functor (Base t) => Corecursive t where
  embed :: Base t t -> t
  ana
    :: (a -> Base t a) -- ^ a (Base t)-coalgebra
    -> a               -- ^ seed
    -> t               -- ^ resulting fixed point
  ana g = a where a = embed . fmap a . g

Instances for embed are similarly straightforward:

instance Corecursive [a] where
  embed (Cons x xs) = x:xs
  embed Nil = []

In practice, you won’t need to write your own Corecursive instances, as makeBaseFunctor creates both Recursive and Corecursive instances.

One More Aside

Particularly alert readers will notice that the definition for cata provided by Kmett in recursion-schemes is slightly different from ours. Our definition used partial application of cata in its definition—cata f, being partially applied to f, can be passed to fmap:

cata :: (Functor f) => Algebra f a -> Term f -> a
cata f = out >>> fmap (cata f) >>> f

By contrast, Kmett’s cata uses a where-clause to capture cata f with a specific name, c.

cata :: (Base t a -> a) -> t -> a
cata f = c where c = f . fmap c . project

Both formulations of cata are defined point-free, but Kmett’s struck me as somewhat unusual— the name c appears unnecessary, given that you can just pass cata f to fmap. It took several years before I inferred the reason behind this—GHC generates more efficient code if you avoid partial applications. Partially-applied functions must carry their arguments along with them, forcing their evaluation process to dredge up the applied arguments and call them when invoking the function. whereas bare functions are much simpler to invoke. (For more of the gory details, you can consult the GHC wiki page on the representation of heap objects).

Bearing this implementation detail in mind, this formulation of cata is quite elegant: by naming cata f, we can reference it not as a partially applied function, but as a regular function. Passing that function into fmap generates more efficient code—usually this kind of microoptimization doesn’t matter much, but given that cata is invoked on every iteration of a fold, the savings add up.

That’s All

I owe thanks to Edward Kmett, whose recursion-schemes library is magnificent and inspiring, and to Austin Seipp, who checked my statements about GHC code generation for accuracy.

In part V, we discuss refolds—hylomorphisms and Elgot algebras.