Introduction

This is a companion blog my fifth Functional Justin YouTube video which you can find here: https://youtu.be/wNVQ75KM8-4

If you're new to the series I'm exploring Scala 3 and functional programming using a simple expression evaluator, and adding features to it every week. Most of the videos are coffee break sized (10-15 minutes) but this one took a bit longer as I needed more time to explain the concepts. Next time will probably be back down to the more bite-sized format.

In video 1, https://youtu.be/J01u_Dmrx5U, I showed how you can use Scala 3 features like Context Functions to pass context around. The eval function below is an expression evaluator that takes expressions of type Exp, returns a result of type Int and has an implicit environment Env which is a symbol table of values. 

type WithEnv = Env ?=> Int

def eval(exp: Exp): WithEnv =
  exp match
    case Var(id) => handleVar(id)
    case Val(value) => value
    case Add(l,r) => handleAdd(l,r)

def handleVar(s: String): WithEnv =
  summon[Env].get(s).get

This is a nice example of context functions, but not so good an example of a pure functional program, let's see why.

Purity

What is a pure function? In short it has three properties… it is a total function, it is deterministic and it has no side effects.

A total function has an answer (of a fixed type) for everything. Our expression evaluator is a total function because every expression you put in can be evaluated and returns a value. Now let's say we had a divide function, and you can pass in a divisor that is zero and the answer is infinity. That is not representable by Int so the function is not total. We can only throw an error at this point.

By deterministic, we mean that the evaluator gives the same answer for every input expression, which may seem self-evident, but imagine if we had a random number command. When used it would return different answers every time and the program would not be deterministic.

Finally, by no side effects, we mean the program does nothing impure. It is not going to print to the screen, send an email, or throw errors.

Is the expression evaluator code pure?

If your nose wrinkled when you saw this code above summon[Env].get(s).get then you're probably an experienced Scala programmer who knows that you should not call get on an option.

What's happening there is a symbol table look up. First I 'summon' the symbol table (see video 1 to understand context functions and where the symbol table is coming from), then I look up the symbol using get. This returns an Option because the symbol may be missing!

I hopefully pointed out at the time that you shouldn't call get on an Option in serious code because it will throw an error. That means that as a program that can throw errors, our program is not pure.

Handling errors with Either

Since the 90s the Haskell folk have been dealing with impurity by wrapping it up in data types that describe the effects, and manipulating them with type classes. If that sounds hopelessly abstract, then fear not, in practise it's quite simple and we will fix our problems with a few lines of code.

Firstly let's look at what we mean by a data type… it is usually a higher kinded type that "contains" things of another type that you can define at compile time.

Scala's Either is a great example of a data type. It encodes the concept of errors. Our pure code does not deal with errors but we can still encode errors by wrapping them as follows. 

val e1: Either[String, Int] = Right(10)
val e2: Either[String, Int] = Left("Oops")

By encoding our values like this we can represent a computation that has succeeded as a Right value, and a computation that has failed with some error as a Left value.

What this means is we can no longer apply pure functions these values directly. That is sort of the point. What we wanted to do was isolate pure functions from having to deal with errors at all. So how do we operate on Eithers? Well you are probably familiar with the map function, and that can be used to apply a pure function to an either! 

val e3 = e1.map(a => a + 1)
// Right(11)
val e4 = e2.map(a => a + 1)
// Left("Oops")

Categorically Speaking

You may not really think of it as Category Theory, but whenever you map an Either you are using Functors!

The Haskell documentation is a nice place to learn about Functors. If you think of a normal pure function as a mapping of values from A to B, a Functor can map values that have been embellished, or wrapped in some special data type.

https://wiki.haskell.org/Functor

Helpfully, the kind folks behind Scala 3 have added how to implement type classes to their documentation. We can use that a starting point to build our own Functor and then make an instance that works with Eithers. 

trait Functor[F[_]]:
  extension [A, B](x: F[A])
    def ffmap(f: A => B): F[B]

This is all we need to define a Functor type class that can extend supported types with a map function. Note that I've added an f to differentiate the function from the built in map. Then I added another f by mistake, don't tell anyone, they might not notice!

Before we can use this against an Either we need to implement an instance of the typeclass. Remember that Functor needs a type of kind F[_]. It has one "type hole". Either has two, which is not going to work, so let's start by specialising to Either with only a fixed error type of String.

First we make a type alias that reduces the Either to one unknown type, the computation result type A.

Next we provide an implementation of ffmap that does the work of mapping our pure function over an Either.

Note that this is roughly the same as the pure function. Instead of A => B we are mapping F[A] => F[B] where F is the Either. 

type StringEither[A] = Either[String, A]

given Functor[StringEither] with
  extension [A, B](x: StringEither[A])
    def ffmap(f: A => B): StringEither[B] = {
      x match {
        case Right(a) => Right(f(a))
        case Left(err) => Left(err)
      }
    }

Let's try it out. 

val e1: Either[String, Int] = Right(10)
val e2: Either[String, Int] = Left("Oops")

val e3 = e1.ffmap(a => a + 1) // Right(11)
val e4 = e2.ffmap(a => a + 1) // Left("Oops")

We can now apply pure functions to Eithers with String error types. Where we want to get to is to be able to apply pure functions to Either[Error,Numeric[A]] so we're not quite there yet.

The first problem is that we can't handle the Error type that I want to use in my expression evaluator, we can only handle String. Well we can just make another instance of Functor for Either[Error,A]?

Well, yes we could, but how about we make a generic instance of Functor for all Eithers?

To do that we need to use type lambdas. These were available in Scala 2 but are greatly simplified in Scala 3.

https://dotty.epfl.ch/docs/reference/new-types/type-lambdas.html

Here's the new instance for Functor with some notable changes. 

1: given eitherFunctor[E]: Functor[[A] =>> Either[E, A]] with
2:   extension [A, B](x: Either[E,A])
3:       def ffmap(f: A => B): Either[E,B] = {
4:         x match {
5:           case Right(a) => Right(f(a))
6:           case Left(err) => Left(err)
7:         }
8:       }

Line 1 is where the action is. First note that we named the given instance eitherFunctor. Our previous instance had no name. You can leave the name out, but it's not recommended, especially for libraries, since it makes the code easier to work with. See also that the instance itself takes parameter E which will represent our error type.

Next the instance of Functor is for the type [A] =>> Either[E, A] which is our type lambda. It means please give me a type that has a single parameter A but that will be substituted into the Either[E,A] in a way that is similar to how parameters are substituted into a lambda function. 

val e1: Either[String, Int] = Right(10)
val e2: Either[Int, Int] = Left(1)

val e3 = e1.ffmap(a => a + 1) // Right(11)
val e4 = e2.ffmap(a => a + 1) // Left(1)

Now we can map over any type of Either! As you can see in the first case the pure function mapped over the A. In the second case the pure function was not executed and the error value is simply passed along.

Functor Laws

Next time we'll look at the Functor laws and show that our code obeys them.

Wrap up

I hope you enjoyed this blog and/or video. Please share, like or subscribe and help me spread this content to those that may find it useful.