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.