The previous chapter gave you solid foundations to move with agility among Scala's type system. This chapter starts by introducing an advanced type system concept that goes by the name of higher-kinded types.
It proceeds with an overview of the most common functional design patterns, such as functor, applicative and monad. As you'll see, these concepts are much easier than you might think.
The chapter ends with an analysis of two very simple algebraic structures, showing how they can be exploited to write very elegant code.
Option or List are not proper types, but they are kinds. A kind is the type of a type constructor. Simply speaking, it means that, in order to be constructed, it needs another type.
In type theory, kinds like List
and Option
are indicated using the following symbology: * -> *
. The star symbol stands for type. So, * -> *
means: “Give me a type and I construct another type.” Indeed, given the List
kind, if you provide the Int
type then your final type will be List[Int]
. If you furnish a String
then it'll be a List[String]
and so on. Table 10.1 shows the most commonly used kinds.
Table 10.1 Kinds in Type Theory
Symbol | Kind | Examples |
* | Simple type. Also known as nullary type constructor or proper type. | Int, String, Double, … |
* -> * | Unary type constructor. | List, Option, Set, … |
* -> * -> * | Binary type constructor. | Either, Function1, Map, … |
(* -> *) -> * | Higher-order type operator, higher-kinded type for friends. | Foo[F[_]], Bar[G[_]], Functor[F[_]], Monad[M[_]], … |
So, a higher-kinded type is a type that, in order to be constructed, needs a kind that is a type constructor. It sounds complex, but it really isn't. An example should help.
Suppose you want to capture, in a type class, the concept represented by the map
method you've met in Option
, List
, Set
and so on. For this purpose, you can write the following abstraction:
import scala.language.higherKinds
trait Mapper[M[_]] {
def map[A, B](ma: M[A])(f: A => B): M[B
}
The first thing to do, in order to avoid a compiler warning, is import the higher-kinded type's feature. Alternatively, you can add it to the scalacOptions
key in your SBT build file as follows:
scalacOptions += "-language:higherKinds"
In the previous example, Mapper
is a higher-kinded type. Indeed, given M[_]
, which is a unary type constructor, you can construct the Mapper
type.
You've seen, from Table 10.1, that unary type constructors are, for example, List
and Option
, so let's go ahead and implement mapper for them. Furthermore, we'll use the type class pattern in order to define a method that will take an instance of Mapper
implicitly, just to make the things more interesting:
object Mapper {
def apply[M[_]: Mapper]: Mapper[M] = implicitly[Mapper[M]
def map[A, B, M[_]: Mapper](ma: M[A])(f: A => B): M[B] = Mapper[M].map(ma)(f)
implicit val optionMapper = new Mapper[Option] {
override def map[A, B](ma: Option[A])(f: A => B): Option[B] = ma.map(f)
}
implicit val listMapper = new Mapper[List] {
override def map[A, B](ma: List[A])(f: A => B): List[B] = ma.map(f)
}
}
Look at the map
method. As you can see, the context bound can also be used with higher-kinded types.
The Mapper
companion object also contains two implicit instances, one for Option
and the other for List
. The implementation is very trivial since both Option
and List
already have an implementation of the map
method.
Follow a couple of examples of the map
method in action:
import Mapper._
val as: List[Int] = List(1, 2, 3)
val bs: List[Int] = map(as)(_ + 1)
println(s"bs: $bs") // prints List(2, 3, 4)
val a: Option[String] = Some("1")
val b: Option[Int] = map(a)(_.toInt + 1)
println(s"b: $b") // prints Some(2)
As you can see, the map
method can be applied, seamlessly, both to Option
and List
instances. Ad hoc polymorphism, for the win.
Don't worry if, at this stage, something is not completely clear. Working with higher-kinded types will become second nature to you because they let you build very powerful abstractions such as functors, applicative functors, monads and so on, which are the subjects of the next sections.
If you've been using functional programming for a while you may have heard about one or all of the following funny-looking terms: functor, applicative functor and monad.
These concepts can be examined from two different approaches: using a very abstract mathematical branch that goes by the name of Category Theory or opting for a more pragmatic approach and leaving the theory for a later moment when you're prepared to dig deeper into the subject.
In this book we'll use the practical approach, trying to demystify these concepts that are, as you'll see, not too complex.
The first evidence that these concepts are not so complex is given by the functor. Do you remember the Mapper
type class seen in the previous section? That's a Functor. We called it Mapper
just to arrive at this demystifying moment. So, you can now rewrite the Mapper
type class and companion object as follows:
trait Functor[F[_]] {
def map[A, B](fa: F[A])(f: A => B): F[B
}
object Functor {
def apply[F[_]: Functor]: Functor[F] = implicitly[Functor[F]
def map[A, B, F[_]: Functor](fa: F[A])(f: A => B): F[B] = Functor[F].map(fa)(f)
implicit val optionFunctor = new Functor[Option] {
override def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
}
implicit val listFunctor = new Functor[List] {
override def map[A, B](fa: List[A])(f: A => B): List[B] = fa.map(f)
}
}
Using a functor you can apply a given function to a value that is inside a context. Examples of contexts are: Option
, List
, Try
, Future
, and so on.
For example, the Option
type represents the context of an optional value that eschews null to handle the no value case. The List
context is that of representing no value or, at least, one value. The Try
type represents the context of a possible failure.
Future
, on the other hand, represents the context where a value may be available in the future. For instance, suppose you have Some(42)
and you want to:
(Some)
Well, that's basically what a functor is for.
Also, you may have heard of the lift word associated with the functor concept. A functor lifts a simple function that goes from A
to B
to one that goes from F[A]
to F[B]
, where F
is the functor, e.g. List
or Option
. Figure 10.1 illustrates lift, which is just the effect of map.
Actually, you could have written the map
method of Functor, equivalently, as follows:
trait Functor[F[_]] {
def map[A, B](f: A => B): F[A] => F[B
}
object Functor {
def apply[F[_]: Functor]: Functor[F] = implicitly[Functor[F]
def map[A, B, F[_] : Functor](f: A => B): F[A] => F[B] = fa =>
Functor[F].map(f)(fa)
// …
}
Can you see now why they say that, through a functor, you can lift a function of type A => B
to one of type F[A] => F[B]
? Again, lift, another buzzword demystified. The latter is the signature used in Haskell, by the way. The problem with this signature in Scala is that its type inference is not as good as Haskell's. Easy up to now, isn't it? This is not the full story, though.
In order for something to be a functor, it should satisfy a couple of laws. In formulating and elaborating the laws, let's use the latter map
function signature, because it makes the reasoning easier to follow. However, in real life, you'd stick to the previous signature because of the type inference problem aforementioned. Let's see these laws then.
Given fa:
F[A]
and the identity function defined as follows:
def identity[A](a: A): A = a
The following laws must hold (in pseudo-code):
Law I: map(identity)(fa) = fa
Law II: map(f compose g)(fa) = map(f)(map(g)(fa))
The first law states that if you map the identity function over a functor, the returned functor should be the same as the original one. The second law states that if you have two functions, f
and g
, the result of mapping their composition over fa
must be the same as mapping g
to fa
obtaining, say, fb
and then mapping f
to fb
.
If you had to read Law I as a question, it would be: “What's the function that applied to fa
gives back fa
unmodified?” If you thought of the identity function you guessed it. So, this means that a potential functor satisfies the first law if and only if:
map(identity) = identity
You can easily verify that this is true both for Option
and List
. For Option
it means that, for example:
Some(42).map(identity) == Some(42)
None.map(identity) == None
This is the same reasoning for List
. So they respect the first law. Now the second. For Option
it means:
Some(42).map(f compose g) == Some(42).map(g).map(f)
None.map(f compose g) == None.map(g).map(f)
The second law is also respected—by List
too. You can say there exists a functor instance for both Option
and List
.
Note that the compiler cannot enforce these laws, so you have to test them out yourself to ensure the functorness. However, if you use functors written by others, you don't even need to worry about these laws, since they should have done it on their side. For example, popular libraries such as scalaz (
) and cats (https://github.com/scalaz/scalaz
) make sure that every functor instance satisfies the aforementioned laws.https://github.com/non/cats
Now that we have demystified the functor concept let's proceed with the applicative functor.
Before introducing the Applicative Functor (simply Applicative from now on) we want to expose the problem it resolves.
Using a functor you can apply a given function to a value that is inside a context: Option
, List
, Try
, Future
, and so on. Now, what if the function you want to apply is within a context as well? An example will make this clear.
Suppose you want to write a very trivial method, based on string interpretation, that returns a function to be applied to an Int
value. For instance, something like the following:
def interpret(str: String): Option[Int => Int] = str.toLowerCase match {
case "incr" => Some(_ + 1)
case "decr" => Some(_ - 1)
case "square" => Some(x => x * x)
case "halve" => Some(x => x / 2)
case _ => None
}
The interpret
method takes a String
and returns an Option[Int => Int]
. If the command is not recognized it returns None
. Pretty fair.
It would be nice being able to apply the function returned by interpret
, which is inside the Option
, to a value wrapped in an Option
too. Of course, as a result, we still want an Option
. Stated differently, given:
val func: Option[Int => Int] = interpret("incr")
val v: Option[Int] = Some(42)
We want to apply the wrapped function represented by func
to the wrapped value represented by v
. Applicative solves this type of problem. Here's the definition of the Applicative type class:
trait Applicative[F[_]] extends Functor[F] {
def pure[A](a: A): F[A
def ap[A, B](fa: F[A])(fab: F[A => B]): F[B
override def map[A, B](fa: F[A])(fab: A => B): F[B] = ap(fa)(pure(fab))
}
The methods exposed are pure
and ap
. The first is needed to wrap a value into a context. The ap
method, instead, is exactly what we needed to combine func
and v
from the previous example.
Moreover, Applicative extends Functor. Indeed, as you can see from the previous code, by providing pure
and ap
you can derive for free an implementation of the map
method, required by the functor.
Now, let's provide the applicative instances for Option
and List
:
object Applicative {
def apply[F[_]: Applicative]: Applicative[F] = implicitly[Applicative[F]
def pure[A, F[_]: Applicative](a: A): F[A] = Applicative[F].pure(a)
def ap[A, B, F[_]: Applicative](fa: F[A])(fab: F[A => B]): F[B] =
Applicative[F].ap(fa)(fab)
implicit val optionApplicative = new Applicative[Option] {
override def pure[A](a: A): Option[A] = Option(a)
override def ap[A, B](fa: Option[A])(fab: Option[A => B]): Option[B] = for {
a <- fa
f <- fab
} yield f(a)
}
implicit val listApplicative = new Applicative[List] {
override def pure[A](a: A): List[A] = List(a)
override def ap[A, B](fa: List[A])(fab: List[A => B]): List[B] = for {
a <- fa
f <- fab
} yield f(a)
}
}
Remember to always follow the types.
Now you can finally combine func
and v
thanks to Applicative:
val func: Option[Int => Int] = interpret("incr")
val v: Option[Int] = Some(42)
val result: Option[Int] = ap(v)(func)
Applicative, like Functor and all other concepts coming from Category Theory, come with some laws that must be respected. For a matter of space, we won't cover the applicative laws here. For the moment, you don't need to worry about them either. At this stage of things, you'll use applicatives exposed by, say, scalaz or cats, as a user. When and if you need to write your own applicative instances, you can then dig deeper into the applicative laws.
The moment to talk about monads arrived. By now, however, you should already know that it is a type class with some laws to respect.
Prof. Eugenio Moggi, an Italian professor of computer science, was the first to describe the general use of monads to structure programs.
Monads can be seen as beefed up applicatives, much in the way applicatives can be seen as beefed up functors. Indeed, here is the definition of the Monad type class:
trait Monad[M[_]] extends Applicative[M] {
def unit[A](a: A): M[A
def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B
override def pure[A](a: A): M[A] = unit(a)
override def ap[A, B](fa: M[A])(fab: M[A => B]): M[B] = flatMap(fab)(map(fa))
}
The primitives required by the Monad type class are unit
and flatMap
.
Once you have an implementation for unit
and flatMap
, you get for free, the implementation of pure
and ap
of the Applicative type class. Here is the Monad companion object that contains the implementation of Monad for Option
and List
:
object Monad {
def apply[M[_] : Monad]: Monad[M] = implicitly[Monad[M]
def flatMap[M[_] : Monad, A, B](ma: M[A])(f: A => M[B]): M[B] =
Monad[M].flatMap(ma)(f)
implicit val optionMonad = new Monad[Option] {
override def unit[A](a: A): Option[A] = Option(a)
override def flatMap[A, B](ma: Option[A])(f: A => Option[B]): Option[B] =
ma.flatMap(f)
}
implicit val listMonad = new Monad[List] {
override def unit[A](a: A): List[A] = List(a)
override def flatMap[A, B](ma: List[A])(f: A => List[B]): List[B] =
ma.flatMap(f)
}
}
Both Option
and List
expose the flatMap
method. Now let's have a look at an example. Suppose you have the following function and value:
val sqrt: Double => Option[Double] = { value =>
val result = math.sqrt(value)
if (result.toInt.toDouble == result) Some(result) else None
}
val perfectSquare: Option[Double] = Some(49)
The sqrt
function takes a Double
and, if it's a perfect square, returns the result of applying the square root to the number wrapped in a Some
; otherwise it just returns None
. You want to apply the sqrt
function to the perfectSquare
value.
Follow the types. You have an Option[Double]
and a function Double => Option[Double]
. The flatMap
method has the following signature:
def flatMap[M[_] : Monad, A, B](ma: M[A])(f: A => M[B]): M[B]
Specifically, if you replace A
and B
with Double
and M
with Option
you'll soon realize you have everything you need. Indeed:
val res: Option[Double] = flatMap(perfectSquare)(sqrt) // Some(7.0)
Again, monads have some laws that must be respected too, but we won't cover them here for space's sake. Moreover, you don't need to know them to exploit the already existent monad instances provided by scalaz and cats.
The concepts of functor, applicative, monad and many others, useful in the functional programming world, are taken very seriously by pretty famous libraries such as scalaz and cats. The latter is younger than scalaz, but better organized and documented. We recommend that you may start with cats and then, once you have mastered some concepts, take a look at the more mature scalaz library.
Another concept you may have heard of is the semigroup. It comes from mathematics.
A semigroup is an algebraic structure consisting of a set together with an associative binary operation. So, a semigroup involves a set S
and a binary operation.
The following properties must hold for a semigroup:
S
and applying the binary operation to them, the result must also be in S
.An example will make it clearer. Consider the set of integers along with the +
binary operation. Does it form a semigroup? Yes. The closure law is satisfied since, by summing two integers, you get back an integer again. Also the associativity holds. Indeed, for example:
(4 + 10) + 2 = 4 + (10 + 2)
In order to see how these mathematical structures can be of help in your day-by-day coding sessions, let's introduce the monoid, which is just a beefed up semigroup.
A semigroup with the identity element is called a monoid. Here's the formal identity element definition:
Identity element: There exists an element e
in S
such that for every element a
in S
, e • a = a • e = a
.
Again, does the set of integers along with the +
operation form a monoid? You've already seen that it forms a semigroup. If you can find the identity element then it's also a monoid. For the plus operation, the identity element, or the neutral element, is the zero. Indeed:
x + 0 = 0 + x = x, for all x being an integer.
Note that the set of integers with the *
operation forms a monoid too. In this case the neutral element is the unit. Indeed:
x * 1 = 1 * x = x, for all x being an integer
OK, enough math; let's get back to coding and see how these mathematical concepts can make your code cleaner and more elegant.
First, let's capture the semigroup and monoid concepts:
trait Semigroup[A] {
def append(a1: A, a2: A): A
}
trait Monoid[A] extends Semigroup[A] {
def zero: A
}
Now, suppose that you want to abstract the concept of summation. That is, given a List[A]
, you want to be able to sum all its elements. Scala already exposes the sum method on List
, but, unfortunately, it works only with numbers. So the following attempts will work:
scala> List(1, 2, 3).sum
res0: Int = 6
scala> List(3.14, 42.6, 3).sum
res1: Double = 48.74
However, if you try to use sum on a List[String]
it won't work because there's no instance of the Numeric
type class for String
:
scala> List("hello", ", ", "world") .sum
<console>:8: error: could not find implicit value for parameter
num: Numeric[String
List("hello", ", ", "world") .sum
^
Can you write a more generic sum method that will also work for strings? Yes, thanks to the monoid structure. Here is the method definition:
def sum[A](elements: List[A])(implicit M: Monoid[A]): A =
elements.foldLeft(M.zero)(M.append)
Look how beautiful and elegant that is! As you already know, foldLeft
expects an initial element of type A
and a binary function of type (A, A) => A
. That's what we are providing through the monoid structure.
In order to make it work for integers you just need to provide an implicit instance of Monoid[Int]
in scope. For String
, you implement Monoid[String]
and make sure it's in scope, implicitly. Let's do it:
object Monoid {
def apply[A: Monoid]: Monoid[A] = implicitly[Monoid[A]
implicit val intMonoid = new Monoid[Int] {
override def zero: Int = 0
override def append(a1: Int, a2: Int): Int = a1 + a2
}
implicit val stringMonoid = new Monoid[String] {
override def zero: String = ""
override def append(a1: String, a2: String): String = a1 + a2
}
}
As you can see, the implementation isn't fancy. The identity element for the String
type is, naturally, the empty string.
Here's the sum
method in action:
val intResult: Int = sum(List(1, 2, 3))
val stringResult: String = sum(List("hello", ", ", "world"))
println(intResult)
println(stringResult)
The output is:
6
hello, world
It seems to work like a charm. Now, suppose you want your sum
function to work with Option
types too. Do you need to change anything from the previous code? No, you don't. You just need to provide an implementation of Monoid[Option[A]]
:
implicit def optionMonoid[A: Semigroup]: Monoid[Option[A]] =
new Monoid[Option[A]] {
def zero: Option[A] = None
def append(f1: Option[A], f2: Option[A]): Option[A] = (f1, f2) match {
case (Some(a1), Some(a2)) => Some(Semigroup[A].append(a1, a2))
case (Some(a1), None) => f1
case (None, Some(a2)) => f2
case (None, None) => None
}
}
What follows is an example of its use:
val optionResult: Option[String] =
sum(List(Some("hello"), Some(", "), None, Some("world")))
println(optionResult)
The output is:
Some(hello, world)
Now some words about one interesting part of the implementation. Notice that we require an implementation of Semigroup
for A
so that you can use it to append the two values of type A
when both values are of type Some
.
You might wonder why we require it to be a Semigroup
and not a Monoid
. The reason is that you only need the append
method, and it's a good development practice to use the least powerful abstraction that will get the job done. This makes your code more reusable. Furthermore, there could be plausible implementations of Semigroup
for some types, but not valid Monoid
implementations since the zero
might not make any sense in some contexts. Similarly, if your method can get away with an applicative, don't require a monad as evidence.
Concepts such as Functor, Applicative Functor and Monad are very useful to provide a common interface to very different and, sometimes, unrelated context Pure algebraic structures can help you write very elegant and reusable code.
Object-oriented design patterns let you use the same vocabulary with other OO programmers. Now functors, applicatives, monads, and so on let you do the same thing among functional programmers. Some object-oriented design patterns reflect the limitation of a language/paradigm, in terms of expressivity. Just think that many of the classic twenty-three design patterns used in OOP are easily implemented in functional programming through HOFs and type classes.
Finally, take into account that we approached the concepts in this chapter very pragmatically. Of course, in doing so, we had to gloss over some details and use some terminology improperly. From a Category Theory point of view this may not be acceptable, but we hope that this served to help you understand the part of these concepts that you need as a programmer. This chapter was meant as an introduction to these concepts. The field is so big you can easily write an entire book about it. Actually, if you want to deepen your knowledge about these and other advanced functional programming patterns you should definitely read the red book that is Functional Programming in Scala—Paul Chiusano and Rúnar Bjarnason.
Oh, and remember: