What is a Functor?

Photo by ArtHouse Studio from Pexels

Intro

The term functor comes from category theory and describes, in a nutshell, a mapping between two categories of things. In programming, these categories are usually types (for instance the generic type T), classes (like String), or kinds (types of types, like F[T]).

Consider the following function

def map[C, D](c: C)(f: C => D): D = f(c)

This function takes two generic type parameters, C and D. It also takes an instance of C, which we call c, in the first parameter list.

In the second parameter list, it takes a function from C to D, which we call f.

map applies the function f to the parameter c and returns some value of type D, since f maps values of type C to values of type D.

A functor is similar to map, except we're mapping entire categories of things. So we don't want to map a single element c to a single element of type D -- we want to map the type C to the type D.

---

Functors in Scala

In Scala, this looks like

trait Functor[F[_]] {
  def map[C, D](fc: F[C])(f: C => D): F[D]
}

where F[_] is a higher-kinded type with an existential type parameter, _.

Existential types in Scala 2 are basically unbounded types, similar to the wildcard type in Java. They have been dropped from Scala 3.

---

Example

All we've done above is move from c: C to fc: F[C] in the first parameter list and "wrap" the return type of map in this same outer type F. The above can be a bit confusing, so imagine that F[_] is a new collection type that we're writing called Improv (similar to Scala's Option):

sealed trait Improv[+C] {
  import Improv._
  def and[D](`then`: C => D): Improv[D] = this match {
    case Yes(what) => Yes(`then`(what))
    case No => No
  }
}

object Improv {
  case class Yes[C](what: C) extends Improv[C]
  case object No extends Improv[Nothing]
}

We might then write an ImprovFunctor like

class ImprovFunctor extends Functor[Improv] {
  def map[C, D](ic: Improv[C])(f: C => D): Improv[D] = ???
}

The above is a bit clearer -- here we're mapping the type Improv[C] to a type Improv[D], using a function C => D. If you're familiar with mapping over collection types, you might know that the way we accomplish this is by applying the function f to every element of ic, to produce a new collection with elements of type D.

(Also note that we write Functor[Improv] and not Functor[Improv[_]].)

In that case, the implementation of map could be written like

class ImprovFunctor extends Functor[Improv] {
  def map[C, D](ic: Improv[C])(f: C => D): Improv[D] = ic.and(f)
}

For example:

import Improv._
val im = new ImprovFunctor
im.map(Yes(24))(n => s"I just thought of something funnier than $n")

evaluates to

Yes("I just thought of something funnier than 24")

We've mapped the Improv[Int] to an Improv[String].

Functor Laws

Given the functions

def id[C](c: C) = c
def c2d[C, D](c: C): D = ???
def d2e[D, E](d: D): E = ???

...an object im is a Functor[F] if it satisfies the two functor laws for any fc: F[C]:

1. im.map(fc)(id) == id(fc)
2. im.map(im.map(fc)(c2d))(d2e) == im.map(fc)(c => d2e(c2d(c)))

Let's investigate these laws using the ImprovFunctor.

The first functor law requires the following concrete example to be true

// fc == Yes(24)
assert {
  im.map(Yes(24))(id) == id(Yes(24))
}

...and the second functor law requires the following concrete example to be true

def c2d(c: Int): Double = c + 1.0
def d2e(d: Double): String = s"$d!"

assert {
  im.map(im.map(Yes(24))(c2d))(d2e) ==
  im.map(Yes(24))(c => d2e(c2d(c)))
}

These are of course just specific examples using a specific class and so they don't prove that ImprovFunctor is a functor, but, provided that our definition of a Functor in Scala is accurate

trait Functor[F[_]] {
  def map[C, D](fc: F[C])(f: C => D): F[D]
}

...the Scala compiler can determine that our ImprovFunctor implementation conforms to this interface.