Representable Functors

Representable functors are a powerful tool in category theory. As it turns out, they’re pretty useful in Haskell as well. Here’s a few examples of what they are and how to use them

First, some definition. We’re interested in Hask which the category where objects are types and arrows are functions. A representable functor for us, is a special functor from Hask -> Hask (an endofunctor). Now when we apply category theory to Haskell, we also pretend Hask is Set (The category of sets). There’s a type of functor called a hom-functor. It’s a functor that looks like this

    newtype Hom a = (->) a
    -- Hom a b = a -> b

Now, a Hom implements Functor like this

    instance Functor Hom where
        fmap f hom = f . hom

In other words, Hom a takes an object b to the set of all morphisms a -> b. It takes an arrow b -> c to the function Hom a b -> Hom a c using composition. Nothing stunning yet.

Now consider some arbitrary functor F. Suppose there exists an object a so that F is isomorphic to Hom a. What would this look like?

    type family Obj (f :: * -> *) :: *
    class Functor f => HomIso f where
      toHom :: f a -> Hom (Obj f) a
      toF   :: Hom (Obj f) a -> f a

And we have the laws that

    toHom . toF = id
    toF . toHom = id

Then f is a representable functor. From now on, I will refer to HomIso as Repr to emphasize this. The simplest representable functor is of course Hom a.

Let’s notice some useful properties of representable functors.

    lookup :: Repr f => f a -> Obj f -> a
    lookup = toHom

Our functor can look things up! Cool! Let’s use this idea to guide us to finding some simple representable functors. Let’s look at a trivial case

    newtype Identity a = Identity {runIdentity :: a}
                       deriving(Eq, Show, Functor)

    newtype Unit = Unit
    type instance Obj Identity = Unit

    instance Repr Identity where
      toHom (Identity a) = const a
      toF f = Identity $ f Unit

Since Identity has only one value, Unit indexes it exactly. A more complicated example

    data Prod a = Prod a a
                deriving(Eq, Show, Functor)

    data Two = InL | InR
    type instance Obj Prod = Two

    instance Repr Prod where
      toHom (Prod a _) InL  = a
      toHom (Prod _ a) InR = b
      toF hom = Prod (hom InL) (hom InR)

This is all quite well, but what about infinite data structures? This is Haskell! we want those too.

    data Forever a = Cons a (Forever a)
                   deriving (Functor)

    data Nat = Z | S Nat
    type instance Obj Forever = Nat

    instance Repr Forever where
      toHom (Cons a as) Z = a
      toHom (Cons a as) (S n) = toHom as n

      toF f = cs z
        where cs n = Cons (f n) (cs (S n))

Since Forever goes, well, forever. It can be keyed with natural numbers, which we represent here with Nat. Then toHom is classic recursion and toF is classic co-recursion.

There are tons more of these, but hopefully now you’re getting the idea. Here’s another cool thought

    switch :: (Repr f, Functor g) => g (f a) -> f (g a)
    switch g = toF $ \obj -> fmap ($ obj) hom
      where hom = fmap toHom g

Wait a moment, what if f and g where both Repr instances? Then

    switch . switch = id

Neat! We can use representable functors to switch around functors.

Now, what about applicatives, can we use a representative functor to build one?

    -- To keep type classes from getting confused
    newtype Wrap f a = Wrap {unWrap :: f a}

    instance (Repr f) => Applicative (Wrap f) where
      pure    = toF . const
      f <*> a = toF $ \obj -> toHom f obj $ toHom a obj

So we can actually build out applicatives from a representable functor. How about monads?

    instance (Repr f) => Monad (Wrap f) where
      return = toF . const
      m >>= f = toF $ \obj -> ($obj) . toHom . f $ toHom m obj

Notice how these are working? The functor and monad are defined “pointwise”. Basically we’re applying each function at a “point” in our functor’s underlying structure and then peeking at the result at that point.

If we translate this into Forever functor, our applicative instance would correspond to taking a stream of functions, and zipping it with a stream of values. Our monad instance would do the same, and select the point in the same position in the resulting list. That’s why we often refer to these as zippy monads.

Well hopefully I’ve convinced you that representable functors are interesting, remember, we were able to build all of this from a simple isomorphism with Hom. Cool right?