Understanding representable functors

Representable functors are put to good use in the linear library, and they can be a useful tool in other contexts. Here's a (hopefully not completely misleading) post on the subject.

The general idea

Consider the functor that carries a type a to the type of infinite lists of elements of type a. Let's call that functor Stream. So Stream Bool is the type of infinite lists of boolean values, Stream Char is the type of infinitely long strings, and so on.

There is a type with which the Stream functor has a special relationship: the type ℕ of natural numbers. Think about it: any value of type Stream a can be alternately represented by a function of type ℕ -> a. To recover the stream, we just have iterate over the naturals, applying the function at each step. Conversely, we can regard a Stream a value as a "memoized" version of a ℕ -> a function. We can recover the function by indexing on the stream.

There are other functors that have a similar "special relationship" with a certain type. That type need not be ℕ. Consider the following very simple functor:

This Pair functor has a special relationship with the Bool type. A value of type Pair a can be alternately represented by a function Bool -> a. Conversely, we can regard a value of type Pair a as a memoized or tabulated version of a Bool -> a function.

There seems to be a pattern here!

One more example: the Identity functor is represented by the trivial unit type (), that has only one value and carries no information. Identity a is just a, so there are no "positions" over which to "range", so to speak.

Composition, products, sums

Functors have the nice property that the composition of two functors is still a functor. We can ask ourselves if the composition of two representable functors is still representable. The answer is yes.

The composition (think of it as "nesting") of two functors is represented by the product of the representations of the original functors. Think of the type Stream (Stream a). It is like an infinite bidimensional array of a values. To index into it, we need two coordinates. So it is represented by (ℕ,ℕ).

The product of two functors is a functor as well. And the product of two representable functors is again representable! It is represented by the sum of the representations of the original functors. Supose you have a pair (Stream a, Stream a). If we want to index into it, we must first choose a side, and then drill into the stream of that side. So the product is represented by Either ℕ ℕ.

A third way of combining functors is summing them. Is a sum of representable functors representable? I don't know about the theory, but intuitively the answer seems to be no. We can't "index" on sum types, because we might attempt to target a branch that isn't there!

The Haskell implementation

The Representable typeclass can be found in module Data.Functor.Rep of the adjunctions package. It has the Distributive class as a prerrequisite. Distributive can be understood as the class of functors with a "fixed shape" whose values can be zipped together easily.

If you check the source, you'll see that the type families extension is used to associate each instance of Representable with its representation. It is instructive to explore which correspond to which. For example, Rep Identity = () as we have alredy mentioned.

You might wonder, why is Stream missing from the list of instances, after having been used many times as an example? It's there, actually, but you have to squint a little.

The Stream functor can be defined as Cofree Identity (the definition of Cofree is here). Cofree Identity is represented by sequences of unit () values. And the type of sequences of () is isomorphic to the natural numbers.