People learn in many ways. For computer science and programming, some enjoy starting from the math, the theory, and proofs. From there they find their way to practical concerns in everyday development. They think in abstract algebra and category theory, encoding their solutions in their chosen language.
That’s awesome.
Other people learn differently, by example, with problems solved with patterns and techniques that later they discover have names and ideas rooted in mathematics.
There are a lot of excellent books, papers and blogs that follow the first path, usually because the authors tend to be the kind of people that are happy to learn from the math and theory, applying it later.
This document follows the second path, describing a set of ideas collectively called the Typeclassopedia, by starting from a problem and developing a solution.
Here is some code that returns a value:
trait Blub {
/**
* @return a Foo or null
*/
def foo(): Foo
}
This is a common pattern, the method returns a Foo instance or null if the method cannot do its job. Anyone calling this method needs to know that the result might be null which is extremely error prone and completely insane.
We can do better than that by returning a value that represents the possibility that the method might not return a result, an optional value.
Instead of the insidious null, we can represent this optional value with a type called Option, a type that represents a value that may or may not exist.
Here is a trivial encoding:
sealed trait Option[+A]
// we have a value
case class Some[A](v: A) extends Option[A]
// no value
case object None extends Option[Nothing]
Notice that None extends Option[Nothing] which is the bottom type which extends all other types.
Because Option is covariant, Option[Nothing] extends all other Option types.
Using Option in Blub results in:
trait Blub {
def foo(): Option[Foo]
}
Two things have happened:
null!We now have another problem: how do we work with an Option? We certainly don’t want to explicitly detect whether the result is a Some or None everytime by pattern matching or other means.
Instead, we can add a method to Option that enables a function to be applied to the value. Traditionally, that method is called map.
trait Option[+A] {
def map[B](f: A => B): Option[B] =
this match {
case Some(a) => Some(f(a))
case None => None
}
}
If the Option is a Some, then the function can be applied to the value, and a new Some returned with the result. If the Option is a None, then map can only return None since there is no value to apply the function to.
So we can now work with values in options by mapping an Option with a function.
Lists are important data structures and its self-evident why they are needed.
Scala’s standard library comes with a List so we won’t go into writing one (challenge: write one yourself as an exercise) but there are a couple of things to point out.
List’s map method is roughly like this:
def map[U](f: T => U): List[U]
Like Option, the map method takes a function, f, and returns a new List.
In Scala, if an object has a map method like Option and List do, it can be used in for comprehension,
syntactic sugar that compiles to map:
val x: Option[String] = ...
for {
v <- x
} yield v.length
// is the same as
x.map(v => v.length)
There is more required to really use Options and Lists in for comprehensions which we will see later.
Looking at Option and List we find that both map methods are very similar:
f: A => B, and then g: B => C, the result is equivalent to passing a composite
function: f andThen g, or g compose f.So the question is, can we abstract this concept into something more general?
Unsurprisingly the answer is yes, and that abstraction is called a Functor. Here it is:
trait Functor[F[_]] {
def map[A, B](f: A => B): F[B]
}
This trait simply says that a Functor must provide a map method, just as the map methods in Option and List do.
However, instead of making types implement this trait, a much more flexible mechanism is to decouple types from their Functor instances, allowing any type with type constructors like Option and List (taking a single type parameter) to have a Functor instance.
To do this we use the power of typeclasses in Scala, which looks like this:
trait Functor[F[_]] {
extension [A, B](x: F[A])
def map(f: A => B): F[B]
}
Its very similar to the original trait but instead declares map as an extension method for any type F[A]. The implementations for List and Option are straight forward:
given Functor[Option] {
extension [A, B](m: Option[A])
override def map(f: A => B): Option[B] = m map f
}
given Functor[List] {
extension [A, B](m: List[A])
override def map(f: A => B): List[B] = m map f
}
To use these instances we only need to be imported either directly, or implicitly if declared in companion objects:
import MyInstance.{given _} // if the instance isn't on the companion
def launch[A, M[_]: Functor](m: M[A]): Result = {
val v: M[B] = m.map(myFunkyFunction)
// …
}
We have learnt a new way to decouple behaviour from data types using typeclasses that has numerous advantages:
Learn more about Scala 3 typeclasses and all the syntax used above here.
TODO - migrate to Scala 3
We have a small problem with our map method, it can return anything at all. Why is that a problem?
// a function that returns an option
def sqrt(x: Double): Option[Double] = if (x >=0) Some(math.sqrt(x)) else None
// a value in an option
val x: Option[Int] = ???
val y: Option[Option[Int]] = x.map(v => sqrt(v))
y has ended up as an Option of an Option of Int which is annoying. So to handle this special case we are going to introduce a new method called flatMap. In Option it looks like this:
sealed trait Option[A] {
def map[B](f: A => B): Option[B] = ???
def flatMap[B](f: A => Option[B]): Option[B] =
this match {
case None => None
case Some(x) => f(x)
}
}
List has a similar method.
This method turns out to be very useful. Lets assume we have two Options and we want to work with the values of both in some way, flatMap will be useful:
val x: Option[Int] = ???
val y: Option[Int] = ???
val sum: Option[Int] = x.flatMap(xv => y.map(yv => xv + yv))
This doesn’t look so nice but fortunately scala’s for comprehension deals with this by offering syntactic sugar for both map and flatMap. The above is identical to:
val sum: Option[Int] =
for {
xv <- x
yv <- y
} yield xv + yv
Much better.
List has a similar method so that we can work with multiple lists like this:
val x: List[Int] = ???
val y: List[Int] = ???
val sums: List[Int] =
for {
xv <- x
yv <- y
} yield xv + yv
Looking at Option and List we find that both flatMap methods are very similar, and as with the map method we can recast it a little:
Option:
def flatMap[A, B](o: Option[A], f: A => Option[B]): Option[B]
List:
def flatMap[A, B](o: List[A], f: A => List[B]): List[B]
These methods are practically identical, what we can do is define this method in terms of any type that takes a single parameter, a type constructor, like this:
trait FlatMappingThing[M[_]] {
def flatMap[A, B](m: M[A], f: A => M[B]): M[B]
}
The implementations for List and Option are:
object AllTheFlatMappingThings {
implicit object ListFlatMappingThing extends FlatMappingThing[List] {
def flatMap[A, B](m: List[A], f: A => List[B]): List[B] = ???
}
implicit object OptionFlatMappingThing extends FlatMappingThing[Option] {
def flatMap[A, B](m: Option[A], f: A => Option[B]): Option[B] = ???
}
}
And using this code with typeclasses:
def launch[A, M[_]](m: M[A])(implicit flatMappingThing: FlatMappingThing[M]): Result = {
val mapped: M[B] = flatMappingThing.flatMap(m, myFunkyFunction)
// return a result
}
So this is very similar to the functor case.
We have applied the same pattern as the functor above, but this time for the flatMap method. This enables us to cope with multple values of Options, Lists or any other kind of type constructor, or functions that return Options, Lists, etc.
Stand back … it is a Monad!
There is a little more to a monad than just a flatMap method, it needs to obey some laws too which we will skip, but if you’re interested search Google for Scala Monad Laws.
The abstractions above are great, but because we’ve moved the map and flatMap methods to typeclasses, scala for-comprehensions won’t work since the map and flatMap method are no longer on the objects you are working with. In the specific case of Option and List they do have those methods because they are part of the Scala library and thats what the original authors did. But if you had a new type for which you’d defined typeclass instances, then that new type won’t have map and flatMap.
The solution is to provide some syntax for any type that has a Functor or Monad typeclass.
implicit class FunctorSyntax[F[_]: Functor, A](v: F[A]) {
def map[B](f: A => B): F[B] = implicitly[Functor[F]].map(v, f)
}
implicit class MonadSyntax[M[_]: Monad, A](v: M[A]) {
def flatMap[B](f: A => M[B]): M[B] = implicitly[Monad[F]].flatMap(v, f)
}
… to be continued.
A variable has a type. For example, x: Int means the variable x has the type Int.
A proper type, also known as an inhabitated type, is a type that can have values. The type Int is a proper type because it has values like 0 and 1.
List[Int] is also an inhabited, or proper type, that is inhabited by values like 1 :: 2 :: Nil, instances of a list.
A type constructor is something that takes a type and produces a type. Examples are anything with type parameters like List or Option. Type constructors are not inhabited, it is not possible to have values of List or Option, only List[X] or Option[Y].
In type theory it is useful to denote different kinds of types so that we can talk more generally about types, type constructors, etc.
Types are denoted with an asterisk: Int is of type *
A type constructor taking a single type is denoted like this: *
-> *, meaning that given a type, denoted by the first *, it will produce a new proper type, *. For example, A List given an Int will produce List[Int].
Something like Either[A, B], which takes two type parameters, is denoted like this: *-> * -> * because it takes two proper types and produces a type.
Either[Int, String] is a proper type contructed with Either and two proper types, Int and String.
Kinds are a way of describing similar types at an abstract level. *, * ->
*, * -> * -> *, are kinds. Kinds are useful when working more abstractly with types, both proper and improper (inhabited or uninhabited).
Further reading Wikipedia Types of a Higher Kind Stack Exchange
Typeclasses are an extremely common pattern used extensively in libraries like the Typelevel libraries. Martin Odersky et al describe typeclasses as follows:
Type classes are useful to solve several fundamental challenges in software engineering and programming languages. In particular type classes support retroactive extension: the ability to extend existing software modules with new functionality without needing to touch or re-compile the original source.
Read more here: Type Classes as Objects and Implicits
In Scala, the typeclass pattern consists of several parts:
For example, a trait with a show method to transform a T into a String
trait Show[T] {
def show(t: T): String
}
// A companion object with some useful default instance of the typeclass
object Show {
implicit object StringShow extends Show[String] {
def show(s: String): String = s.toString
}
implicit object IntShow extends Show[Int] {
def show(t: Int) = t.toString
}
// This show requires a Show[T] so its a method
implicit def listShow[T](implicit tShow: Show[T]): Show[List[T]] = new Show[List[T]] {
def show(l: List[T]): String = {
val list = l.map(v => tShow.show(v)).mkString(",")
s"List($list)"
}
}
}
// Example of use
def foo[T](v: T)(implicit show: Show[T]) = show.show(v)
println(foo("hi"))
println(foo(123))
println(foo(List(1,2,3,4,5)))
As an exercise, implement Show[Option[T]] and Show[Either[A, B]]
It is not uncommon to read blogs or other articles in which the follow statements are made:
What do they mean?
Option represents an optional value, or sometimes, success and failure.
It has two constructors: None and Some[T], where Some[T] contains a value of type T.
Option is of kind * -> *
Lists represent lists of things, but they are often referred to as representing indeterminism. A function returning a list can return any number of values including nothing (the empty list), hence the list is being used to represent an indeterministic result.
Lists are recursive data structures because they are typically defined in terms of themselves: a list is either the empty list, Nil, or a single element followed by a list.
List is of kind * -> *
Either is of kind * -> * -> *
Intuitively it simply wraps a value, it does not embody anything meaningful but is useful in some contexts beyond the scope of this document.
Identity is of kind * -> *