Functor

Functor

Often when we learn things, our perception of how much the subject matter is understood fluctuates. That is pretty much what happens with my experience with Functor.

For a long time I thought Functor is just a fancy way of referring to mappable objects. A notable example is list. We can apply a function to each of the element in the list by mapping that function to it. As a matter of fact this really is how functor is defined in scalaz.

Later I came to realize that on top of that there are two laws that every Functor has to obey, namely identity and associative law, which basically means that if we map an identity function to a Functor it has to remain the same and that a series of maps can be rewritten as just one map with one composed function. The following code snippet from scalaz tells the full story:

trait FunctorLaw {
  /** The identity function, lifted, is a no-op. */
  def identity[A](fa: F[A])(implicit FA: Equal[F[A]]): Boolean =
    FA.equal(map(fa)(x => x), fa)

  /**
   * A series of maps may be freely rewritten as a single map on a
   * composed function.
   */
  def associative[A, B, C](fa: F[A], f1: A => B, f2: B => C)(
    implicit FC: Equal[F[C]]
  ): Boolean =
     FC.equal(map(map(fa)(f1))(f2),map(fa)(f2 compose f1))
}

That is great, until recently I read a little bit about category theory and notice that in the category of smaller categories, Functor refers to the morphism that turns one category into another category. By definition, the transformation by the Functor should keep the structure of the category, which consists of three parts: objects, morphisms and some sort of internal structure. This is not that easy to digest, but.. after a while it kinda sinks in.

But wait, is the Functor in category theory somehow connected to the one we talked about in the context of functional programming? If it is, how can we interpret this fancy of referring to mappable objects with its corresponding definition in category theory? hmmmm…

Gladly this is answered rather clearly in the Haskell Wikibook on Category Theory. Basically if we think of the types of any functional language as a category (let’s use T to denote that) and Functor[T] as another category (which is a subset of the category T). Then Functor can be seen as a morphism that transforms the former category to later. Since the map function of the Functor has following signature:

1
def map[A, B](fa: F[A])(f: A => B): F[B]

It essentially turns a function X of A => B to a function Y of F[A] => F[B] therefore effectively transformed X, which is the morphism in the category of T, to Y, which is the morphism of category Functor[T].

Interesting. :)

Written on June 12, 2015