Introduction to Functors With Scala 3

You’ve recently started learning functional programming and have been successful in writing functions, but then something unexpected happens. A wild functor appears! What is that? Why is it here?

Don’t be scared, functors are a mathematical structure that arises from category theory, and they can be found everywhere in functional programming. For those of you who don’t know category theory, this will give you enough knowledge to understand functors and use them to program.

Motivation

Let’s imagine that we have some library that parses JSON and returns a JSONReader[A] object. The object has some method to extract the value. Our logic will get the configuration reader for the timeout, and then pass that configuration reader to the function that sets the time out. A very simple illustration of what happens is below:

// we put in in a trait so that it compiles
trait Example:
  // trivial definition, to illustrate
  type JSONReader[A] = A

  // some provided business service
  def setTimeoutFromConfig(r: JSONReader[Int]): Unit

  // some library provides this
  def getConfigReader: JSONReader[String]

  // we get the reader, but it is the wrong type
  val configReader = getConfigReader

  // we define the transformation
  def transform(in: JSONReader[String]): JSONReader[Int]

  // we can now call our function
  setTimeoutFromConfig(transform(configReader))
end Example

This kind of problem arises al the time. We need to adapt a type to be used in another context. Furthermore, we do not realize it but we have certain expectations of this transformation. To behave as expected it would be like extracting the String, applying to _.toInt to it, and wrapping it back into the JSONReader object. We expect that only the contents or result of the JSONReader object will be modified, but the computation itself remains unchanged.

The questions that arises is: How can I define my JSONReader type and my transform function in a way that is both:

• captures my intuition that only the contents but not the container is modified
• captures my intuition that the container is not modifying the contents when apply several transformations to it.

This is the question that functors provide the answer to. Functors are data structures that represent computations or containers and that allow the contents or result to be modified without modifying the structure itself.

Definition

A functor F has two parts:

• a part that transforms a type into another type. For example, if we have type A, we will call the new type F[A]. In our example above, it would be the type constructor of JSONReader[A].
• A part that transforms functions into other functions. Lets write it like this: def map[A, B](f: A => B): F[A] => F[B] . This is a slightly more generic version of the transform function from above. In this case, we take a function from the original type and create a new function from it.

There are several ways to write map, so there are some restrictions on it. Our new type needs to fulfil two equations, called the functor laws. The laws say that:

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

The two functor laws are written in Scala code, but they are still so abstract that we cannot expect the compiler to check them when written like that. Let’s write a function to check them, that the compiler can compile and execute:

def check1stFunctorLaw[A, F[_]](fa: F[A])(map: (A => A) => (F[A] => F[A])): Boolean =
	map(identity[A])(fa) == identity(fa)

def check2ndFunctorLaw[A, B, C, F[_]] (fa: F[A])(f: A => B, g: B => C)(map: [X, Y] => (X => Y) => (F[X] => F[Y])): Boolean =
  map((g.compose(f)))(fa) == map(g).compose(map(f))(fa)

Now, even though the code above compiles and actually checks the two functor laws, it is still abstract. Indeed, to actually use them, we need to first define our first functor.

Some Concrete Functors

To define a functor, we have several ways of achieving that in Scala. We can, for example, define a new type using the type. Let’s define a very simple functor, the identity functor.

type IdFunctor[A] = A

The identity functor feels like cheating. We are just transforming A into A? That is not even a transformation. But we have fulfilled the requirements. The second part is easy to implement, we have:

def mapId[A, B](f: A => B): IdFunctor[A] => IdFunctor[B] = f

The functor laws are vacuously verified. We can say that our type IdFunctor with the function map forms a functor.

Let’s use our functions to test the two function laws for some values:

// we can check for example that for fa: IdFunctor[Int] = 2
// the first law holds
check1stFunctorLaw[Int, IdFunctor](2)(mapId)
// we can check fhat for fa: IdFunctor[String], and f(x) = x.toInt and g(x) = x + 2
// the second law holds
check2ndFunctorLaw[String, Int, Int, IdFunctor]("5")(_.toInt, _ + 2)([X, Y] => (f: X => Y) => mapId(f)) 	

A lot is happening here - we instantiated a functor with a type, created a value for that functor, and now we can run it.

Now let’s create another functor. This time we use an ADT. This is the constant functor. We define the constant functor as follows:

case class CstFunctor[C, A](c: C):
	def getConstant: C = c
	def map[B](f: A => B): CstFunctor[C, B] = CstFunctor.map(f)(this) // this is the normal way you will see functors defined, as a method.

object CstFunctor:
	def map[A, B](f: A => B): [C] => CstFunctor[C, A] => CstFunctor[C, B] = 
		[C] => ((cst: CstFunctor[C, A]) => CstFunctor[C, B](cst.getConstant))

Once again, we are almost cheating here. This functor will pass all checks because it actually never changes, but a functor it is, and you can create an instance of it and check that it passes all laws.

Now, let us define a functor that is actually used in the real world, and a lot. The next functor is a sort of combination of the identity functor and the constant functor, and believe it or not, we use it all over the place. Let’s define the Option functor:

enum MyOption[+A]:

	def map[B](f: A => B) = MyOption.map(f)(this)

	case MyNone
	case MySome(a: A)

object MyOption:
	def map[A, B](f: A => B): MyOption[A] => MyOption[B] =
		_ match 
			case MyNone => MyNone
			case MySome(a) => MySome(f(a))

If you remove the MyNone part, you end up with a sort of identity functor. If you remove the MySome part, you end up with a sort of constant functor. This is no other than the well known Option type. You can, once again, instantiate it and check that it always passes the functor laws.

Exercise

Try to define a functor for the list type as defined here:

enum MyList[+A]:
	case MyNil
	case MyCons(h: A, tail: MyList[A])

What is The Intuition Behind All This?

We can see that the Option functor is a data structure that either contains one value or none. A list is a data structure that contains several values. We can also see a function as a functor, for example:

type MyFunctionFunctor[X, Y] = X => Y

This case shows a function from something to be defined (X) to A. We can define a map function for that as:

def map[A, B](f: A => B): [X] => MyFunctionFunctor[X, A] => MyFunctionFunctor[X, B] =
	[X] => (g: X => A) => f.compose(g)

Futures, tasks and other effects form a functor. Indeed, they will produce a value and we can always define a map function that can transform the value. The added value of functors is that a library can give you a value wrapped in some unknown container, but if it is a functor, then you know that:

• you can modify the value without affecting the container
• the container will not affect the operations on the values

We observe functors are data structures where the container or computation does not interact with the result type or computed value. You can change the value inside the computation or container without worrying about changing the structure or computation.

Let us define something that does not respect the functor rules:

enum MyOptionOnce[+A]:

	def map[B](f: A => B) = MyOptionOnce.map(f)(this)

	case MyNoneOnce
	case MySomeOnce(a: A)

object MyOptionOnce:
	def map[A, B](f: A => B): MyOptionOnce[A] => MyOptionOnce[B] =
		_ match 
			case MyNoneOnce => MyNoneOnce
			case MySomeOnce(a) => MyNoneOnce
import MyOptionOnce.*
// you can easily check that it fails for the first functor law
check1stFunctorLaw[Int, MyOptionOnce](MySomeOnce(2))(MyOptionOnce.map) == false

This structure self-destructs after a map. As we can see, if you try to change the value inside, it forgets about it and the structure collapses. We can do infinite variations on this concept, the main point being that somehow by manipulating the content, we did something to the container. Funnily, MyOptionOnce will always pass the second functor law.

The other law concerns more with the fact that we want our container to respect the operations of its contained type. This means that after I have moved an operation to the new type of map, the container (or the map implementation may not mess with the operations). Let us define a new version of the option type that will mess with the operations when they return a 0:

enum MyOptionSneaky[+A]:

  def map[B](f: A => B) = MyOptionSneaky.map(f)(this)

  case MyNoneSneaky
  case MySomeSneaky(a: A)

object MyOptionSneaky:

  def map[A, B](f: A => B): MyOptionSneaky[A] => MyOptionSneaky[B] =
    _ match
      case MyNoneSneaky => MyNoneSneaky
      case MySomeSneaky(a) =>
        MySomeSneaky(f(a)) match
          case MySomeSneaky(b) if a == b => MySomeSneaky(b) // keep identity
          case MySomeSneaky(0) => // never return 0
            MySomeSneaky(1.asInstanceOf[B])
          case _ => MySomeSneaky(f(a)) // the standard case

import MyOptionSneaky.*
// it passes for the first functor law because it checks that the function changes something
check1stFunctorLaw[Int, MyOptionSneaky](MySomeSneaky(0))(MyOptionSneaky.map)
// it will fail only if the first function returns 0
check2ndFunctorLaw[String, Int, Int, MyOptionSneaky](MySomeSneaky("0"))(_.toInt, _ + 2)([X, Y] => (f: X => Y) => MyOptionSneaky.map(f)) 
check2ndFunctorLaw[String, Int, Int, MyOptionSneaky](MySomeSneaky("1"))(_.toInt, _ + 2)([X, Y] => (f: X => Y) => MyOptionSneaky.map(f)) 

My point here, however, is that if you write your own functors, or try to redefine something that you already had, as a functor, special cases are not your friends. It is not hard to imagine a case where you have some computation that checks that nothing has changed and then does something in just one particular case like setting a default value. Something as simple as that can break the functor rules.

Conclusion

We have learned about functor, implemented some of them and understood how they work and how to use them. You have also seen how to break the functor laws and are now ready to use them in your code.

If you have read until here and liked this content please consider subscribing to my mailing list. I write regularly about Blockchain Technology, Scala and Language Engineering. Have questions? Leave a comment below and I’ll try to answer!