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 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:
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.
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.