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
.
Functor
s 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 notFunctor[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 map
ped 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]
:
-
im.map(fc)(id)
==
id(fc)
-
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.
Top comments (0)