Representable Functors

December 23, 2020

It took me a long time to grok rep­re­sentable func­tors (Chap­ter 14 of Cat­e­go­ry Theory for Pro­gram­mers), so I hope this post will help anyone who’s also strug­gling. It’ll be a bit silly if I try to moti­vate every­thing from scratch, so I’ll assume some famil­iar­i­ty with:

  • Mor­phisms
  • Iso­mor­phisms
  • Func­tors
  • Hom-func­tors (or reader func­tors)

Here we go.


A rep­re­sentable func­tor is a func­tor which is iso­mor­phic to the hom-func­tor.

To unpack that state­ment, we must first under­stand how func­tions and data are really two sides of the same coin.

Imag­ine a Post­gres data­base stor­ing user data. To keep things simple, let’s say we’re just stor­ing names:

CREATE TABLE "user" (
  id SERIAL PRIMARY KEY,
  name TEXT NOT NULL
);

localhost=# select * from "user";
 id | name
----+------
  1 | Adam
  2 | Eve
(2 rows)

Given an id, we can lookup the user’s name.

Now, it’s not too much of a stretch to imag­ine con­vert­ing this Post­gres table whole­sale into a func­tion that looks like the fol­low­ing:

def findUsernameById(id: Int): String = {
  if (id == 1) "Adam"
  else if (id == 2) "Eve"
  ...
}

It sounds con­trived, but hope­ful­ly you can see how func­tions are really just com­pact rep­re­sen­ta­tions of data. Some people try to use terms like mem­o­iza­tion — that once you com­pute a func­tion with some set of argu­ments, you can store it, and that is the same thing as look­ing up a map by key.

Since func­tors can be thought of con­tain­ers for data, then for a con­tain­er to be iso­mor­phic to the hom-func­tor is to mean that this con­tain­er can “do” what­ev­er the hom-func­tor can.

Let’s see an exam­ple of a func­tor which is con­sid­ered rep­re­sentable: the Stream func­tor.

case class Stream[X](h: () => X, t: () => Stream[X])

Notice that a stream, as com­pared to a list, cannot be empty, and does not have a def­i­nite length.

Let’s also go ahead and define the func­tor and hom-func­tor (named here more canon­i­cal­ly as ReaderFunctor):

trait Functor[F[_]] {
  def map[A,B](f: A => B): F[A] => F[B]
}

def ReaderFunctor[E](r: E => _) = new Functor[({ type F[X] = E => X })#F] {
  def map[A, B](f: A => B): (E => A) => (E => B) = { r => r andThen f }
}

Then, we define a Rep­re­sentable trait like so:

trait Representable[F[_]] {
  type A
  def tabulate[B](f: A => B): F[B]
  def index[B](f: F[B]): A => B
}

We’ll explain more about tabulate and index in a bit, but notice first of all that the Rep­re­sentable trait con­tains an abstract type member A. This will be our fixed ref­er­ence point in the cat­e­go­ry of pro­gram­ming types.

And so, we can imple­ment the Stream func­tor as a rep­re­sentable func­tor, using Int (assume non-neg­a­tiv­i­ty) as the con­crete type for A:

def representableStream = new Representable[Stream] {
  type A = Int
  def tabulate[B](f: A => B): Stream[B] = {
    Stream[B](() => f(0), () => tabulate(f compose (_ + 1)))
  }
  def index[B](f: Stream[B]): A => B = f match {
    case Stream(x, xs) => {
      n => if (n == 0) x() else index(xs())(n - 1)
    }
  }
}

And if you stare at this imple­men­ta­tion long enough, what you’ll see is that tabulate some­how takes a given func­tion f, and “maps” out all results of that func­tion for every input inte­ger 0, 1, 2…, and “stores” that as a stream. Or at least you can think of that way, since it does­n’t actu­al­ly do the (infi­nite) com­pu­ta­tion eager­ly, it “stores” it in the tail of the stream.

And index is the inverse of that — it takes a stream and unrav­els it as far as is needed to find the nth item in the stream, which con­tains the answer to the input n.

Visu­al­ly, it looks like this:

We have a func­tion, rep­re­sent­ed here as a lookup table:

representable functors 1

and we have a Stream[X] for some type X:

representable functors 2

They are really the same thing:

representable functors 3

Note the bi-direc­tion­al arrows. We can go between both rep­re­sen­ta­tions loss­less­ly.

In some sense, what we’re trying to say is, for some func­tion that takes a (non-neg­a­tive) inte­ger and returns some x in X, a Stream[X] is the same thing. They are iso­mor­phic. tabulate compose index should be the iden­ti­ty func­tion.


Let’s look at a small­er exam­ple. Say we have a Pair type, which con­tains 2 values of some type A:

case class Pair[A](a: A, b: A)

If we use Boolean as the “key” type, Pair is rep­re­sentable, since there are only two pos­si­ble values for such a func­tion Boolean => B. We arbi­trar­i­ly choose false to rep­re­sent the first item in the Pair, and true to rep­re­sent the second item in the Pair.

def representablePair = new Representable[Pair] {
  type A = Boolean
  def tabulate[B](f: A => B): Pair[B] = {
    Pair[B](f(false), f(true))
  }
  def index[B](f: Pair[B]): A => B = f match {
    case Pair(a, b) => {
      n => if (n) f.b else f.a
    }
  }
}

Here, tabulate con­verts a func­tion Boolean => B into a Pair:

scala> representablePair.tabulate((x) => if (x) 1 else 2)
val res0: Pair[Int] = Pair(2,1)

And index con­verts a Pair into a func­tion Boolean => B (here B is a string):

scala> val f = representablePair.index(Pair("A", "B"))
val f: Boolean => String = $anon$1$$Lambda$1197/1238209644@57cabdc3

scala> f(false)
val res2: String = A

scala> f(true)
val res3: String = B

And now cir­cling back to the book, we have:

For F to be rep­re­sentable we require that: There be an object α in C; one nat­ur­al trans­for­ma­tion α from C(α, −) to F; anoth­er nat­ur­al trans­for­ma­tion, β, in the oppo­site direc­tion; and that their com­po­si­tion be the iden­ti­ty nat­ur­al trans­for­ma­tion.

The nat­ur­al trans­for­ma­tion α here is tabulate, and β is index. The hom-set C(α, −) rep­re­sents the set of all map­pings, and there is a nat­ur­al trans­for­ma­tion from Reader[A] to Stream[A].

As an exten­sion, note that the List func­tor [] is not rep­re­sentable, because a list may be empty or too short.

representable functors 4