What is a Functor?
Tags: scala, functional, computerscience
Published: 2021-11-28 11:40:22

> _Photo by [ArtHouse Studio](https://www.pexels.com/@arthousestudio?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels) from [Pexels](https://www.pexels.com/photo/old-map-of-iceland-on-wall-4338273/?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels)_

### Intro

The term [functor](https://en.wikipedia.org/wiki/Functor) comes from category theory and describes, in a nutshell, a mapping between two categories of things. In programming, these categories are usually [types](https://en.wikipedia.org/wiki/Type_system) (for instance the generic type `T`), [classes](https://en.wikipedia.org/wiki/Class_(computer_programming)) (like `String`), or [kinds](https://en.wikipedia.org/wiki/Kind_(type_theory)) (types of types, like `F[T]`).

Consider the following function

```scala
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`.

---

### `Functor`s in Scala

In Scala, this looks like

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

where `F[_]` is a [_higher-kinded type_](https://stackoverflow.com/a/15204140/2925434) with an _existential type parameter_, `_`.

> Existential types in Scala 2 are basically [unbounded types](https://dzone.com/articles/existential-types-in-scala), similar to the [wildcard type](https://docs.oracle.com/javase/tutorial/java/generics/wildcards.html) in Java. They have been [dropped from Scala 3](https://dotty.epfl.ch/docs/reference/dropped-features/existential-types.html).

---

### 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`):

```scala
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

```scala
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

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

For example:

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

evaluates to

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

We've `map`ped the `Improv[Int]` to an `Improv[String]`.

### Functor Laws

Given the functions

```scala
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_](https://en.wikipedia.org/wiki/Functor_(functional_programming)) 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

```scala
// 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

```scala
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

```scala
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.