The UberFunctor: Higher Order Functors

Posted by Jonathan Immanuel Brachthäuser on June 23, 2014 · 3 mins read

This week I was faced with the problem of abstracting over two functors like F1[O] = Int × O and F2[I, O] = (I => Int) × (I => O). Both look very similar, but not similar enough - so I had to repeat the functor with the slight changes over and over again. Then I came up with a solution…

The idea is strikingly simple: Since the differences are uniformly applied to every factor of the product we can abstract over this pattern. To see how this can be achieved in Scala, first lets encode both signatures naively:

// F1[O] = Int × O
trait F1[O] {
  def head: Int
  def tail: O

// F2[I, O] = (I => Int) × (I => O)
trait F2[I, O] {
  def head: I => Int
  def tail: I => O

Now we can abstract over the two special instances by defining a generic functor, parametrized over a type function that encapsulates the difference.

trait UberFunctor[T[_], O] {
  def head: T[Int]
  def tail: T[O]

where T is for “transformation” since it is some type-level function that transforms the input. The two instances can be recovered simply by applying UberFunctor with type level functions:

type Id[X] = X
type F1[O] = UberFunctor[Id, O]
type F2[I, O] = UberFunctor[({ type λ[X] = I => X })#λ, O]

That was easy, wasn’t it? The cool thing is, that this way transformations between the different shapes of related functors like F1 and F2 can be expressed as transformation between two instances of UberFunctor, highlighting the difference on the type-level.

Your help is needed: UberFunctor is of course just some working title. I am not sure how to name this concept. I only have a very basic understanding of category, yet. Maybe this concept already exists and has a terrific name? Maybe it is related to some other concept where the name could draw inspiration from?

I would love to hear some feedback, where you think this technique could be applied and how it should be called.