Type Class 101: Functor

In the last installation of this series, we covered the Foldable and now we take a turn to discuss the Functor type class. Basically we cover some building blocks out of which more complex type classes can be build.

The Functor is usually well understood, as each scala programmer has made intensive contact with it already:

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

Let us build a type class instance for Option[A] without resorting to the build-in map function:

implicit val optionFunctorInstance = new Functor[Option] {
  def map[A,B](F: Option[A])(f: A => B) : Option[B] {
    F match {
      case Some(a) => Option(f(a))
      case None => None
    }
  }
}

Laws

A Functor has to follow some laws as well, in particular:

  • Identity: F[A].map(x => x) == F[A]
  • Composition: Given
    • f: A => B and
    • g: B => C,
    • then F[A].map(g compose f) == F[B].map(g) compose F[A].map(f)

The graph above can be read as follows (and category theorists will kill me now, but I do not have a better way to express it): Given your boring scala types A and B, and a function f between them, this same function can be applied between the cool types F[A] and F[B] using map. Hence map allows us to lift a function in the context of F[_] provided there is a functor instance for F[_]

Something fishy in the land of functors

Considering that we are so used to using the map operation one might expect Functor instances for all occurrences of map in the scala. This is not true. For example using scala collections provide Set.map but scalaz does not. Why? I honestly can’t explain it in all details, but Set.map is not well behaved. Consider Set(1,2,3,4).map(x => 3). Before you had a Set of size 4, now you have one of size 1. I am pretty sure that this is not the real reason why there is not functor for set, and before you rush off to create that pull request for the missing set functor instance, just believe me for a second that others had that thought before and were never seen again on github.

What this boils down to is: there are laws, and if you break them, then… We need to absolutely rely on the laws, otherwise we cannot build more complex abstract algorithms on top of the foundation.

Further or not so further learning

How do you learn this stuff, how am I going about learning this? The underlying mathematical concepts of type classes (at least some of them), are called Category theory. I find these books fairly hard to read. I get a thrill out of it too, because despite the fact that I fought a live long war against mathemathics (school, university, paying rent) I am still very much attracted by its beautiful power of reasoning, which I am sometimes missing in computer science. There are a lot of academic papers and books available using Haskell, but I promised myself to write this blog series without resorting to Haskell, primarily because I would need to learn it myself first. Nevertheless grokking the concepts is often not too hard. Then there is one book available which cannot be praised enough, which is Functional programming in Scala. And there is Stackoverflow.

Cliffhanger

In the next installments of this series, we will cover how to implement the dashed arrow in the graph, that is how are we going to put something in a A in a F[A]. This will bring us on to Applicatives and Monads. We will then also see, that it is possible to implement one type class in terms of another.

For further articles in this series: TypeClass101

typeclass101 scalaz scala

Kommentare