Scala With Cats
Scala With Cats
Scala With Cats
July 2020
Preface 1
Versions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Template Projects . . . . . . . . . . . . . . . . . . . . . . . 2
Typographical Conventions . . . . . . . . . . . . . . . . . . 3
Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Callout Boxes . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . 4
Backers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
I Theory 7
1 Introduction 9
iii
1.2.1 Packaging Implicits . . . . . . . . . . . . . . . . . . . 14
1.5 Example: Eq . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.6.1 Variance . . . . . . . . . . . . . . . . . . . . . . . . 30
1.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3 Functors 47
3.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4 Monads 75
4.4 Either . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
The aims of this book are two‐fold: to introduce monads, functors, and other
functional programming patterns as a way to structure program design, and to
explain how these concepts are implemented in Cats.
This generality means they can be difficult to understand. Everyone finds ab‐
straction difficult. However, it is generality that allows concepts like monads
to be applied in such a wide variety of situations.
In this book we aim to show the concepts in a number of different ways, to help
you build a mental model of how they work and where they are appropriate.
We have extended case studies, a simple graphical notation, many smaller ex‐
amples, and of course the mathematical definitions. Between them we hope
you’ll find something that works for you.
1
2
Versions
This book is written for Scala 2.13.1 and Cats 2.1.0. Here is a minimal
build.sbt containing the relevant dependencies and settings¹:
scalaVersion := "2.13.1"
libraryDependencies +=
"org.typelevel" %% "cats-core" % "2.1.0"
Template Projects
This will generate a sandbox project with Cats as a dependency. See the gen‐
erated README.md for instructions on how to run the sample code and/or start
an interactive Scala console.
This will generate a project with a suite of library dependencies and compiler
plugins, together with templates for unit tests and documentation. See the
project pages for catalysts and sbt‐catalysts for more information.
This book contains a lot of technical information and program code. We use
the following typographical conventions to reduce ambiguity and highlight im‐
portant concepts:
Typographical Conventions
New terms and phrases are introduced in italics. After their initial introduction
they are written in normal roman font.
Terms from program code, filenames, and file contents, are written in
monospace font. Note that we do not distinguish between singular and
plural forms. For example, we might write String or Strings to refer to
java.lang.String.
Source Code
Most code passes through mdoc to ensure it compiles. mdoc uses the Scala
console behind the scenes, so we sometimes show console‐style output as
comments:
"Hello Cats!".toUpperCase
// res0: String = "HELLO CATS!"
4
Callout Boxes
Acknowledgements
We’d like to thank our colleagues at Inner Product and Underscore, our friends
at Typelevel, and everyone who helped contribute to this book. Special thanks
to Jenny Clements for her fantastic artwork and Richard Dallaway for his proof
reading expertise. Here is an alphabetical list of contributors:
Alessandro Marrella, Cody Koeninger, Connie Chen, Conor Fennell, Dani Rey,
Daniela Sfregola, Danielle Ashley, David Castillo, David Piggott, Denis Zjukow,
Dennis Hunziker, Deokhwan Kim, Edd Steel, Evgeny Veretennikov, Francis
Devereux, Ghislain Vaillant, Gregor Ihmor, Henk‐Jan Meijer, Janne Pelkonen,
Jason Scott, Javier Arrieta, Jenny Clements, Jérémie Jost, Joachim Hofer,
Jonathon Ferguson, Lance Paine, Leif Wickland, ltbs, Marc Prud’hommeaux,
Martin Carolan, mizuno, Mr‐SD, Narayan Iyer, Niccolo’ Paravanti, niqdev, Noor
Nashid, Pablo Francisco Pérez Hidalgo, Pawel Jurczenko, Phil Derome, Philip
Schwarz, Riccardo Sirigu, Richard Dallaway, Robert Stoll, Rodney Jacobsen,
Rodrigo B. de Oliveira, Rud Wangrungarun, Seoh Char, Sergio Magnacco, Tim
McIver, Toby Weston, Victor Osolovskiy, and Yinka Erinle.
Backers
We’d also like to extend very special thanks to our backers—fine people who
helped fund the development of the book by buying a copy before we released
it as open source. This book wouldn’t exist without you:
Theory
7
Chapter 1
Introduction
Cats contains a wide variety of functional programming tools and allows de‐
velopers to pick and choose the ones we want to use. The majority of these
tools are delivered in the form of type classes that we can apply to existing
Scala types.
In this chapter we will refresh our memory of type classes from Underscore’s
Essential Scala book, and take a first look at the Cats codebase. We will look
at two example type classes—Show and Eq—using them to identify patterns
that lay the foundations for the rest of the book.
We’ll finish by tying type classes back into algebraic data types, pattern match‐
ing, value classes, and type aliases, presenting a structured approach to func‐
tional programming in Scala.
¹The word “class” doesn’t strictly mean class in the Scala or Java sense.
9
10 CHAPTER 1. INTRODUCTION
There are three important components to the type class pattern: the type class
itself, instances for particular types, and the methods that use type classes.
Type classes in Scala are implemented using implicit values and parameters, and
optionally using implicit classes. Scala language constructs correspond to the
components of type classes as follows:
JsonWriter is our type class in this example, with Json and its subtypes
providing supporting code. When we come to implement instances of
1.1. ANATOMY OF A TYPE CLASS 11
JsonWriter, the type parameter A will be the concrete type of data we are
writing.
The instances of a type class provide implementations of the type class for
specific types we care about, which can include types from the Scala standard
library and types from our domain model.
object JsonWriterInstances {
implicit val stringWriter: JsonWriter[String] =
new JsonWriter[String] {
def write(value: String): Json =
JsString(value)
}
// etc...
}
A type class use is any functionality that requires a type class instance to work.
In Scala this means any method that accepts instances of the type class as
12 CHAPTER 1. INTRODUCTION
implicit parameters.
Cats provides utilities that make type classes easier to use, and you will some‐
times seem these patterns in other libraries. There are two ways it does this:
Interface Objects and Interface Syntax.
Interface Objects
The simplest way of creating an interface that uses a type class is to place
methods in a singleton object:
object Json {
def toJson[A](value: A)(implicit w: JsonWriter[A]): Json =
w.write(value)
}
To use this object, we import any type class instances we care about and call
the relevant method:
import JsonWriterInstances._
Json.toJson(Person("Dave", "dave@example.com"))
// res1: Json = JsObject(
// Map("name" -> JsString("Dave"), "email" -> JsString("dave@example
.com"))
// )
The compiler spots that we’ve called the toJson method without providing
the implicit parameters. It tries to fix this by searching for type class instances
of the relevant types and inserting them at the call site:
Json.toJson(Person("Dave", "dave@example.com"))(personWriter)
Interface Syntax
We can alternatively use extension methods to extend existing types with in‐
terface methods². Cats refers to this as “syntax” for the type class:
²You may occasionally see extension methods referred to as “type enrichment” or “pimping”.
These are older terms that we don’t use anymore.
1.1. ANATOMY OF A TYPE CLASS 13
object JsonSyntax {
implicit class JsonWriterOps[A](value: A) {
def toJson(implicit w: JsonWriter[A]): Json =
w.write(value)
}
}
We use interface syntax by importing it alongside the instances for the types
we need:
import JsonWriterInstances._
import JsonSyntax._
Person("Dave", "dave@example.com").toJson
// res3: Json = JsObject(
// Map("name" -> JsString("Dave"), "email" -> JsString("dave@example
.com"))
// )
Again, the compiler searches for candidates for the implicit parameters and
fills them in for us:
Person("Dave", "dave@example.com").toJson(personWriter)
The Scala standard library provides a generic type class interface called
implicitly. Its definition is very simple:
We can use implicitly to summon any value from implicit scope. We pro‐
vide the type we want and implicitly does the rest:
import JsonWriterInstances._
implicitly[JsonWriter[String]]
// res5: JsonWriter[String] = repl.
14 CHAPTER 1. INTRODUCTION
Session$App0$JsonWriterInstances$$anon$1@6fccdc48
Most type classes in Cats provide other means to summon instances. How‐
ever, implicitly is a good fallback for debugging purposes. We can insert a
call to implicitly within the general flow of our code to ensure the compiler
can find an instance of a type class and ensure that there are no ambiguous
implicit errors.
Working with type classes in Scala means working with implicit values and im‐
plicit parameters. There are a few rules we need to know to do this effectively.
As we saw above, the compiler searches for candidate type class instances by
type. For example, in the following expression it will look for an instance of
type JsonWriter[String]:
Json.toJson("A string!")
The places where the compiler searches for candidate instances is known as
the implicit scope. The implicit scope applies at the call site; that is the point
1.2. WORKING WITH IMPLICITS 15
where we call a method with an implicit parameter. The implicit scope which
roughly consists of:
• imported definitions;
Definitions are only included in implicit scope if they are tagged with the
implicit keyword. Furthermore, if the compiler sees multiple candidate def‐
initions, it fails with an ambiguous implicit values error:
Json.toJson("A string")
// error: ambiguous implicit values:
// both value writer1 in object App0 of type => repl.Session.App0.
JsonWriter[String]
// and value writer2 in object App0 of type => repl.Session.App0.
JsonWriter[String]
// match expected type repl.Session.App0.JsonWriter[String]
// Json.toJson("A string")
// ^^^^^^^^^^^^^^^^^^^^^^^
The precise rules of implicit resolution are more complex than this, but the
complexity is largely irrelevant for day‐to‐day use³. For our purposes, we can
package type class instances in roughly four ways:
³If you’re interested in the finer rules of implicit resolution in Scala, start by taking a look at
this Stack Overflow post on implicit scope and this blog post on implicit priority.
16 CHAPTER 1. INTRODUCTION
With option 1 we bring instances into scope by importing them. With option
2 we bring them into scope with inheritance. With options 3 and 4 instances
are always in implicit scope, regardless of where we try to use them.
The power of type classes and implicits lies in the compiler’s ability to combine
implicit definitions when searching for candidate instances. This is sometimes
known as type class composition.
Earlier we insinuated that all type class instances are implicit vals. This
was a simplification. We can actually define instances in two ways:
⁴We can also use an implicit object, which provides the same thing as an implicit
val.
1.2. WORKING WITH IMPLICITS 17
// and so on...
Fortunately, we can abstract the code for handling Option[A] into a common
constructor based on the instance for A:
Json.toJson(Option("A string"))
Json.toJson(Option("A string"))(optionWriter[String])
Json.toJson(Option("A string"))(optionWriter(stringWriter))
In this way, implicit resolution becomes a search through the space of possible
combinations of implicit definitions, to find a combination that creates a type
class instance of the correct overall type.
Implicit Conversions
The code above forms a general purpose printing library that we can use in
multiple applications. Let’s define an “application” now that uses the library.
First we’ll define a data type to represent a well‐known type of furry animal:
Next we’ll create an implementation of Printable for Cat that returns con‐
tent in the following format:
Finally, use the type class on the console or in a short demo app: create a Cat
and print it to the console:
// Define a cat:
val cat = Cat(/* ... */)
Better Syntax
Let’s make our printing library easier to use by defining some extension meth‐
ods to provide better syntax:
4. Use the extension methods to print the example Cat you created in the
previous exercise.
In the previous section we saw how to implement type classes in Scala. In this
section we will look at how type classes are implemented in Cats.
Cats is written using a modular structure that allows us to choose which type
classes, instances, and interface methods we want to use. Let’s take a first
look using cats.Show as an example.
Show is Cats’ equivalent of the Printable type class we defined in the last
section. It provides a mechanism for producing developer‐friendly console
output without using toString. Here’s an abbreviated definition:
package cats
trait Show[A] {
def show(value: A): String
}
The type classes in Cats are defined in the cats package. We can import Show
directly from this package:
import cats.Show
The companion object of every Cats type class has an apply method that
locates an instance for any type we specify:
22 CHAPTER 1. INTRODUCTION
Oops—that didn’t work! The apply method uses implicits to look up individual
instances, so we’ll have to bring some instances into scope.
That’s better! We now have access to two instances of Show, and can use
them to print Ints and Strings:
1.4. MEET CATS 23
We can make Show easier to use by importing the interface syntax from
cats.syntax.show. This adds an extension method called show to any type
for which we have an instance of Show in scope:
Cats provides separate syntax imports for each type class. We will introduce
these as we encounter them in later sections and chapters.
In this book we will use specific imports to show you exactly which instances
and syntax you need in each example. However, this is doesn’t add value in
production code. It is simpler and faster to use the following imports:
We can define an instance of Show simply by implementing the trait for a given
type:
import java.util.Date
new Date().show
// res1: String = "1594650192117ms since the epoch."
object Show {
// Convert a function to a `Show` instance:
def show[A](f: A => String): Show[A] =
???
These allow us to quickly construct instances with less ceremony than defining
them from scratch:
As you can see, the code using construction methods is much terser than the
code without. Many type classes in Cats provide helper methods like these
for constructing instances, either from scratch or by transforming existing in‐
stances for other types.
1.5. EXAMPLE: EQ 25
Re‐implement the Cat application from the previous section using Show in‐
stead of Printable.
1.5 Example: Eq
We will finish off this chapter by looking at another useful type class: cats.Eq.
Eq is designed to support type‐safe equality and address annoyances using
Scala’s built‐in == operator.
Almost every Scala developer has written code like this before:
Ok, many of you won’t have made such a simple mistake as this, but the prin‐
ciple is sound. The predicate in the filter clause always returns false be‐
cause it is comparing an Int to an Option[Int].
package cats
trait Eq[A] {
def eqv(a: A, b: A): Boolean
// other concrete methods based on eqv...
}
import cats.Eq
eqInt.eqv(123, 123)
// res1: Boolean = true
eqInt.eqv(123, 234)
// res2: Boolean = false
eqInt.eqv(123, "234")
// error: type mismatch;
// found : String("234")
// required: Int
We can also import the interface syntax in cats.syntax.eq to use the ===
and =!= methods:
We have received an error here because the types don’t quite match up. We
have Eq instances in scope for Int and Option[Int] but the values we are
comparing are of type Some[Int]. To fix the issue we have to re‐type the
arguments as Option[Int]:
We can define our own instances of Eq using the Eq.instance method, which
accepts a function of type (A, A) => Boolean and returns an Eq[A]:
import java.util.Date
import cats.instances.long._ // for Eq
x === x
// res12: Boolean = true
x === y
// res13: Boolean = false
Use this to compare the following pairs of objects for equality and inequality:
When working with type classes we must consider two issues that control
instance selection:
• How do we choose between type class instances when there are many
available?
What if we define two JsonWriters for Person? When we write
Json.toJson(aPerson), which instance is selected?
1.6.1 Variance
When we define type classes we can add variance annotations to the type
parameter to affect the variance of the type class and the compiler’s ability to
select instances during implicit resolution.
Co‐ and contravariance annotations arise when working with type construc‐
tors. For example, we denote covariance with a + symbol:
Covariance
Covariance means that the type F[B] is a subtype of the type F[A] if B is a
subtype of A. This is useful for modelling many types, including collections like
List and Option:
trait List[+A]
trait Option[+A]
Generally speaking, covariance is used for outputs: data that we can later get
out of a container type such as List, or otherwise returned by some method.
Contravariance
trait F[-A]
trait JsonWriter[-A] {
def write(value: A): Json
}
Let’s unpack this a bit further. Remember that variance is all about the ability
to substitute one value for another. Consider a scenario where we have two
values, one of type Shape and one of type Circle, and two JsonWriters,
one for Shape and one for Circle:
Now ask yourself the question: “Which combinations of value and writer can
I pass to format?” We can write a Circle with either writer because all
32 CHAPTER 1. INTRODUCTION
Invariance
Invariance is the easiest situation to describe. It’s what we get when we don’t
write a + or - in a type constructor:
trait F[A]
This means the types F[A] and F[B] are never subtypes of one another, no
matter what the relationship between A and B. This is the default semantics
for Scala type constructors.
When the compiler searches for an implicit it looks for one matching the type
or subtype. Thus we can use variance annotations to control type class in‐
stance selection to some extent.
There are two issues that tend to arise. Let’s imagine we have an algebraic
data type like:
sealed trait A
final case object B extends A
final case object C extends A
It turns out we can’t have both at once. The three choices give us behaviour
as follows:
It’s clear there is no perfect system. Cats prefers to use invariant type classes.
This allows us to specify more specific instances for subtypes if we want. It
does mean that if we have, for example, a value of type Some[Int], our type
class instance for Option will not be used. We can solve this problem with a
type annotation like Some(1) : Option[Int] or by using “smart construc‐
tors” like the Option.apply, Option.empty, some, and none methods we
saw in Section 1.5.3.
1.7 Summary
In this chapter we took a first look at type classes. We implemented our own
Printable type class using plain Scala before looking at two examples from
Cats—Show and Eq.
• The type classes themselves are generic traits in the cats package.
• Each type class has a companion object with, an apply method for ma‐
terializing instances, one or more construction methods for creating in‐
stances, and a collection of other relevant helper methods.
34 CHAPTER 1. INTRODUCTION
• Many type classes have syntax provided via the cats.syntax package.
In the remaining chapters of Part I we will look at several broad and pow‐
erful type classes—Semigroup, Monoid, Functor, Monad, Semigroupal,
Applicative, Traverse, and more. In each case we will learn what func‐
tionality the type class provides, the formal rules it follows, and how it is im‐
plemented in Cats. Many of these type classes are more abstract than Show
or Eq. While this makes them harder to learn, it makes them far more useful
for solving general problems in our code.
Chapter 2
In this section we explore our first type classes, monoid and semigroup. These
allow us to add or combine values. There are instances for Ints, Strings,
Lists, Options, and many more. Let’s start by looking at a few simple types
and operations to see what common principles we can extract.
Integer addition
Addition of Ints is a binary operation that is closed, meaning that adding two
Ints always produces another Int:
2 + 1
// res0: Int = 3
2 + 0
// res1: Int = 2
0 + 2
// res2: Int = 2
There are also other properties of addition. For instance, it doesn’t matter in
35
36 CHAPTER 2. MONOIDS AND SEMIGROUPS
what order we add elements because we always get the same result. This is a
property known as associativity:
(1 + 2) + 3
// res3: Int = 6
1 + (2 + 3)
// res4: Int = 6
Integer multiplication
The same properties for addition also apply for multiplication, provided we
use 1 as the identity instead of 0:
1 * 3
// res5: Int = 3
3 * 1
// res6: Int = 3
(1 * 2) * 3
// res7: Int = 6
1 * (2 * 3)
// res8: Int = 6
We can also add Strings, using string concatenation as our binary operator:
"One" ++ "two"
// res9: String = "Onetwo"
"" ++ "Hello"
// res10: String = "Hello"
"Hello" ++ ""
// res11: String = "Hello"
Note that we used ++ above instead of the more usual + to suggest a parallel
with sequences. We can do the same with other types of sequence, using
concatenation as the binary operator and the empty sequence as our identity.
This definition translates nicely into Scala code. Here is a simplified version of
the definition from Cats:
trait Monoid[A] {
def combine(x: A, y: A): A
def empty: A
}
def associativeLaw[A](x: A, y: A, z: A)
(implicit m: Monoid[A]): Boolean = {
m.combine(x, m.combine(y, z)) ==
m.combine(m.combine(x, y), z)
}
def identityLaw[A](x: A)
(implicit m: Monoid[A]): Boolean = {
(m.combine(x, m.empty) == x) &&
(m.combine(m.empty, x) == x)
}
(1 - 2) - 3
// res14: Int = -4
1 - (2 - 3)
// res15: Int = 2
In practice we only need to think about laws when we are writing our own
Monoid instances. Unlawful instances are dangerous because they can yield
unpredictable results when used with the rest of Cats’ machinery. Most of
the time we can rely on the instances provided by Cats and assume the library
authors know what they’re doing.
A semigroup is just the combine part of a monoid, without the empty part.
While many semigroups are also monoids, there are some data types for which
we cannot define an empty element. For example, we have just seen that
sequence concatenation and integer addition are monoids. However, if we
restrict ourselves to non‐empty sequences and positive integers, we are no
longer able to define a sensible empty element. Cats has a NonEmptyList
data type that has an implementation of Semigroup but no implementation
of Monoid.
2.3. EXERCISE: THE TRUTH ABOUT MONOIDS 39
trait Semigroup[A] {
def combine(x: A, y: A): A
}
We’ll see this kind of inheritance often when discussing type classes. It pro‐
vides modularity and allows us to re‐use behaviour. If we define a Monoid
for a type A, we get a Semigroup for free. Similarly, if a method requires a
parameter of type Semigroup[B], we can pass a Monoid[B] instead.
We’ve seen a few examples of monoids but there are plenty more to be found.
Consider Boolean. How many monoids can you define for this type? For each
monoid, define the combine and empty operations and convince yourself that
the monoid laws hold. Use the following definitions as a starting point:
trait Semigroup[A] {
def combine(x: A, y: A): A
}
object Monoid {
def apply[A](implicit monoid: Monoid[A]) =
monoid
}
Now we’ve seen what monoids are, let’s look at their implementation in Cats.
Once again we’ll look at the three main aspects of the implementation: the
type class, the instances, and the interface.
import cats.Monoid
import cats.Semigroup
Cats Kernel?
The Cats Kernel type classes covered in this book are Eq, Semigroup,
and Monoid. All the other type classes we cover are part of the main
Cats project and are defined directly in the cats package.
2.5. MONOIDS IN CATS 41
Monoid follows the standard Cats pattern for the user interface: the compan‐
ion object has an apply method that returns the type class instance for a
particular type. For example, if we want the monoid instance for String, and
we have the correct implicits in scope, we can write the following:
import cats.Monoid
import cats.instances.string._ // for Monoid
import cats.Semigroup
The type class instances for Monoid are organised under cats.instances in
the standard way described in Chapter 1.4.2. For example, if we want to pull
in instances for Int we import from cats.instances.int:
import cats.Monoid
import cats.instances.int._ // for Monoid
Monoid[Int].combine(32, 10)
42 CHAPTER 2. MONOIDS AND SEMIGROUPS
// res5: Int = 42
import cats.Monoid
import cats.instances.int._ // for Monoid
import cats.instances.option._ // for Monoid
val a = Option(22)
// a: Option[Int] = Some(22)
val b = Option(20)
// b: Option[Int] = Some(20)
Monoid[Option[Int]].combine(a, b)
// res6: Option[Int] = Some(42)
import cats._
import cats.implicits._
Cats provides syntax for the combine method in the form of the |+| operator.
Because combine technically comes from Semigroup, we access the syntax
by importing from cats.syntax.semigroup:
The cutting edge SuperAdder v3.5a‐32 is the world’s first choice for adding
together numbers. The main function in the program has signature def
add(items: List[Int]): Int. In a tragic accident this code is deleted!
Rewrite the method and save the day!
SuperAdder is entering the POS (point‐of‐sale, not the other POS) market.
Now we want to add up Orders:
We need to release this code really soon so we can’t make any modifications
to add. Make it so!
In big data applications like Spark and Hadoop we distribute data analysis over
many machines, giving fault tolerance and scalability. This means each ma‐
chine will return results over a portion of the data, and we must then combine
these results to get our final result. In the vast majority of cases this can be
viewed as a monoid.
If we want to calculate how many total visitors a web site has received, that
means calculating an Int on each portion of the data. We know the monoid
instance of Int is addition, which is the right way to combine partial results.
If we want to find out how many unique visitors a website has received, that’s
equivalent to building a Set[User] on each portion of the data. We know the
monoid instance for Set is the set union, which is the right way to combine
partial results.
If we want to calculate 99% and 95% response times from our server logs, we
can use a data structure called a QTree for which there is a monoid.
Hopefully you get the idea. Almost every analysis that we might want to do
over a large data set is a monoid, and therefore we can build an expressive
and powerful analytics system around this idea. This is exactly what Twitter’s
Algebird and Summingbird projects have done. We explore this idea further
in the map‐reduce case study in Section 9.
A particular class of data types support this reconciliation. These data types
are called commutative replicated data types (CRDTs). The key operation is
the ability to merge two data instances, with a result that captures all the in‐
formation in both instances. This operation relies on having a monoid instance.
We explore this idea further in the CRDT case study.
2.7. SUMMARY 45
The two examples above are cases where monoids inform the entire system
architecture. There are also many cases where having a monoid around makes
it easier to write a small code fragment. We’ll see lots of examples in the case
studies in this book.
2.7 Summary
We hit a big milestone in this chapter—we covered our first type classes with
fancy functional programming names:
We can use Semigroups and Monoids by importing three things: the type
classes themselves, the instances for the types we care about, and the semi‐
group syntax to give us the |+| operator:
import cats.Monoid
import cats.instances.string._ // for Monoid
import cats.syntax.semigroup._ // for |+|
With the correct instances in scope, we can set about adding anything we
want:
We can also write generic code that works with any type for which we have
an instance of Monoid:
addAll(List(1, 2, 3))
// res4: Int = 6
addAll(List(None, Some(1), Some(2)))
// res5: Option[Int] = Some(3)
Monoids are a great gateway to Cats. They’re easy to understand and simple
to use. However, they’re just the tip of the iceberg in terms of the abstractions
Cats enables us to make. In the next chapter we’ll look at functors, the type
class personification of the beloved map method. That’s where the fun really
begins!
Chapter 3
Functors
Informally, a functor is anything with a map method. You probably know lots
of types that have this: Option, List, and Either, to name a few.
We typically first encounter map when iterating over Lists. However, to un‐
derstand functors we need to think of the method in another way. Rather than
traversing the list, we should think of it as transforming all of the values inside
in one go. We specify the function to apply, and map ensures it is applied to
every item. The values change but the structure of the list (the number of
elements and their order) remains the same:
47
48 CHAPTER 3. FUNCTORS
map
map
map
Figure 3.1: Type chart: mapping over List, Option, and Either
Similarly, when we map over an Option, we transform the contents but leave
the Some or None context unchanged. The same principle applies to Either
with its Left and Right contexts. This general notion of transformation, along
with the common pattern of type signatures shown in Figure 3.1, is what con‐
nects the behaviour of map across different data types.
Because map leaves the structure of the context unchanged, we can call it
repeatedly to sequence multiple computations on the contents of an initial
data structure:
List(1, 2, 3).
map(n => n + 1).
map(n => n * 2).
map(n => s"${n}!")
// res1: List[String] = List("4!", "6!", "8!")
map
The map methods of List, Option, and Either apply functions eagerly. How‐
ever, the idea of sequencing computations is more general than this. Let’s
investigate the behaviour of some other functors that apply the pattern in
different ways.
Futures
When we work with a Future we have no guarantees about its internal state.
The wrapped computation may be ongoing, complete, or rejected. If the
Future is complete, our mapping function can be called immediately. If not,
some underlying thread pool queues the function call and comes back to it
later. We don’t know when our functions will be called, but we do know what
order they will be called in. In this way, Future provides the same sequencing
behaviour seen in List, Option, and Either:
50 CHAPTER 3. FUNCTORS
Await.result(future, 1.second)
// res2: String = "248!"
Note that Scala’s Futures aren’t a great example of pure functional pro‐
gramming because they aren’t referentially transparent. Future always
computes and caches a result and there’s no way for us to tweak this
behaviour. This means we can get unpredictable results when we use
Future to wrap side‐effecting computations. For example:
3.2. MORE EXAMPLES OF FUNCTORS 51
import scala.util.Random
val future1 = {
// Initialize Random with a fixed seed:
val r = new Random(0L)
for {
a <- x
b <- x
} yield (a, b)
}
val future2 = {
val r = new Random(0L)
for {
a <- Future(r.nextInt)
b <- Future(r.nextInt)
} yield (a, b)
}
Ideally we would like result1 and result2 to contain the same value.
However, the computation for future1 calls nextInt once and the
computation for future2 calls it twice. Because nextInt returns a dif‐
ferent result every time we get a different result in each case.
map
Rob Norris.
When we look at Cats Effect we’ll see that the IO type solves these
problems.
Functions (?!)
It turns out that single argument functions are also functors. To see this we
have to tweak the types a little. A function A => B has two type parameters:
the parameter type A and the result type B. To coerce them to the correct
shape we can fix the parameter type and let the result type vary:
val func =
((x: Int) => x.toDouble).
map(x => x + 1).
map(x => x * 2).
map(x => s"${x}!")
func(123)
// res6: String = "248.0!"
Partial Unification
scalacOptions += "-Ypartial-unification"
54 CHAPTER 3. FUNCTORS
map
func1.map(func2)
// <console>: error: value map is not a member of Int => Double
// func1.map(func2)
^
package cats
trait Functor[F[_]] {
def map[A, B](fa: F[A])(f: A => B): F[B]
}
If you haven’t seen syntax like F[_] before, it’s time to take a brief detour to
discuss type constructors and higher kinded types.
3.4. ASIDE: HIGHER KINDS AND TYPE CONSTRUCTORS 55
Functor Laws
Identity: calling map with the identity function is the same as doing noth‐
ing:
fa.map(a => a) == fa
fa.map(g(f(_))) == fa.map(f).map(g)
Kinds are like types for types. They describe the number of “holes” in a type.
We distinguish between regular types that have no holes and “type construc‐
tors” that have holes we can fill to produce types.
For example, List is a type constructor with one hole. We fill that hole by
specifying a parameter to produce a regular type like List[Int] or List[A].
The trick is not to confuse type constructors with generic types. List is a type
constructor, List[A] is a type:
There’s a close analogy here with functions and values. Functions are “value
constructors”—they produce values when we supply parameters:
// ...
}
Armed with this knowledge of type constructors, we can see that the Cats def‐
inition of Functor allows us to create instances for any single‐parameter type
constructor, such as List, Option, Future, or a type alias such as MyFunc.
import scala.language.higherKinds
scalacOptions += "-language:higherKinds"
3.5. FUNCTORS IN CATS 57
Let’s look at the implementation of functors in Cats. We’ll examine the same
aspects we did for monoids: the type class, the instances, and the syntax.
The functor type class is cats.Functor. We obtain instances using the stan‐
dard Functor.apply method on the companion object. As usual, default in‐
stances are arranged by type in the cats.instances package:
import cats.Functor
import cats.instances.list._ // for Functor
import cats.instances.option._ // for Functor
liftedFunc(Option(1))
// res1: Option[Int] = Some(2)
The as method is the other method you are likely to use. It replaces with value
inside the Functor with the given value.
Functor[List].as(list1, "As")
// res2: List[String] = List("As", "As", "As")
The main method provided by the syntax for Functor is map. It’s difficult to
demonstrate this with Options and Lists as they have their own built‐in map
methods and the Scala compiler will always prefer a built‐in method over an
extension method. We’ll work around this with two examples.
First let’s look at mapping over functions. Scala’s Function1 type doesn’t
have a map method (it’s called andThen instead) so there are no naming con‐
flicts:
func4(123)
// res3: String = "248!"
Let’s look at another example. This time we’ll abstract over functors so we’re
not working with any particular concrete type. We can write a method that
applies an equation to a number no matter what functor context it’s in:
3.5. FUNCTORS IN CATS 59
doMath(Option(20))
// res4: Option[Int] = Some(22)
doMath(List(1, 2, 3))
// res5: List[Int] = List(3, 4, 5)
To illustrate how this works, let’s take a look at the definition of the map
method in cats.syntax.functor. Here’s a simplified version of the code:
The compiler can use this extension method to insert a map method wherever
no built‐in map is available:
Assuming foo has no built‐in map method, the compiler detects the potential
error and wraps the expression in a FunctorOps to fix the code:
List(1, 2, 3).as("As")
// res7: List[String] = List("As", "As", "As")
We can define a functor simply by defining its map method. Here’s an ex‐
ample of a Functor for Option, even though such a thing already exists in
cats.instances. The implementation is trivial—we simply call Option's
map method:
value.map(func)
}
// We write this:
Functor[Future]
Write a Functor for the following binary tree data type. Verify that the code
works as expected on instances of Branch and Leaf:
contramap
The first of our type classes, the contravariant functor, provides an operation
called contramap that represents “prepending” an operation to a chain. The
general type signature is shown in Figure 3.5.
The contramap method only makes sense for data types that represent trans‐
formations. For example, we can’t define contramap for an Option because
there is no way of feeding a value in an Option[B] backwards through a func‐
tion A => B. However, we can define contramap for the Printable type
class we discussed in Chapter 1:
3.6. CONTRAVARIANT AND INVARIANT FUNCTORS 63
trait Printable[A] {
def format(value: A): String
}
trait Printable[A] {
def format(value: A): String
Implement the contramap method for Printable above. Start with the fol‐
lowing code template and replace the ??? with a working method body:
trait Printable[A] {
def format(value: A): String
If you get stuck, think about the types. You need to turn value, which is of
type B, into a String. What functions and methods do you have available and
in what order do they need to be combined?
For testing purposes, let’s define some instances of Printable for String
and Boolean:
format("hello")
// res2: String = "'hello'"
format(true)
// res3: String = "yes"
Now define an instance of Printable for the following Box case class. You’ll
need to write this as an implicit def as described in Section 1.2.3:
Rather than writing out the complete definition from scratch (new
Printable[Box] etc…), create your instance from an existing instance using
contramap.
format(Box("hello world"))
// res4: String = "'hello world'"
format(Box(true))
// res5: String = "yes"
If we don’t have a Printable for the type inside the Box, calls to format
should fail to compile:
3.6. CONTRAVARIANT AND INVARIANT FUNCTORS 65
format(Box(123))
// error: could not find implicit value for parameter p: repl.Session.
App1.Printable[repl.Session.App1.Box[Int]]
// def encode(value: B): String =
// ^
The most intuitive examples of this are a type class that represents encoding
and decoding as some data type, such as Play JSON’s Format and scodec’s
Codec. We can build our own Codec by enhancing Printable to support
encoding and decoding to/from a String:
trait Codec[A] {
def encode(value: A): String
def decode(value: String): A
def imap[B](dec: A => B, enc: B => A): Codec[B] = ???
}
The type chart for imap is shown in Figure 3.6. If we have a Codec[A] and a
pair of functions A => B and B => A, the imap method creates a Codec[B]:
imap
,
We can construct many useful Codecs for other types by building off of
stringCodec using imap:
Note that the decode method of our Codec type class doesn’t account
for failures. If we want to model more sophisticated relationships we
can move beyond functors to look at lenses and optics.
Optics are beyond the scope of this book. However, Julien Truffaut’s
library Monocle provides a great starting point for further investigation.
encode(123.4)
// res11: String = "123.4"
decode[Double]("123.4")
// res12: Double = 123.4
encode(Box(123.4))
// res13: String = "123.4"
decode[Box[Double]]("123.4")
// res14: Box[Double] = Box(123.4)
If you recall from Section 1.6.1, variance affects subtyping, which is es‐
sentially our ability to use a value of one type in place of a value of
another type without breaking the code.
convert to an F[B].
Finally, invariant functors capture the case where we can convert from
F[A] to F[B] via a function A => B and vice versa via a function B =>
A.
trait Contravariant[F[_]] {
def contramap[A, B](fa: F[A])(f: B => A): F[B]
}
trait Invariant[F[_]] {
def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B]
}
import cats.Contravariant
import cats.Show
import cats.instances.string._
showSymbol.show(Symbol("dave"))
3.7. CONTRAVARIANT AND INVARIANT IN CATS 69
showString
.contramap[Symbol](sym => s"'${sym.name}")
.show(Symbol("dave"))
// res2: String = "'dave"
Among other types, Cats provides an instance of Invariant for Monoid. This
is a little different from the Codec example we introduced in Section 3.6.2. If
you recall, this is what Monoid looks like:
package cats
trait Monoid[A] {
def empty: A
def combine(x: A, y: A): A
}
Imagine we want to produce a Monoid for Scala’s Symbol type. Cats doesn’t
provide a Monoid for Symbol but it does provide a Monoid for a similar type:
String. We can write our new semigroup with an empty method that relies
on the empty String, and a combine method that works as follows:
We can implement combine using imap, passing functions of type String =>
Symbol and Symbol => String as parameters. Here’ the code, written out
using the imap extension method provided by cats.syntax.invariant:
70 CHAPTER 3. FUNCTORS
import cats.Monoid
import cats.instances.string._ // for Monoid
import cats.syntax.invariant._ // for imap
import cats.syntax.semigroup._ // for |+|
Monoid[Symbol].empty
// res3: Symbol = '
import cats.Functor
import cats.instances.function._ // for Functor
import cats.syntax.functor._ // for map
Function1 has two type parameters (the function argument and the result
type):
trait Functor[F[_]] {
def map[A, B](fa: F[A])(func: A => B): F[B]
}
The compiler has to fix one of the two parameters of Function1 to create a
type constructor of the correct kind to pass to Functor. It has two options to
choose from:
We know that the former of these is the correct choice. However the compiler
doesn’t understand what the code means. Instead it relies on a simple rule,
implementing what is called “partial unification”.
The partial unification in the Scala compiler works by fixing type parameters
from left to right. In the above example, the compiler fixes the Int in Int =>
Double and looks for a Functor for functions of type Int => ?:
either.map(_ + 1)
// res0: Either[String, Int] = Right(124)
scalacOptions += "-Ypartial-unification"
72 CHAPTER 3. FUNCTORS
There are situations where left‐to‐right elimination is not the correct choice.
One example is the Or type in Scalactic, which is a conventionally left‐biased
equivalent of Either:
The problem here is that the Contravariant for Function1 fixes the return
type and leaves the parameter type varying, requiring the compiler to elimi‐
nate type parameters from right to left, as shown below and in Figure 3.7:
3.8. ASIDE: PARTIAL UNIFICATION 73
contramap
The compiler fails simply because of its left‐to‐right bias. We can prove this
by creating a type alias that flips the parameters on Function1:
3.9 Summary
• Regular covariant Functors, with their map method, represent the abil‐
ity to apply functions to a value in some context. Successive calls to
map apply these functions in sequence, each accepting the result of its
predecessor as a parameter.
Regular Functors are by far the most common of these type classes, but even
then it is rare to use them on their own. Functors form a foundational building
block of several more interesting abstractions that we use all the time. In
the following chapters we will look at two of these abstractions: monads and
applicative functors.
Functors for collections are extremely important, as they transform each el‐
ement independently of the rest. This allows us to parallelise or distribute
transformations on large collections, a technique leveraged heavily in “map‐
reduce” frameworks like Hadoop. We will investigate this approach in more
detail in the map‐reduce case study later in Section 9.
The Contravariant and Invariant type classes are less widely applicable
but are still useful for building data types that represent transformations. We
will revisit them to discuss the Semigroupal type class later in Chapter 6.
Chapter 4
Monads
Monads are one of the most common abstractions in Scala. Many Scala pro‐
grammers quickly become intuitively familiar with monads, even if we don’t
know them by name.
In this chapter we will take a deep dive into monads. We will start by moti‐
vating them with a few examples. We’ll proceed to their formal definition and
their implementation in Cats. Finally, we’ll tour some interesting monads that
you may not have seen, providing introductions and examples of their use.
This is the question that has been posed in a thousand blog posts, with ex‐
planations and analogies involving concepts as diverse as cats, Mexican food,
space suits full of toxic waste, and monoids in the category of endofunctors
75
76 CHAPTER 4. MONADS
(whatever that means). We’re going to solve the problem of explaining monads
once and for all by stating very simply:
That was easy! Problem solved, right? But then again, last chapter we said
functors were a control mechanism for exactly the same thing. Ok, maybe we
need some more discussion…
This is where monads come in. A monad’s flatMap method allows us to spec‐
ify what happens next, taking into account an intermediate complication. The
flatMap method of Option takes intermediate Options into account. The
flatMap method of List handles intermediate Lists. And so on. In each
case, the function passed to flatMap specifies the application‐specific part
of the computation, and flatMap itself takes care of the complication allow‐
ing us to flatMap again. Let’s ground things by looking at some examples.
Options
Option allows us to sequence computations that may or may not return val‐
ues. Here are some examples:
Each of these methods may “fail” by returning None. The flatMap method
allows us to ignore this when we sequence operations:
4.1. WHAT IS A MONAD? 77
flatMap
At each step, flatMap chooses whether to call our function, and our function
generates the next computation in the sequence. This is shown in Figure 4.1.
stringDivideBy("6", "2")
// res0: Option[Int] = Some(3)
stringDivideBy("6", "0")
// res1: Option[Int] = None
stringDivideBy("6", "foo")
78 CHAPTER 4. MONADS
Every monad is also a functor (see below for proof), so we can rely on both
flatMap and map to sequence computations that do and don’t introduce a
new monad. Plus, if we have both flatMap and map we can use for compre‐
hensions to clarify the sequencing behaviour:
Lists
for {
x <- (1 to 3).toList
y <- (4 to 5).toList
} yield (x, y)
// res5: List[(Int, Int)] = List(
// (1, 4),
// (1, 5),
// (2, 4),
// (2, 5),
// (3, 4),
// (3, 5)
// )
However, there is another mental model we can apply that highlights the
monadic behaviour of List. If we think of Lists as sets of intermediate re‐
sults, flatMap becomes a construct that calculates permutations and combi‐
nations.
4.1. WHAT IS A MONAD? 79
For example, in the for comprehension above there are three possible values
of x and two possible values of y. This means there are six possible values
of (x, y). flatMap is generating these combinations from our code, which
states the sequence of operations:
• get x
• get y
• create a tuple (x, y)
Futures
import scala.concurrent.Future
import scala.concurrent.ExecutionContext.Implicits.global
Again, we specify the code to run at each step, and flatMap takes care of all
the horrifying underlying complexities of thread pools and schedulers.
If you’ve made extensive use of Future, you’ll know that the code above is
running each operation in sequence. This becomes clearer if we expand out
the for comprehension to show the nested calls to flatMap:
flatMap
}
}
Each Future in our sequence is created by a function that receives the result
from a previous Future. In other words, each step in our computation can
only start once the previous step is finished. This is born out by the type chart
for flatMap in Figure 4.2, which shows the function parameter of type A =>
Future[B].
We can run futures in parallel, of course, but that is another story and shall be
told another time. Monads are all about sequencing.
While we have only talked about flatMap above, monadic behaviour is for‐
mally captured in two operations:
trait Monad[F[_]] {
def pure[A](value: A): F[A]
Monad Laws
pure and flatMap must obey a set of laws that allow us to sequence
operations freely without unintended glitches and side‐effects:
Left identity: calling pure and transforming the result with func is the
same as calling func:
pure(a).flatMap(func) == func(a)
m.flatMap(pure) == m
Every monad is also a functor. We can define map in the same way for every
monad using the existing methods, flatMap and pure:
trait Monad[F[_]] {
def pure[A](a: A): F[A]
82 CHAPTER 4. MONADS
It’s time to give monads our standard Cats treatment. As usual we’ll look at
the type class, instances, and syntax.
The monad type class is cats.Monad. Monad extends two other type classes:
FlatMap, which provides the flatMap method, and Applicative, which pro‐
vides pure. Applicative also extends Functor, which gives every Monad a
map method as we saw in the exercise above. We’ll discuss Applicatives in
Chapter 6.
Here are some examples using pure and flatMap, and map directly:
import cats.Monad
import cats.instances.option._ // for Monad
import cats.instances.list._ // for Monad
Monad provides many other methods, including all of the methods from
Functor. See the scaladoc for more information.
Cats provides instances for all the monads in the standard library (Option,
List, Vector and so on) via cats.instances:
Cats also provides a Monad for Future. Unlike the methods on the Future
class itself, the pure and flatMap methods on the monad can’t accept implicit
ExecutionContext parameters (because the parameters aren’t part of the
definitions in the Monad trait). To work around this, Cats requires us to have
an ExecutionContext in scope when we summon a Monad for Future:
val fm = Monad[Future]
// error: Could not find an instance of Monad for scala.concurrent.
Future
// val fm = Monad[Future]
// ^^^^^^^^^^^^^
Bringing the ExecutionContext into scope fixes the implicit resolution re‐
quired to summon the instance:
import scala.concurrent.ExecutionContext.Implicits.global
val fm = Monad[Future]
// fm: Monad[Future] = cats.instances.FutureInstances$$anon$1@7ba44cd6
Await.result(future, 1.second)
// res4: Int = 3
In addition to the above, Cats provides a host of new monads that we don’t
have in the standard library. We’ll familiarise ourselves with some of these in
a moment.
We can use pure to construct instances of a monad. We’ll often need to spec‐
ify the type parameter to disambiguate the particular instance we want.
1.pure[Option]
// res5: Option[Int] = Some(1)
1.pure[List]
// res6: List[Int] = List(1)
It’s difficult to demonstrate the flatMap and map methods directly on Scala
monads like Option and List, because they define their own explicit versions
of those methods. Instead we’ll write a generic function that performs a cal‐
culation on parameters that come wrapped in a monad of the user’s choice:
import cats.Monad
import cats.syntax.functor._ // for map
import cats.syntax.flatMap._ // for flatMap
sumSquare(Option(3), Option(4))
// res7: Option[Int] = Some(25)
sumSquare(List(1, 2, 3), List(4, 5))
// res8: List[Int] = List(17, 26, 20, 29, 25, 34)
We can rewrite this code using for comprehensions. The compiler will “do the
right thing” by rewriting our comprehension in terms of flatMap and map and
inserting the correct implicit conversions to use our Monad:
y <- b
} yield x*x + y*y
sumSquare(Option(3), Option(4))
// res10: Option[Int] = Some(25)
sumSquare(List(1, 2, 3), List(4, 5))
// res11: List[Int] = List(17, 26, 20, 29, 25, 34)
That’s more or less everything we need to know about the generalities of mon‐
ads in Cats. Now let’s take a look at some useful monad instances that we
haven’t seen in the Scala standard library.
import cats.Monad
import cats.syntax.functor._ // for map
import cats.syntax.flatMap._ // for flatMap
This method works well on Options and Lists but we can’t call it passing in
plain values:
sumSquare(3, 4)
// error: no type parameters for method sumSquare: (a: F[Int], b: F[
Int])(implicit evidence$1: cats.Monad[F])F[Int] exist so that it
can be applied to arguments (Int, Int)
// --- because ---
// argument expression's type is not compatible with formal parameter
type;
// found : 3
4.3. THE IDENTITY MONAD 87
// required: ?F[Int]
// error: type mismatch;
// found : Int(3)
// required: F[Int]
// error: type mismatch;
// found : Int(4)
// required: F[Int]
import cats.Id
Id allows us to call our monadic method using plain values. However, the
exact semantics are difficult to understand. We cast the parameters to
sumSquare as Id[Int] and received an Id[Int] back as a result!
package cats
type Id[A] = A
"Dave" : Id[String]
// res2: Id[String] = "Dave"
123 : Id[Int]
// res3: Id[Int] = 123
List(1, 2, 3) : Id[List[Int]]
// res4: Id[List[Int]] = List(1, 2, 3)
Cats provides instances of various type classes for Id, including Functor and
Monad. These let us call map, flatMap, and pure passing in plain values:
88 CHAPTER 4. MONADS
val a = Monad[Id].pure(3)
// a: Id[Int] = 3
val b = Monad[Id].flatMap(a)(_ + 1)
// b: Id[Int] = 4
for {
x <- a
y <- b
} yield x + y
// res5: Id[Int] = 7
The ability to abstract over monadic and non‐monadic code is extremely pow‐
erful. For example, we can run code asynchronously in production using
Future and synchronously in test using Id. We’ll see this in our first case
study in Chapter 8.
Implement pure, map, and flatMap for Id! What interesting discoveries do
you uncover about the implementation?
4.4 Either
Let’s look at another useful monad: the Either type from the Scala standard
library. In Scala 2.11 and earlier, many people didn’t consider Either a monad
because it didn’t have map and flatMap methods. In Scala 2.12, however,
Either became right biased.
In Scala 2.11, Either had no default map or flatMap method. This made the
Scala 2.11 version of Either inconvenient to use in for comprehensions. We
4.4. EITHER 89
for {
a <- either1.right
b <- either2.right
} yield a + b
In Scala 2.12, Either was redesigned. The modern Either makes the deci‐
sion that the right side represents the success case and thus supports map and
flatMap directly. This makes for comprehensions much more pleasant:
for {
a <- either1
b <- either2
} yield a + b
// res1: Either[String, Int] = Right(42)
for {
a <- either1
b <- either2
} yield a + b
val a = 3.asRight[String]
// a: Either[String, Int] = Right(3)
val b = 4.asRight[String]
// b: Either[String, Int] = Right(4)
for {
x <- a
y <- b
} yield x*x + y*y
// res3: Either[String, Int] = Right(25)
countPositive(List(1, 2, 3))
// res5: Either[String, Int] = Right(3)
countPositive(List(1, -2, 3))
// res6: Either[String, Int] = Left("Negative. Stopping!")
Either.catchOnly[NumberFormatException]("foo".toInt)
// res7: Either[NumberFormatException, Int] = Left(
// java.lang.NumberFormatException: For input string: "foo"
// )
Either.catchNonFatal(sys.error("Badness"))
// res8: Either[Throwable, Nothing] = Left(java.lang.RuntimeException:
Badness)
There are also methods for creating an Either from other data types:
Either.fromTry(scala.util.Try("foo".toInt))
// res9: Either[Throwable, Int] = Left(
// java.lang.NumberFormatException: For input string: "foo"
// )
92 CHAPTER 4. MONADS
Users of Scala 2.11 or 2.12 can use orElse and getOrElse to extract values
from the right side or return a default:
import cats.syntax.either._
"Error".asLeft[Int].getOrElse(0)
// res11: Int = 0
"Error".asLeft[Int].orElse(2.asRight[String])
// res12: Either[String, Int] = Right(2)
The ensure method allows us to check whether the right‐hand value satisfies
a predicate:
"error".asLeft[Int].recover {
case _: String => -1
}
// res14: Either[String, Int] = Right(-1)
"error".asLeft[Int].recoverWith {
case _: String => Right(-1)
}
// res15: Either[String, Int] = Right(-1)
"foo".asLeft[Int].leftMap(_.reverse)
// res16: Either[String, Int] = Left("oof")
6.asRight[String].bimap(_.reverse, _ * 7)
// res17: Either[String, Int] = Right(42)
"bar".asLeft[Int].bimap(_.reverse, _ * 7)
// res18: Either[String, Int] = Left("rab")
123.asRight[String]
// res19: Either[String, Int] = Right(123)
123.asRight[String].swap
// res20: Either[Int, String] = Left(123)
for {
a <- 1.asRight[String]
b <- 0.asRight[String]
c <- if(b == 0) "DIV0".asLeft[Int]
else (a / b).asRight[String]
} yield c * 100
// res21: Either[String, Int] = Left("DIV0")
When using Either for error handling, we need to determine what type we
want to use to represent errors. We could use Throwable for this:
object wrapper {
sealed trait LoginError extends Product with Serializable
This approach solves the problems we saw with Throwable. It gives us a fixed
set of expected error types and a catch‐all for anything else that we didn’t ex‐
pect. We also get the safety of exhaustivity checking on any pattern matching
we do:
result1.fold(handleError, println)
// User(dave,passw0rd)
result2.fold(handleError, println)
// User not found: dave
Is the error handling strategy in the previous examples well suited for all pur‐
poses? What other features might we want from error handling?
Cats provides an additional type class called MonadError that abstracts over
Either‐like data types that are used for error handling. MonadError provides
extra operations for raising and handling errors.
You won’t need to use MonadError unless you need to abstract over
error handling monads. For example, you can use MonadError to ab‐
stract over Future and Try, or over Either and EitherT (which we
will meet in Chapter 5).
If you don’t need this kind of abstraction right now, feel free to skip
onwards to Section 4.6.
package cats
import cats.MonadError
import cats.instances.either._ // for MonadError
ApplicativeError
monadError.handleErrorWith(failure) {
case "Badness" =>
monadError.pure("It's ok")
case _ =>
monadError.raiseError("It's not ok")
}
// res0: ErrorOr[String] = Right("It's ok")
monadError.handleError(failure) {
case "Badness" => 42
case _ => -1
}
// res1: ErrorOr[Int] = Right(42)
case _ =>
("It's not ok").raiseError
}
// res4: ErrorOr[Int] = Right(256)
success.ensure("Number to low!")(_ > 1000)
// res5: ErrorOr[Int] = Left("Number to low!")
There are other useful variants of these methods. See the source of
cats.MonadError and cats.ApplicativeError for more information.
import scala.util.Try
import cats.instances.try_._ // for MonadError
exn.raiseError[Try, Int]
// res6: Try[Int] = Failure(java.lang.RuntimeException: It's all gone
wrong)
validateAdult[Try](18)
// res7: Try[Int] = Success(18)
validateAdult[Try](8)
// res8: Try[Int] = Failure(
// java.lang.IllegalArgumentException: Age must be greater than or
equal to 18
// )
type ExceptionOr[A] = Either[Throwable, A]
validateAdult[ExceptionOr](-1)
// res9: ExceptionOr[Int] = Left(
// java.lang.IllegalArgumentException: Age must be greater than or
equal to 18
// )
Eval is also stack‐safe, which means we can use it in very deep recursions
without blowing up the stack.
What do these terms for models of evaluation mean? Let’s see some examples.
Let’s first look at Scala vals. We can see the evaluation model using a com‐
putation with a visible side‐effect. In the following example, the code to com‐
pute the value of x happens at place where it is defined rather than on access.
Accessing x recalls the stored value without re‐running the code.
val x = {
println("Computing X")
math.random
}
// Computing X
// x: Double = 0.0396922778013471
x // first access
// res0: Double = 0.0396922778013471 // first access
x // second access
// res1: Double = 0.0396922778013471
Let’s look at an example using a def. The code to compute y below is not run
until we use it, and is re‐run on every access:
4.6. THE EVAL MONAD 101
def y = {
println("Computing Y")
math.random
}
y // first access
// Computing Y
// res2: Double = 0.5270290953284378 // first access
y // second access
// Computing Y
// res3: Double = 0.348549829974959
Last but not least, lazy vals are an example of call‐by‐need evaluation. The
code to compute z below is not run until we use it for the first time (lazy). The
result is then cached and re‐used on subsequent accesses (memoized):
lazy val z = {
println("Computing Z")
math.random
}
z // first access
// Computing Z
// res4: Double = 0.6672110951657263 // first access
z // second access
// res5: Double = 0.6672110951657263
Eval has three subtypes: Now, Always, and Later. They correspond to call‐
by‐value, call‐by‐name, and call‐by‐need respectively. We construct these
with three constructor methods, which create instances of the three classes
and return them typed as Eval:
import cats.Eval
now.value
// res6: Double = 1000.7009661848473
always.value
// res7: Double = 3000.5158510235524
later.value
// res8: Double = 2000.6995448328964
Each type of Eval calculates its result using one of the evaluation models
defined above. Eval.now captures a value right now. Its semantics are similar
to a val—eager and memoized:
4.6. THE EVAL MONAD 103
val x = Eval.now{
println("Computing X")
math.random
}
// Computing X
// x: Eval[Double] = Now(0.6969571260771719)
val y = Eval.always{
println("Computing Y")
math.random
}
// y: Eval[Double] = cats.Always@6d355284
val z = Eval.later{
println("Computing Z")
math.random
}
// z: Eval[Double] = cats.Later@3429dabc
Like all monads, Eval's map and flatMap methods add computations to a
chain. In this case, however, the chain is stored explicitly as a list of functions.
The functions aren’t run until we call Eval's value method to request a re‐
sult:
greeting.value
// Step 1
// Step 2
// res16: String = "Hello world"
Note that, while the semantics of the originating Eval instances are main‐
tained, mapping functions are always called lazily on demand (def semantics):
One useful property of Eval is that its map and flatMap methods are tram‐
polined. This means we can nest calls to map and flatMap arbitrarily without
consuming stack frames. We call this property “stack safety”.
factorial(50000)
// java.lang.StackOverflowError
// ...
factorial(50000).value
// java.lang.StackOverflowError
// ...
Oops! That didn’t work—our stack still blew up! This is because we’re still mak‐
ing all the recursive calls to factorial before we start working with Eval's
map method. We can work around this using Eval.defer, which takes an ex‐
isting instance of Eval and defers its evaluation. The defer method is tram‐
polined like map and flatMap, so we can use it as a quick way to make an
existing operation stack safe:
factorial(50000).value
// res: A very big value
Eval is a useful tool to enforce stack safety when working on very large com‐
putations and data structures. However, we must bear in mind that trampolin‐
ing is not free. It avoids consuming stack by creating a chain of function objects
4.7. THE WRITER MONAD 107
on the heap. There are still limits on how deeply we can nest computations,
but they are bounded by the size of the heap rather than the stack.
Writer is the first data type we’ve seen from the cats.data package.
This package provides instances of various type classes that produce
useful semantics. Other examples from cats.data include the monad
transformers that we will see in the next chapter, and the Validated
108 CHAPTER 4. MONADS
import cats.data.Writer
import cats.instances.vector._ // for Monoid
Writer(Vector(
"It was the best of times",
"it was the worst of times"
), 1859)
// res0: cats.data.WriterT[cats.package.Id, Vector[String], Int] =
WriterT(
// (Vector("It was the best of times", "it was the worst of times"),
1859)
// )
Let’s try to ignore this detail for now. Writer is a type alias for WriterT, so
we can read types like WriterT[Id, W, A] as Writer[W, A]:
For convenience, Cats provides a way of creating Writers specifying only the
log or the result. If we only have a result we can use the standard pure syntax.
To do this we must have a Monoid[W] in scope so Cats knows how to produce
an empty log:
4.7. THE WRITER MONAD 109
123.pure[Logged]
// res1: Logged[Int] = WriterT((Vector(), 123))
If we have a log and no result we can create a Writer[Unit] using the tell
syntax from cats.syntax.writer:
If we have both a result and a log, we can either use Writer.apply or we can
use the writer syntax from cats.syntax.writer:
We can extract the result and log from a Writer using the value and written
methods respectively:
a.written
// aLog: Vector[String] = Vector("msg1", "msg2", "msg3")
We can extract both values at the same time using the run method:
The log in a Writer is preserved when we map or flatMap over it. flatMap
appends the logs from the source Writer and the result of the user’s sequenc‐
ing function. For this reason it’s good practice to use a log type that has an
efficient append and concatenate operations, such as a Vector:
writer1.run
// res3: (Vector[String], Int) = (Vector("a", "b", "c", "x", "y", "z")
, 42)
In addition to transforming the result with map and flatMap, we can transform
the log in a Writer with the mapWritten method:
writer2.run
// res4: (Vector[String], Int) = (Vector("A", "B", "C", "X", "Y", "Z")
, 42)
We can transform both log and result simultaneously using bimap or mapBoth.
bimap takes two function parameters, one for the log and one for the result.
mapBoth takes a single function that accepts two parameters:
writer3.run
// res5: (Vector[String], Int) = (Vector("A", "B", "C", "X", "Y", "Z")
, 4200)
writer4.run
// res6: (Vector[String], Int) = (
// Vector("a!", "b!", "c!", "x!", "y!", "z!"),
// 42000
// )
Finally, we can clear the log with the reset method and swap log and result
with the swap method:
112 CHAPTER 4. MONADS
writer5.run
// res7: (Vector[String], Int) = (Vector(), 42)
writer6.run
// res8: (Int, Vector[String]) = (42, Vector("a", "b", "c", "x", "y",
"z"))
The factorial function below computes a factorial and prints out the inter‐
mediate steps as it runs. The slowly helper function ensures this takes a while
to run, even on the very small examples below:
factorial(5)
// fact 0 1
// fact 1 1
// fact 2 2
// fact 3 6
// fact 4 24
// fact 5 120
// res9: Int = 120
If we start several factorials in parallel, the log messages can become inter‐
leaved on standard out. This makes it difficult to see which messages come
from which computation:
import scala.concurrent._
import scala.concurrent.ExecutionContext.Implicits._
import scala.concurrent.duration._
Await.result(Future.sequence(Vector(
Future(factorial(5)),
Future(factorial(5))
)), 5.seconds)
// fact 0 1
// fact 0 1
// fact 1 1
// fact 1 1
// fact 2 2
// fact 2 2
// fact 3 6
// fact 3 6
// fact 4 24
// fact 4 24
// fact 5 120
// fact 5 120
// res: scala.collection.immutable.Vector[Int] =
// Vector(120, 120)
import cats.data.Reader
We can extract the function again using the Reader's run method and call it
using apply as usual:
catName.run(Cat("Garfield", "lasagne"))
// res1: cats.package.Id[String] = "Garfield"
So far so simple, but what advantage do Readers give us over the raw func‐
tions?
The power of Readers comes from their map and flatMap methods, which
represent different kinds of function composition. We typically create a set of
4.8. THE READER MONAD 115
Readers that accept the same type of configuration, combine them with map
and flatMap, and then call run to inject the config at the end.
The map method simply extends the computation in the Reader by passing its
result through a function:
greetAndFeed(Cat("Garfield", "lasagne"))
// res3: cats.package.Id[String] = "Hello Garfield. Have a nice bowl
of lasagne."
greetAndFeed(Cat("Heathcliff", "junk food"))
// res4: cats.package.Id[String] = "Hello Heathcliff. Have a nice bowl
of junk food."
Now create methods that generate DbReaders to look up the username for
an Int user ID, and look up the password for a String username. The type
signatures should be as follows:
def checkPassword(
username: String,
password: String): DbReader[Boolean] =
???
Finally create a checkLogin method to check the password for a given user
ID. The type signature should be as follows:
def checkLogin(
userId: Int,
password: String): DbReader[Boolean] =
???
checkLogin(1, "zerocool").run(db)
// res7: cats.package.Id[Boolean] = true
checkLogin(4, "davinci").run(db)
// res8: cats.package.Id[Boolean] = false
Readers provide a tool for doing dependency injection. We write steps of our
program as instances of Reader, chain them together with map and flatMap,
and build a function that accepts the dependency as input.
Kleisli Arrows
You may have noticed from console output that Reader is implemented
in terms of another type called Kleisli. Kleisli arrows provide a more
general form of Reader that generalise over the type constructor of the
result type. We will encounter Kleislis again in Chapter 5.
import cats.data.State
We can “run” our monad by supplying an initial state. State provides three
methods—run, runS, and runA—that return different combinations of state
and result. Each method returns an instance of Eval, which State uses to
maintain stack safety. We call the value method as usual to extract the actual
result:
4.9. THE STATE MONAD 119
As we’ve seen with Reader and Writer, the power of the State monad
comes from combining instances. The map and flatMap methods thread the
state from one instance to another. Each individual instance represents an
atomic state transformation, and their combination represents a complete se‐
quence of changes:
As you can see, in this example the final state is the result of applying both
transformations in sequence. State is threaded from step to step even though
we don’t interact with it in the for comprehension.
The general model for using the State monad is to represent each step of a
computation as an instance and compose the steps using the standard monad
operators. Cats provides several convenience constructors for creating primi‐
tive steps:
import cats.data.State
import State._
The State monad allows us to implement simple interpreters for complex ex‐
pressions, passing the values of mutable registers along with the result. We
can see a simple example of this by implementing a calculator for post‐order
integer arithmetic expressions.
In case you haven’t heard of post‐order expressions before (don’t worry if you
haven’t), they are a mathematical notation where we write the operator after
its operands. So, for example, instead of writing 1 + 2 we would write:
1 2 +
Although post‐order expressions are difficult for humans to read, they are easy
to evaluate in code. All we need to do is traverse the symbols from left to right,
carrying a stack of operands with us as we go:
• when we see an operator, we pop two operands off the stack, operate
on them, and push the result in their place.
Let’s write an interpreter for these expressions. We can parse each symbol
into a State instance representing a transformation on the stack and an inter‐
mediate result. The State instances can be threaded together using flatMap
to produce an interpreter for any sequence of symbols.
Start by writing a function evalOne that parses a single symbol into an in‐
stance of State. Use the code below as a template. Don’t worry about error
handling for now—if the stack is in the wrong configuration, it’s OK to throw
an exception.
import cats.data.State
If this seems difficult, think about the basic form of the State instances you’re
returning. Each instance represents a functional transformation from a stack
to a pair of a stack and a result. You can ignore any wider context and focus
on just that one step:
4.9. THE STATE MONAD 123
Feel free to write your Stack instances in this form or as sequences of the
convenience constructors we saw above.
evalOne("42").runA(Nil).value
// res10: Int = 42
We can represent more complex programs using evalOne, map, and flatMap.
Note that most of the work is happening on the stack, so we ignore the results
of the intermediate steps for evalOne("1") and evalOne("2"):
program.runA(Nil).value
// res11: Int = 3
multistageProgram.runA(Nil).value
// res13: Int = 9
Because evalOne and evalAll both return instances of State, we can thread
these results together using flatMap. evalOne produces a simple stack trans‐
formation and evalAll produces a complex one, but they’re both pure func‐
tions and we can use them in any order as many times as we like:
biggerProgram.runA(Nil).value
// res14: Int = 21
import cats.Monad
import scala.annotation.tailrec
@tailrec
def tailRecM[A, B](a: A)
(fn: A => Option[Either[A, B]]): Option[B] =
fn(a) match {
case None => None
case Some(Left(a1)) => tailRecM(a1)(fn)
case Some(Right(b)) => Some(b)
}
}
To motivate its use let’s use the following example: Suppose we want to write
a method that calls a function until the function indicates it should stop. The
function will return a monad instance because, as we know, monads represent
sequencing and many monads have some notion of stopping.
import cats.instances.option._
It’s important to note that we have to explicitly call tailRecM. There isn’t a
code transformation that will convert non‐tail recursive code into tail recur‐
sive code that uses tailRecM. However there are several utilities provided
by the Monad type class that makes these kinds of methods easier to write.
For example, we can rewrite retry in terms of iterateWhileM and we don’t
have to explicitly call tailRecM.
4.10. DEFINING CUSTOM MONADS 127
Let’s write a Monad for our Tree data type from last chapter. Here’s the type
again:
Verify that the code works on instances of Branch and Leaf, and that the
Monad provides Functor‐like behaviour for free.
Also verify that having a Monad in scope allows us to use for comprehensions,
despite the fact that we haven’t directly implemented flatMap or map on
Tree.
128 CHAPTER 4. MONADS
Don’t feel you have to make tailRecM tail‐recursive. Doing so is quite difficult.
We’ve included both tail‐recursive and non‐tail‐recursive implementations in
the solutions so you can check your work.
4.11 Summary
In this chapter we’ve seen monads up‐close. We saw that flatMap can be
viewed as an operator for sequencing computations, dictating the order in
which operations must happen. From this viewpoint, Option represents a
computation that can fail without an error message, Either represents com‐
putations that can fail with a message, List represents multiple possible re‐
sults, and Future represents a computation that may produce a value at some
point in the future.
We’ve also seen some of the custom types and data structures that Cats pro‐
vides, including Id, Reader, Writer, and State. These cover a wide range of
use cases.
Finally, in the unlikely event that we have to implement a custom monad, we’ve
learned about defining our own instance using tailRecM. tailRecM is an odd
wrinkle that is a concession to building a functional programming library that is
stack‐safe by default. We don’t need to understand tailRecM to understand
monads, but having it around gives us benefits of which we can be grateful
when writing monadic code.
Chapter 5
Monad Transformers
Monads are like burritos, which means that once you acquire a taste, you’ll
find yourself returning to them again and again. This is not without issues. As
burritos can bloat the waist, monads can bloat the code base through nested
for‐comprehensions.
To use this value we must nest flatMap calls (or equivalently, for‐
comprehensions):
129
130 CHAPTER 5. MONAD TRANSFORMERS
A question arises. Given two arbitrary monads, can we combine them in some
way to make a single monad? That is, do monads compose? We can try to
write the code but we soon hit problems:
new Monad[Composed] {
def pure[A](a: A): Composed[A] =
a.pure[M2].pure[M1]
Notice that the definition above makes use of None—an Option‐specific con‐
cept that doesn’t appear in the general Monad interface. We need this extra
detail to combine Option with other monads. Similarly, there are things about
other monads that help us write composed flatMap methods for them. This
is the idea behind monad transformers: Cats defines transformers for a vari‐
ety of monads, each providing the extra knowledge we need to compose that
monad with others. Let’s look at some examples.
5.2. A TRANSFORMATIVE EXAMPLE 131
Cats provides transformers for many monads, each named with a T suffix:
EitherT composes Either with other monads, OptionT composes Option,
and so on.
Here’s an example that uses OptionT to compose List and Option. We can
use OptionT[List, A], aliased to ListOption[A] for convenience, to trans‐
form a List[Option[A]] into a single monad:
import cats.data.OptionT
Note how we build ListOption from the inside out: we pass List, the type
of the outer monad, as a parameter to OptionT, the transformer for the inner
monad.
The map and flatMap methods combine the corresponding methods of List
and Option into single operations:
}
// res1: OptionT[List, Int] = OptionT(List(Some(42)))
This is the basis of all monad transformers. The combined map and flatMap
methods allow us to use both component monads without having to recur‐
sively unpack and repack values at each stage in the computation. Now let’s
look at the API in more depth.
Complexity of Imports
The imports in the code samples above hint at how everything bolts
together.
we’ve built via the Monad type class. The main concepts we have to cover to
understand monad transformers are:
By convention, in Cats a monad Foo will have a transformer class called FooT.
In fact, many monads in Cats are defined by combining a monad transformer
with the Id monad. Concretely, some of the available instances are:
Kleisli Arrows
We can now reveal that Kleisli and ReaderT are, in fact, the same
thing! ReaderT is actually a type alias for Kleisli. Hence, we were
creating Readers last chapter and seeing Kleislis on the console.
All of these monad transformers follow the same convention. The transformer
itself represents the inner monad in a stack, while the first type parameter
134 CHAPTER 5. MONAD TRANSFORMERS
specifies the outer monad. The remaining type parameters are the types we’ve
used to form the corresponding monads.
Many monads and all transformers have at least two type parameters, so we
often have to define type aliases for intermediate stages.
For example, suppose we want to wrap Either around Option. Option is the
innermost type so we want to use the OptionT monad transformer. We need
to use Either as the first type parameter. However, Either itself has two
type parameters and monads only have one. We need a type alias to convert
the type constructor to the correct shape:
ErrorOrOption is a monad, just like ListOption. We can use pure, map, and
flatMap as usual to create and transform instances:
val a = 10.pure[ErrorOrOption]
// a: ErrorOrOption[Int] = OptionT(Right(Some(10)))
val b = 32.pure[ErrorOrOption]
// b: ErrorOrOption[Int] = OptionT(Right(Some(32)))
Things become even more confusing when we want to stack three or more
monads.
5.3. MONAD TRANSFORMERS IN CATS 135
This time we create an alias for EitherT that fixes Future and Error and
allows A to vary:
import scala.concurrent.Future
import cats.data.{EitherT, OptionT}
Our mammoth stack now composes three monads and our map and flatMap
methods cut through three layers of abstraction:
b <- 32.pure[FutureEitherOption]
} yield a + b
Kind Projector
If you frequently find yourself defining multiple type aliases when build‐
ing monad stacks, you may want to try the Kind Projector compiler plu‐
gin. Kind Projector enhances Scala’s type syntax to make it easier to
define partially applied type constructors. For example:
Kind Projector can’t simplify all type declarations down to a single line,
but it can reduce the number of intermediate type definitions needed
to keep our code readable.
As we saw above, we can create transformed monad stacks using the relevant
monad transformer’s apply method or the usual pure syntax¹:
Once we’ve finished with a monad transformer stack, we can unpack it using
its value method. This returns the untransformed stack. We can then manip‐
ulate the individual monads in the usual way:
Each call to value unpacks a single monad transformer. We may need more
than one call to completely unpack a large stack. For example, to Await the
FutureEitherOption stack above, we need to call value twice:
futureEitherOr
// res6: FutureEitherOption[Int] = OptionT(
// EitherT(Future(Success(Right(Some(42)))))
// )
Await.result(stack, 1.second)
// res7: Either[String, Option[Int]] = Right(Some(42))
Many monads in Cats are defined using the corresponding transformer and
the Id monad. This is reassuring as it confirms that the APIs for monads and
transformers are identical. Reader, Writer, and State are all defined in this
way:
138 CHAPTER 5. MONAD TRANSFORMERS
We can cope with this in multiple ways. One approach involves creating a
single “super stack” and sticking to it throughout our code base. This works
if the code is simple and largely uniform in nature. For example, in a web
application, we could decide that all request handlers are asynchronous and
all can fail with the same set of HTTP error codes. We could design a custom
ADT representing the errors and use a fusion Future and Either everywhere
in our code:
The “super stack” approach starts to fail in larger, more heterogeneous code
bases where different stacks make sense in different contexts. Another design
pattern that makes more sense in these contexts uses monad transformers
as local “glue code”. We expose untransformed stacks at module boundaries,
transform them to operate on them locally, and untransform them before pass‐
ing them on. This allows each module of code to make its own decisions about
which transformers to use:
5.3. MONAD TRANSFORMERS IN CATS 139
import cats.data.Writer
result.value
}
Transmissions take time in Earth’s viscous atmosphere, and messages are oc‐
casionally lost due to satellite malfunction or sabotage by pesky Decepticons².
Responses are therefore represented as a stack of monads:
Optimus Prime is getting tired of the nested for comprehensions in his neural
matrix. Help him by rewriting Response using a monad transformer.
Two autobots can perform a special move if their combined power level is
greater than 15. Write a second method, canSpecialMove, that accepts the
²It is a well known fact that Autobot neural nets are implemented in Scala. Decepticon
brains are, of course, dynamically typed.
5.5. SUMMARY 141
names of two allies and checks whether a special move is possible. If either
ally is unavailable, fail with an appropriate error message:
Finally, write a method tacticalReport that takes two ally names and prints
a message saying whether they can perform a special move:
tacticalReport("Jazz", "Bumblebee")
// res13: String = "Jazz and Bumblebee need a recharge."
tacticalReport("Bumblebee", "Hot Rod")
// res14: String = "Bumblebee and Hot Rod are ready to roll out!"
tacticalReport("Jazz", "Ironhide")
// res15: String = "Comms error: Ironhide unreachable"
5.5 Summary
The type signatures of monad transformers are written from the in‐
side out, so an EitherT[Option, String, A] is a wrapper for an
142 CHAPTER 5. MONAD TRANSFORMERS
In previous chapters we saw how functors and monads let us sequence opera‐
tions using map and flatMap. While functors and monads are both immensely
useful abstractions, there are certain types of program flow that they cannot
represent.
for {
a <- parseInt("a")
b <- parseInt("b")
c <- parseInt("c")
} yield (a + b + c)
// res0: Either[String, Int] = Left("Couldn't read a")
143
144 CHAPTER 6. SEMIGROUPAL AND APPLICATIVE
The calls to parseInt and Future.apply above are independent of one an‐
other, but map and flatMap can’t exploit this. We need a weaker construct—
one that doesn’t guarantee sequencing—to achieve the result we want. In this
chapter we will look at three type classes that support this pattern:
6.1 Semigroupal
trait Semigroupal[F[_]] {
def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}
is also the winner of Underscore’s 2017 award for the most difficult functional
programming term to work into a coherent English sentence.
import cats.Semigroupal
import cats.instances.option._ // for Semigroupal
Semigroupal[Option].product(Some(123), Some("abc"))
// res1: Option[(Int, String)] = Some((123, "abc"))
If both parameters are instances of Some, we end up with a tuple of the values
within. If either parameter evaluates to None, the entire result is None:
¹It
146 CHAPTER 6. SEMIGROUPAL AND APPLICATIVE
Semigroupal[Option].product(None, Some("abc"))
// res2: Option[Tuple2[Nothing, String]] = None
Semigroupal[Option].product(Some(123), None)
// res3: Option[Tuple2[Int, Nothing]] = None
The methods map2 through map22 apply a user‐specified function to the val‐
ues inside 2 to 22 contexts:
Semigroupal.map2(Option(1), Option.empty[Int])(_ + _)
// res7: Option[Int] = None
There is only one law for Semigroupal: the product method must be asso‐
ciative.
6.2. APPLY SYNTAX 147
Cats provides a convenient apply syntax that provides a shorthand for the
methods described above. We import the syntax from cats.syntax.apply.
Here’s an example:
The tupled method is implicitly added to the tuple of Options. It uses the
Semigroupal for Option to zip the values inside the Options, creating a sin‐
gle Option of a tuple:
(Option(123), Option("abc")).tupled
// res8: Option[(Int, String)] = Some((123, "abc"))
We can use the same trick on tuples of up to 22 values. Cats defines a separate
tupled method for each arity:
In addition to tupled, Cats’ apply syntax provides a method called mapN that
accepts an implicit Functor and a function of the correct arity to combine the
values.
(
Option("Garfield"),
Option(1978),
Option("Orange & black")
148 CHAPTER 6. SEMIGROUPAL AND APPLICATIVE
).mapN(Cat.apply)
// res10: Option[Cat] = Some(Cat("Garfield", 1978, "Orange & black"))
Internally mapN uses the Semigroupal to extract the values from the Option
and the Functor to apply the values to the function.
It’s nice to see that this syntax is type checked. If we supply a function that
accepts the wrong number or types of parameters, we get a compile error:
(Option("cats"), Option(true)).mapN(add)
// error: ':' expected but '(' found.
// Option("Garfield"),
// ^
// error: identifier expected but '}' found.
Apply syntax also has contramapN and imapN methods that accept Con‐
travariant and Invariant functors (Section 3.6). For example, we can combine
Monoids using Invariant. Here’s an example:
import cats.Monoid
import cats.instances.int._ // for Monoid
import cats.instances.invariant._ // for Semigroupal
import cats.instances.list._ // for Monoid
import cats.instances.string._ // for Monoid
import cats.syntax.apply._ // for imapN
name: String,
yearOfBirth: Int,
favoriteFoods: List[String]
)
Our Monoid allows us to create “empty” Cats, and add Cats together using
the syntax from Chapter 2:
Future
import cats.Semigroupal
import cats.instances.future._ // for Semigroupal
import scala.concurrent._
import scala.concurrent.duration._
import scala.concurrent.ExecutionContext.Implicits.global
Await.result(futurePair, 1.second)
// res0: (String, Int) = ("Hello", 123)
The two Futures start executing the moment we create them, so they are
already calculating results by the time we call product. We can use apply
syntax to zip fixed numbers of Futures:
val futureCat = (
Future("Garfield"),
Future(1978),
Future(List("Lasagne"))
).mapN(Cat.apply)
Await.result(futureCat, 1.second)
// res1: Cat = Cat("Garfield", 1978, List("Lasagne"))
List
import cats.Semigroupal
import cats.instances.list._ // for Semigroupal
Either
Semigroupal[ErrorOr].product(
Left(Vector("Error 1")),
Left(Vector("Error 2"))
)
// res3: ErrorOr[Tuple2[Nothing, Nothing]] = Left(Vector("Error 1"))
In this example product sees the first failure and stops, even though it is pos‐
sible to examine the second parameter and see that it is also a failure.
The reason for the surprising results for List and Either is that they are both
monads. If we have a monad we can implement product as follows.
import cats.Monad
import cats.syntax.functor._ // for map
import cats.syntax.flatMap._ // for flatmap
fa.flatMap(a =>
fb.map(b =>
(a, b)
)
)
Even our results for Future are a trick of the light. flatMap provides se‐
quential ordering, so product provides the same. The parallel execution we
observe occurs because our constituent Futures start running before we call
product. This is equivalent to the classic create‐then‐flatMap pattern:
for {
x <- a
y <- b
} yield (x, y)
So why bother with Semigroupal at all? The answer is that we can create
useful data types that have instances of Semigroupal (and Applicative)
but not Monad. This frees us to implement product in different ways. We’ll
examine this further in a moment when we look at an alternative data type for
error handling.
Why does product for List produce the Cartesian product? We saw an ex‐
ample above. Here it is again.
6.4 Parallel
In the previous section we saw that when call product on a type that has a
Monad instance we get sequential semantics. This makes sense from the point‐
of‐view of keeping consistency with implementations of product in terms of
flatMap and map. However it’s not always what we want. The Parallel
type class, and its associated syntax, allows us to access alternate semantics
for certain monads.
We’ve seen how the product method on Either stops at the first error.
import cats.Semigroupal
import cats.instances.either._ // for Semigroupal
Semigroupal[ErrorOr].product(error1, error2)
// res0: ErrorOr[(Int, Int)] = Left(Vector("Error 1"))
(error1, error2).tupled
// res1: ErrorOr[(Int, Int)] = Left(Vector("Error 1"))
To collect all the errors we simply replace tupled with its “parallel” version
called parTupled.
154 CHAPTER 6. SEMIGROUPAL AND APPLICATIVE
(error1, error2).parTupled
// res2: ErrorOr[(Int, Int)] = Left(Vector("Error 1", "Error 2"))
Notice that both errors are returned! This behaviour is not special to using
Vector as the error type. Any type that has a Semigroup instance will work.
For example, here we use List instead.
(errStr1, errStr2).parTupled
// res3: ErrorOrList[(Int, Int)] = Left(List("error 1", "error 2"))
(error1, error2).parMapN(addTwo)
// res4: ErrorOr[Int] = Left(Vector("Error 1", "Error 2"))
(success1, success2).parMapN(addTwo)
// res5: ErrorOr[Int] = Right(3)
Let’s dig into how Parallel works. The definition below is the core of
Parallel.
trait Parallel[M[_]] {
type F[_]
This tells us if there is a Parallel instance for some type constructor M then:
We haven’t seen ~> before. It’s a type alias for FunctionK and is what per‐
forms the conversion from M to F. A normal function A => B converts values
of type A to values of type B. Remember that M and F are not types; they
are type constructors. A FunctionK M ~> F is a function from a value with
type M[A] to a value with type F[A]. Let’s see a quick example by defining a
FunctionK that converts an Option to a List.
import cats.arrow.FunctionK
optionToList(Some(1))
// res6: List[Int] = List(1)
optionToList(None)
// res7: List[Nothing] = List()
We’ve seen the case above where the related applicative for Either allows
for accumulation of errors instead of fail‐fast semantics.
Now we’ve seen Parallel it’s time to finally learn about Applicative.
Does List have a Parallel instance? If so, what does the Parallel instance
do?
Cats models applicatives using two type classes. The first, cats.Apply, ex‐
tends Semigroupal and Functor and adds an ap method that applies a pa‐
rameter to a function within a context. The second, cats.Applicative, ex‐
tends Apply and adds the pure method introduced in Chapter 4. Here’s a
simplified definition in code:
Applicative also introduces the pure method. This is the same pure we
saw in Monad. It constructs a new applicative instance from an unwrapped
value. In this sense, Applicative is related to Apply as Monoid is related to
Semigroup.
With the introduction of Apply and Applicative, we can zoom out and see
a whole family of type classes that concern themselves with sequencing com‐
putations in different ways. Figure 6.1 shows the relationship between the
type classes covered in this book³.
Each type class in the hierarchy represents a particular set of sequencing se‐
mantics, introduces a set of characteristic methods, and defines the function‐
ality of its supertypes in terms of them:
Because of the lawful nature of the relationships between the type classes,
the inheritance relationships are constant across all instances of a type class.
Apply defines product in terms of ap and map; Monad defines product, ap,
and map, in terms of pure and flatMap.
• Foo is a monad. It has an instance of the Monad type class that imple‐
ments pure and flatMap and inherits standard definitions of product,
map, and ap;
What can we say about these two data types without knowing more about
their implementation?
This demonstrates the classic trade‐off of power (in the mathematical sense)
versus constraint. The more constraints we place on a data type, the more
6.6. SUMMARY 159
guarantees we have about its behaviour, but the fewer behaviours we can
model.
Monads happen to be a sweet spot in this trade‐off. They are flexible enough
to model a wide range of behaviours and restrictive enough to give strong guar‐
antees about those behaviours. However, there are situations where monads
aren’t the right tool for the job. Sometimes we want Thai food, and burritos
just won’t satisfy.
6.6 Summary
While monads and functors are the most widely used sequencing data types
we’ve covered in this book, semigroupals and applicatives are the most general.
These type classes provide a generic mechanism to combine values and apply
functions within a context, from which we can fashion monads and a variety
of other combinators.
In this chapter we’ll look at two type classes that capture iteration over collec‐
tions:
We’ll start by looking at Foldable, and then examine cases where folding
becomes complex and Traverse becomes convenient.
7.1 Foldable
The Foldable type class captures the foldLeft and foldRight meth‐
ods we’re used to in sequences like Lists, Vectors, and Streams. Using
Foldable, we can write generic folds that work with a variety of sequence
types. We can also invent new sequences and plug them into our code.
Foldable gives us great use cases for Monoids and the Eval monad.
161
162 CHAPTER 7. FOLDABLE AND TRAVERSE
Let’s start with a quick recap of the general concept of folding. We supply an
accumulator value and a binary function to combine it with each item in the
sequence:
show(Nil)
// res0: String = "nil"
show(List(1, 2, 3))
// res1: String = "3 then 2 then 1 then nil"
The foldLeft method works recursively down the sequence. Our binary
function is called repeatedly for each item, the result of each call becoming
the accumulator for the next. When we reach the end of the sequence, the
final accumulator becomes our final result.
Depending on the operation we’re performing, the order in which we fold may
be important. Because of this there are two standard variants of fold:
List(1, 2, 3).foldLeft(0)(_ + _)
// res2: Int = 6
List(1, 2, 3).foldRight(0)(_ + _)
// res3: Int = 6
1 1
2 2
3
3
0 + 1
3 + 0
1 + 2 2 + 3
3 + 3 1 + 5
6 6
List(1, 2, 3).foldLeft(0)(_ - _)
// res4: Int = -6
List(1, 2, 3).foldRight(0)(_ - _)
// res5: Int = 2
Try using foldLeft and foldRight with an empty list as the accumulator and
:: as the binary operator. What results do you get in each case?
foldLeft and foldRight are very general methods. We can use them
to implement many of the other high‐level sequence operations we know.
Prove this to yourself by implementing substitutes for List's map, flatMap,
filter, and sum methods in terms of foldRight.
Cats’ Foldable abstracts foldLeft and foldRight into a type class. In‐
stances of Foldable define these two methods and inherit a host of derived
164 CHAPTER 7. FOLDABLE AND TRAVERSE
We can summon instances as usual using Foldable.apply and call their im‐
plementations of foldLeft directly. Here is an example using List:
import cats.Foldable
import cats.instances.list._ // for Foldable
Foldable[List].foldLeft(ints, 0)(_ + _)
// res0: Int = 6
Other sequences like Vector and LazyList work in the same way. Here is
an example using Option, which is treated like a sequence of zero or one
elements:
Foldable[Option].foldLeft(maybeInt, 10)(_ * _)
// res1: Int = 1230
Using Eval means folding is always stack safe, even when the collection’s de‐
fault definition of foldRight is not. For example, the default implementation
of foldRight for LazyList is not stack safe. The longer the lazy list, the
larger the stack requirements for the fold. A sufficiently large lazy list will trig‐
ger a StackOverflowError:
7.1. FOLDABLE 165
import cats.Eval
import cats.Foldable
bigData.foldRight(0L)(_ + _)
// java.lang.StackOverflowError ...
Using Foldable forces us to use stack safe operations, which fixes the over‐
flow exception:
eval.value
// res3: Long = 5000050000L
Stack safety isn’t typically an issue when using the standard library. The
most commonly used collection types, such as List and Vector, pro‐
vide stack safe implementations of foldRight:
(1 to 100000).toList.foldRight(0L)(_ + _)
// res4: Long = 5000050000L
(1 to 100000).toVector.foldRight(0L)(_ + _)
// res5: Long = 5000050000L
Foldable[Option].nonEmpty(Option(42))
// res6: Boolean = true
Foldable[List].find(List(1, 2, 3))(_ % 2 == 0)
// res7: Option[Int] = Some(2)
In addition to these familiar methods, Cats provides two methods that make
use of Monoids:
• combineAll (and its alias fold) combines all elements in the sequence
using their Monoid;
Foldable[List].combineAll(List(1, 2, 3))
// res8: Int = 6
Alternatively, we can use foldMap to convert each Int to a String and con‐
catenate them:
Foldable[List].foldMap(List(1, 2, 3))(_.toString)
// res9: String = "123"
List(1, 2, 3).combineAll
// res12: Int = 6
List(1, 2, 3).foldMap(_.toString)
// res13: String = "123"
List(1, 2, 3).foldLeft(0)(_ + _)
// res14: Int = 6
7.2 Traverse
foldLeft and foldRight are flexible iteration methods but they require us
to do a lot of work to define accumulators and combinator functions. The
Traverse type class is a higher level tool that leverages Applicatives to
provide a more convenient, more lawful, pattern for iteration.
import scala.concurrent._
import scala.concurrent.duration._
import scala.concurrent.ExecutionContext.Implicits.global
Now, suppose we want to poll all of the hosts and collect all of their
uptimes. We can’t simply map over hostnames because the result—a
7.2. TRAVERSE 169
Await.result(allUptimes, 1.second)
// res0: List[Int] = List(1020, 960, 840)
Intuitively, we iterate over hostnames, call func for each item, and combine
the results into a list. This sounds simple, but the code is fairly unwieldy be‐
cause of the need to create and combine Futures at every iteration. We can
improve on things greatly using Future.traverse, which is tailor‐made for
this pattern:
Await.result(allUptimes, 1.second)
// res2: List[Int] = List(1020, 960, 840)
This is much clearer and more concise—let’s see how it works. If we ignore
distractions like CanBuildFrom and ExecutionContext, the implementation
of Future.traverse in the standard library looks like this:
object Future {
def sequence[B](futures: List[Future[B]]): Future[List[B]] =
traverse(futures)(identity)
// etc...
}
Cats’ Traverse type class generalises these patterns to work with any type
of Applicative: Future, Option, Validated, and so on. We’ll approach
7.2. TRAVERSE 171
Traverse in the next sections in two steps: first we’ll generalise over the
Applicative, then we’ll generalise over the sequence type. We’ll end up
with an extremely valuable tool that trivialises many operations involving se‐
quences and other data types.
Future(List.empty[Int])
is equivalent to Applicative.pure:
import cats.Applicative
import cats.instances.future._ // for Applicative
import cats.syntax.applicative._ // for pure
List.empty[Int].pure[Future]
def oldCombine(
accum : Future[List[Int]],
host : String
): Future[List[Int]] = {
val uptime = getUptime(host)
for {
accum <- accum
uptime <- uptime
} yield accum :+ uptime
}
Await.result(totalUptime, 1.second)
// res5: List[Int] = List(1020, 960, 840)
or we can use it with other Applicative data types as shown in the following
exercises.
What is the return type of this method? What does it produce for the following
inputs?
process(List(2, 4, 6))
process(List(1, 2, 3))
import cats.data.Validated
import cats.instances.list._ // for Monoid
process(List(2, 4, 6))
process(List(1, 2, 3))
package cats
trait Traverse[F[_]] {
def traverse[G[_]: Applicative, A, B]
(inputs: F[A])(func: A => G[B]): G[F[B]]
import cats.Traverse
import cats.instances.future._ // for Applicative
import cats.instances.list._ // for Traverse
Await.result(totalUptime, 1.second)
// res0: List[Int] = List(1020, 960, 840)
Await.result(numbers2, 1.second)
// res1: List[Int] = List(1, 2, 3)
Await.result(hostnames.traverse(getUptime), 1.second)
// res2: List[Int] = List(1020, 960, 840)
Await.result(numbers.sequence, 1.second)
// res3: List[Int] = List(1, 2, 3)
As you can see, this is much more compact and readable than the foldLeft
code we started with earlier this chapter!
7.3 Summary
useful additions. That said, Foldable doesn’t introduce much that we didn’t
already know.
The real power comes from Traverse, which abstracts and generalises the
traverse and sequence methods we know from Future. Using these meth‐
ods we can turn an F[G[A]] into a G[F[A]] for any F with an instance of
Traverse and any G with an instance of Applicative. In terms of the re‐
duction we get in lines of code, Traverse is one of the most powerful pat‐
terns in this book. We can reduce folds of many lines down to a single
foo.traverse.
…and with that, we’ve finished all of the theory in this book. There’s plenty
more to come, though, as we put everything we’ve learned into practice in a
series of in‐depth case studies in Part II!
Part II
Case Studies
177
Chapter 8
We’ll start with a straightforward case study: how to simplify unit tests for
asynchronous code by making them synchronous.
Let’s return to the example from Chapter 7 where we’re measuring the uptime
on a set of servers. We’ll flesh out the code into a more complete structure.
There will be two components. The first is an UptimeClient that polls remote
servers for their uptime:
import scala.concurrent.Future
trait UptimeClient {
def getUptime(hostname: String): Future[Int]
}
We’ll also have an UptimeService that maintains a list of servers and allows
the user to poll them for their total uptime:
179
180 CHAPTER 8. CASE STUDY: TESTING ASYNCHRONOUS CODE
import scala.concurrent.ExecutionContext.Implicits.global
Now, suppose we’re writing unit tests for UptimeService. We want to test
its ability to sum values, regardless of where it is getting them from. Here’s an
example:
def testTotalUptime() = {
val hosts = Map("host1" -> 10, "host2" -> 6)
val client = new TestUptimeClient(hosts)
val service = new UptimeService(client)
val actual = service.getTotalUptime(hosts.keys.toList)
val expected = hosts.values.sum
assert(actual == expected)
}
//
The code doesn’t compile because we’ve made a classic error¹. We forgot
that our application code is asynchronous. Our actual result is of type
Future[Int] and our expected result is of type Int. We can’t compare
them directly!
There are a couple of ways to solve this problem. We could alter our test
code to accommodate the asynchronousness. However, there is another al‐
¹Technically this is a warning not an error. It has been promoted to an error in our case
because we’re using the -Xfatal-warnings flag on scalac.
8.1. ABSTRACTING OVER TYPE CONSTRUCTORS 181
ternative. Let’s make our service code synchronous so our test works without
modification!
The question is: what result type should we give to the abstract method in
UptimeClient? We need to abstract over Future[Int] and Int:
trait UptimeClient {
def getUptime(hostname: String): ???
}
At first this may seem difficult. We want to retain the Int part from each
type but “throw away” the Future part in the test code. Fortunately, Cats
provides a solution in terms of the identity type, Id, that we discussed way
back in Section 4.3. Id allows us to “wrap” types in a type constructor without
changing their meaning:
package cats
type Id[A] = A
• write out the method signature for getUptime in each case to verify
that it compiles.
Finally, let’s turn our attention to our unit tests. Our test code now
works as intended without any modification. We create an instance of
TestUptimeClient and wrap it in an UptimeService. This effectively binds
F to Id, allowing the rest of the code to operate synchronously without wor‐
rying about monads or applicatives:
def testTotalUptime() = {
val hosts = Map("host1" -> 10, "host2" -> 6)
val client = new TestUptimeClient(hosts)
val service = new UptimeService(client)
val actual = service.getTotalUptime(hosts.keys.toList)
val expected = hosts.values.sum
assert(actual == expected)
}
testTotalUptime()
8.3 Summary
This case study provides an example of how Cats can help us abstract over
different computational scenarios. We used the Applicative type class to
abstract over asynchronous and synchronous code. Leaning on a functional
abstraction allows us to specify the sequence of computations we want to
perform without worrying about the details of the implementation.
184 CHAPTER 8. CASE STUDY: TESTING ASYNCHRONOUS CODE
We used Applicative in this case study because it was the least powerful
type class that did what we needed. If we had required flatMap, we could
have swapped out Applicative for Monad. If we had needed to abstract over
different sequence types, we could have used Traverse. There are also type
classes like ApplicativeError and MonadError that help model failures as
well as successful computations.
Let’s move on now to a more complex case study where type classes will help
us produce something more interesting: a map‐reduce‐style framework for
parallel processing.
Chapter 9
If you have used Hadoop or otherwise worked in “big data” you will have heard
of MapReduce, which is a programming model for doing parallel data process‐
ing across clusters of machines (aka “nodes”). As the name suggests, the model
is built around a map phase, which is the same map function we know from
Scala and the Functor type class, and a reduce phase, which we usually call
fold¹ in Scala.
Recall the general signature for map is to apply a function A => B to a F[A],
returning a F[B]:
¹In Hadoop there is also a shuffle phase that we will ignore here.
185
186 CHAPTER 9. CASE STUDY: MAP‐REDUCE
map
foldLeft ,
What about fold? We can implement this step with an instance of Foldable.
Not every functor also has an instance of foldable but we can implement a
map‐reduce system on top of any data type that has both of these type classes.
Our reduction step becomes a foldLeft over the results of the distributed
map.
By distributing the reduce step we lose control over the order of traversal.
Our overall reduction may not be entirely left‐to‐right—we may reduce left‐
to‐right across several subsequences and then combine the results. To ensure
correctness we need a reduction operation that is associative:
In summary, our parallel fold will yield the correct results if:
What does this pattern sound like? That’s right, we’ve come full circle back
to Monoid, the first type class we discussed in this book. We are not the
first to recognise the importance of monoids. The monoid design pattern for
map‐reduce jobs is at the core of recent big data systems such as Twitter’s
Summingbird.
Start by writing out the signature of foldMap. It should accept the following
parameters:
You will have to add implicit parameters or context bounds to complete the
type signature.
Now implement the body of foldMap. Use the flow chart in Figure 9.3 as a
guide to the steps required:
188 CHAPTER 9. CASE STUDY: MAP‐REDUCE
2. Map step
3. Fold/reduce step
4. Final result
foldMap(Vector(1, 2, 3))(identity)
// res1: Int = 6
We’ll write a multi‐CPU implementation that simulates the way we would dis‐
tribute work in a map‐reduce cluster as shown in Figure 9.4:
We already know a fair amount about the monadic nature of Futures. Let’s
take a moment for a quick recap, and to describe how Scala futures are sched‐
uled behind the scenes.
6. Final result
import scala.concurrent.Future
import scala.concurrent.ExecutionContext.Implicits.global
Some combinators create new Futures that schedule work based on the re‐
sults of other Futures. The map and flatMap methods, for example, schedule
computations that run as soon as their input values are computed and a CPU
is available:
or an instance of Traverse:
import scala.concurrent._
import scala.concurrent.duration._
There are also Monad and Monoid implementations for Future available from
cats.instances.future:
Monad[Future].pure(42)
Monoid[Future[Int]].combine(Future(1), Future(2))
Now we’ve refreshed our memory of Futures, let’s look at how we can di‐
vide work into batches. We can query the number of available CPUs on our
machine using an API call from the Java standard library:
9.3. PARALLELISING FOLDMAP 193
Runtime.getRuntime.availableProcessors
// res11: Int = 2
(1 to 10).toList.grouped(3).toList
// res12: List[List[Int]] = List(
// List(1, 2, 3),
// List(4, 5, 6),
// List(7, 8, 9),
// List(10)
// )
Use the techniques described above to split the work into batches, one batch
per CPU. Process each batch in a parallel thread. Refer back to Figure 9.4 if
you need to review the overall algorithm.
For bonus points, process the batches for each CPU using your implementa‐
tion of foldMap from above.
9.4 Summary
In this case study we will build a library for validation. What do we mean by
validation? Almost all programs must check their input meets certain criteria.
Usernames must not be blank, email addresses must be valid, and so on. This
type of validation often occurs in web forms, but it could be performed on
configuration files, on web service responses, and any other case where we
have to deal with data that we can’t guarantee is correct. Authentication, for
example, is just a specialised form of validation.
We want to build a library that performs these checks. What design goals
should we have? For inspiration, let’s look at some examples of the types of
checks we want to perform:
• A bid in an auction must apply to one or more items and have a positive
value.
195
196 CHAPTER 10. CASE STUDY: DATA VALIDATION
• An email address must contain a single @ sign. Split the string at the @.
The string to the left must not be empty. The string to the right must
be at least three characters long and contain a dot.
• We should be able to combine small checks into larger ones. Taking the
username example above, we should be able to express this by combin‐
ing a check of length and a check for alphanumeric values.
These goals assume we’re checking a single piece of data. We will also need to
combine checks across multiple pieces of data. For a login form, for example,
we’ll need to combine the check results for the username and the password.
This will turn out to be quite a small component of the library, so the majority
of our time will focus on checking a single data item.
Let’s start at the bottom, checking individual pieces of data. Before we start
coding let’s try to develop a feel for what we’ll be building. We can use a
graphical notation to help us. We’ll go through our goals one by one.
Our first goal requires us to associate useful error messages with a check fail‐
ure. The output of a check could be either the value being checked, if it passed
10.1. SKETCHING THE LIBRARY STRUCTURE 197
F[A]
A => F[A]
the check, or some kind of error message. We can abstractly represent this as
a value in a context, where the context is the possibility of an error message
as shown in Figure 10.1.
Combine checks
Not really. With applicative combination, both checks are applied to the same
value and result in a tuple with the value repeated. What we want feels more
like a monoid as shown in Figure 10.4. We can define a sensible identity—a
check that always passes—and two binary combination operators—and and or:
We’ll probably be using and and or about equally often with our validation
( , ).tupled
|+|
map
flatMap
Monoids also feel like a good mechanism for accumulating error messages.
If we store messages as a List or NonEmptyList, we can even use a pre‐
existing monoid from inside Cats.
In addition to checking data, we also have the goal of transforming it. This
seems like it should be a map or a flatMap depending on whether the trans‐
form can fail or not, so it seems we also want checks to be a monad as shown
in Figure 10.5.
We’ve now broken down our library into familiar abstractions and are in a good
position to begin development.
10.2. THE CHECK DATATYPE 199
Our design revolves around a Check, which we said was a function from a
value to a value in a context. As soon as you see this description you should
think of something like
Here we’ve represented the error message as a String. This is probably not
the best representation. We may want to accumulate messages in a List, for
example, or even use a different representation that allows for international‐
ization or standard error codes.
We could attempt to build some kind of ErrorMessage type that holds all
the information we can think of. However, we can’t predict the user’s require‐
ments. Instead let’s let the user specify what they want. We can do this by
adding a second type parameter to Check:
trait Check[E, A] {
def apply(value: A): Either[E, A]
// other methods...
}
Type classes allow us to unify disparate data types with a common interface.
This doesn’t seem like what we’re trying to do here. That leaves us with an
200 CHAPTER 10. CASE STUDY: DATA VALIDATION
E • E => E
algebraic data type. Let’s keep that thought in mind as we explore the design
a bit further.
Let’s add some combinator methods to Check, starting with and. This method
combines two checks into one, succeeding only if both checks succeed. Think
about implementing this method now. You should hit some problems. Read
on when you do!
trait Check[E, A] {
def and(that: Check[E, A]): Check[E, A] =
???
// other methods...
}
The problem is: what do you do when both checks fail? The correct thing to
do is to return both errors, but we don’t currently have any way to combine
Es. We need a type class that abstracts over the concept of “accumulating”
errors as shown in Figure 10.6 What type class do we know that looks like
this? What method or operator should we use to implement the • operation?
There is another semantic issue that will come up quite quickly: should and
short‐circuit if the first check fails. What do you think the most useful be‐
haviour is?
Use this knowledge to implement and. Make sure you end up with the be‐
haviour you expect!
With and and or we can implement many of checks we’ll want in practice.
However, we still have a few more methods to add. We’ll turn to map and
related methods next.
The obvious starting point is map. When we try to implement this, we imme‐
diately run into a wall. Our current definition of Check requires the input and
output types to be the same:
When we map over a check, what type do we assign to the result? It can’t be
A and it can’t be B. We are at an impasse:
202 CHAPTER 10. CASE STUDY: DATA VALIDATION
However, splitting our input and output types raises another issue. Up until
now we have operated under the assumption that a Check always returns its
input when successful. We used this in and and or to ignore the output of the
left and right rules and simply return the original input on success:
// etc...
}
10.4.1 Predicates
We can make progress by pulling apart the concept of a predicate, which can
be combined using logical operations such as and and or, and the concept of
a check, which can transform data.
10.4. TRANSFORMING DATA 203
What we have called Check so far we will call Predicate. For Predicate
we can state the following identity law encoding the notion that a predicate
always returns its input if it succeeds:
import cats.Semigroup
import cats.data.Validated
import cats.syntax.semigroup._ // for |+|
import cats.syntax.apply._ // for mapN
import cats.data.Validated._ // for Valid and Invalid
10.4.2 Checks
We’ll use Check to represent a structure we build from a Predicate that also
allows transformation of its input. Implement Check with the following inter‐
face:
What about flatMap? The semantics are a bit unclear here. The method is
simple enough to declare but it’s not so obvious what it means or how we
should implement apply. The general shape of flatMap is shown in Figure
10.7.
How do we relate F in the figure to Check in our code? Check has three type
variables while F only has one.
To unify the types we need to fix two of the type parameters. The idiomatic
choices are the error type E and the input type A. This gives us the relationships
shown in Figure 10.8. In other words, the semantics of applying a FlatMap
are:
10.4. TRANSFORMING DATA 205
flatMap
flatMap
• return to the original input of type A and apply it to the chosen check
to generate the final result of type F[C].
This is quite an odd method. We can implement it, but it is hard to find a use
for it. Go ahead and implement flatMap for Check, and then we’ll see a more
generally useful method.
We can write a more useful combinator that chains together two Checks. The
output of the first check is connected to the input of the second. This is anal‐
ogous to function composition using andThen:
trait Check[E, A, B] {
def andThen[C](that: Check[E, B, C]): Check[E, A, C]
}
10.4.3 Recap
We now have two algebraic data types, Predicate and Check, and a host
of combinators with their associated case class implementations. Look at the
following solution for a complete definition of each ADT.
There are a lot of ways this library could be cleaned up. However, let’s imple‐
ment some examples to prove to ourselves that our library really does work,
and then we’ll turn to improving it.
• An email address must contain an @ sign. Split the string at the @. The
string to the left must not be empty. The string to the right must be at
least three characters long and contain a dot.
10.5 Kleislis
We’ll finish off this case study by cleaning up the implementation of Check. A
justifiable criticism of our approach is that we’ve written a lot of code to do
very little. A Predicate is essentially a function A => Validated[E, A],
and a Check is basically a wrapper that lets us compose these functions.
flatMap flatMap
• We lift some value into a monad (by using pure, for example). This is a
function with type A => F[A].
We can illustrate this as shown in Figure 10.9. We can also write out this
example using the monad API as follows:
Recall that Check is, in the abstract, allowing us to compose functions of type
A => F[B]. We can write the above in terms of andThen as:
The result is a (wrapped) function aToC of type A => F[C] that we can sub‐
sequently apply to a value of type A.
We have achieved the same thing as the example method without having to
reference an argument of type A. The andThen method on Check is analogous
to function composition, but is composing function A => F[B] instead of A
=> B.
The abstract concept of composing functions of type A => F[B] has a name:
a Kleisli.
import cats.data.Kleisli
import cats.instances.list._ // for Monad
These steps each transform an input Int into an output of type List[Int]:
We can combine the steps into a single pipeline that combines the underlying
Lists using flatMap:
The result is a function that consumes a single Int and returns eight outputs,
each produced by a different combination of transformations from step1,
step2, and step3:
pipeline.run(20)
// res0: List[Int] = List(42, 10, -42, -10, 38, 9, -38, -9)
The only notable difference between Kleisli and Check in terms of API is
that Kleisli renames our apply method to run.
Add a method to Predicate called run that returns a function of the correct
type. Leave the rest of the code in Predicate the same.
Now rewrite our username and email validation example in terms of Kleisli
and Predicate. Here are few tips in case you get stuck:
First, remember that the run method on Predicate takes an implicit param‐
eter. If you call aPredicate.run(a) it will try to pass the implicit parameter
explicitly. If you want to create a function from a Predicate and immediately
apply that function, use aPredicate.run.apply(a)
Second, type inference can be tricky in this exercise. We found that the fol‐
lowing definitions helped us to write code with fewer type declarations.
We have now written our code entirely in terms of Kleisli and Predicate,
completely removing Check. This is a good first step to simplifying our library.
There’s still plenty more to do, but we have a sophisticated building block from
Cats to work with. We’ll leave further improvements up to the reader.
10.6. SUMMARY 211
10.6 Summary
This case study has been an exercise in removing rather than building abstrac‐
tions. We started with a fairly complex Check type. Once we realised we
were conflating two concepts, we separated out Predicate leaving us with
something that could be implemented with Kleisli.
We made several design choices above that reasonable developers may dis‐
agree with. Should the method that converts a Predicate to a function really
be called run instead of, say, toFunction? Should Predicate be a subtype
of Function to begin with? Many functional programmers prefer to avoid
subtyping because it plays poorly with implicit resolution and type inference,
but there could be an argument to use it here. As always the best decisions
depend on the context in which the library will be used.
212 CHAPTER 10. CASE STUDY: DATA VALIDATION
Chapter 11
In this case study we will explore Commutative Replicated Data Types (CRDTs),
a family of data structures that can be used to reconcile eventually consistent
data.
We’ll start by describing the utility and difficulty of eventually consistent sys‐
tems, then show how we can use monoids and their extensions to solve the
issues that arise. Finally, we will model the solutions in Scala.
One approach is to build a system that is consistent, meaning that all machines
have the same view of data. For example, if a user changes their password
then all machines that store a copy of that password must accept the change
before we consider the operation to have completed successfully.
213
214 CHAPTER 11. CASE STUDY: CRDTS
Consistent systems are easy to work with but they have their disadvantages.
They tend to have high latency because a single change can result in many
messages being sent between machines. They also tend to have relatively low
uptime because outages can cut communications between machines creating
a network partition. When there is a network partition, a consistent system
may refuse further updates to prevent inconsistencies across machines.
Let’s look at one particular CRDT implementation. Then we’ll attempt to gen‐
eralise properties to see if we can find a general pattern.
Machine A Machine B
0 0
Machine A Machine B
5 5
Now imagine we receive some web traffic. Our load balancer distributes five
incoming requests to A and B, A serving three visitors and B two. The ma‐
chines have inconsistent views of the system state that they need to reconcile
to achieve consistency. One reconciliation strategy with simple counters is to
exchange counts and add them as shown in Figure 11.2.
So far so good, but things will start to fall apart shortly. Suppose A serves
a single visitor, which means we’ve seen six visitors in total. The machines
attempt to reconcile state again using addition leading to the answer shown
in Figure 11.3.
This is clearly wrong! The problem is that simple counters don’t give us enough
information about the history of interactions between the machines. Fortu‐
nately we don’t need to store the complete history to get the correct answer—
just a summary of it. Let’s look at how the GCounter solves this problem.
216 CHAPTER 11. CASE STUDY: CRDTS
Machine A Machine B
Incoming request
6 5
Add counters
11 11 Incorrect result!
Figure 11.3: Simple counters: second round of requests and (incorrect) recon‐
ciliation
Machine A Machine B
A:0 A:0
B:0 B:0
11.2.2 GCounters
The first clever idea in the GCounter is to have each machine storing a separate
counter for every machine it knows about (including itself). In the previous
example we had two machines, A and B. In this situation both machines would
store a counter for A and a counter for B as shown in Figure 11.4.
The rule with GCounters is that a given machine is only allowed to increment
its own counter. If A serves three visitors and B serves two visitors the counters
look as shown in Figure 11.5.
When two machines reconcile their counters the rule is to take the largest
value stored for each machine. In our example, the result of the first merge
will be as shown in Figure 11.6.
Machine A Machine B
Incoming requests
A:3 A:0 Incoming requests
B:0 B:2
Machine A Machine B
Incoming requests
A:3 A:0 Incoming requests
B:0 B:2
Merge, take max
A:3 A:3
B:2 B:2
Figure 11.7.
Machine A Machine B
Incoming request
A:4 A:3
B:2 B:2
Merge, take max
???
11.3 Generalisation
You can probably guess that there’s a monoid in here somewhere, but let’s look
in more detail at the properties we’re relying on.
As a refresher, in Chapter 2 we saw that monoids must satisfy two laws. The
binary operation + must be associative:
(a + b) + c == a + (b + c)
0 + a == a + 0 == a
a max a = a
increment Y N Y N
merge Y Y Y Y
total Y Y Y N
220 CHAPTER 11. CASE STUDY: CRDTS
Since increment and get both use the same binary operation (addition) it’s
usual to require the same commutative monoid for both.
11.3.1 Implementation
Cats provides a type class for both Monoid and CommutativeMonoid, but
doesn’t provide one for bounded semilattice¹. That’s why we’re going to im‐
plement our own BoundedSemiLattice type class.
import cats.kernel.CommutativeMonoid
Implement BoundedSemiLattice type class instances for Ints and for Sets.
The instance for Int will technically only hold for non‐negative numbers, but
you don’t need to model non‐negativity explicitly in the types.
When you implement this, look for opportunities to use methods and syn‐
tax on Monoid to simplify your implementation. This is a good example of
how type class abstractions work at multiple levels in our code. We’re using
monoids to design a large component—our CRDTs—but they are also useful in
the small, simplifying our code and making it shorter and clearer.
We’ve created a generic GCounter that works with any value that has in‐
stances of BoundedSemiLattice and CommutativeMonoid. However we’re
still tied to a particular representation of the map from machine IDs to values.
There is no need to have this restriction, and indeed it can be useful to ab‐
stract away from it. There are many key‐value stores that we want to work
with, from a simple Map to a relational database.
There are a number of ways we can implement this. One approach is to de‐
fine a GCounter type class with dependencies on CommutativeMonoid and
222 CHAPTER 11. CASE STUDY: CRDTS
trait GCounter[F[_,_],K, V] {
def increment(f: F[K, V])(k: K, v: V)
(implicit m: CommutativeMonoid[V]): F[K, V]
object GCounter {
def apply[F[_,_], K, V]
(implicit counter: GCounter[F, K, V]) =
counter
}
Try defining an instance of this type class for Map. You should be able to reuse
your code from the case class version of GCounter with some minor modifi‐
cations.
The implementation strategy for the type class instance is a bit unsatisfying.
11.5. ABSTRACTING A KEY VALUE STORE 223
Although the structure of the implementation will be the same for most in‐
stances we define, we won’t get any code reuse.
One solution is to capture the idea of a key‐value store within a type class, and
then generate GCounter instances for any type that has a KeyValueStore
instance. Here’s the code for such a type class:
trait KeyValueStore[F[_,_]] {
def put[K, V](f: F[K, V])(k: K, v: V): F[K, V]
With our type class in place we can implement syntax to enhance data types
for which we have instances:
Now we can generate GCounter instances for any data type that has instances
of KeyValueStore and CommutativeMonoid using an implicit def:
The complete code for this case study is quite long, but most of it is boilerplate
setting up syntax for operations on the type class. We can cut down on this
using compiler plugins such as Simulacrum and Kind Projector.
11.6 Summary
In this case study we’ve seen how we can use type classes to model a simple
CRDT, the GCounter, in Scala. Our implementation gives us a lot of flexibility
and code reuse: we aren’t tied to the data type we “count”, nor to the data
type that maps machine IDs to counters.
The focus in this case study has been on using the tools that Scala provides,
not on exploring CRDTs. There are many other CRDTs, some of which operate
in a similar manner to the GCounter, and some of which have very different
11.6. SUMMARY 225
Solutions to Exercises
227
Appendix A
These steps define the three main components of our type class. First we
define Printable—the type class itself:
trait Printable[A] {
def format(value: A): String
}
object PrintableInstances {
implicit val stringPrintable = new Printable[String] {
def format(input: String) = input
}
229
230 APPENDIX A. SOLUTIONS FOR: INTRODUCTION
object Printable {
def format[A](input: A)(implicit p: Printable[A]): String =
p.format(input)
This is a standard use of the type class pattern. First we define a set of custom
data types for our application:
Then we define type class instances for the types we care about. These either
go into the companion object of Cat or a separate object to act as a names‐
pace:
import PrintableInstances._
Finally, we use the type class by bringing the relevant instances into scope
and using interface object/syntax. If we defined the instances in companion
objects Scala brings them into scope for us automatically. Otherwise we use
an import to access them:
A.3. PRINTABLE LIBRARY PART 3 231
Printable.print(cat)
// Garfield is a 41 year-old ginger and black cat.
object PrintableSyntax {
implicit class PrintableOps[A](value: A) {
def format(implicit p: Printable[A]): String =
p.format(value)
With PrintableOps in scope, we can call the imaginary print and format
methods on any value for which Scala can locate an implicit instance of
Printable:
import PrintableSyntax._
import java.util.Date
new Date().print
// error: could not find implicit value for parameter p: repl.Session.
App0.Printable[java.util.Date]
232 APPENDIX A. SOLUTIONS FOR: INTRODUCTION
// new Date().print
// ^^^^^^^^^^^^^^^^
First let’s import everything we need from Cats: the Show type class, the in‐
stances for Int and String, and the interface syntax:
import cats.Show
import cats.instances.int._ // for Show
import cats.instances.string._ // for Show
import cats.syntax.show._ // for show
Finally, we use the Show interface syntax to print our instance of Cat:
First we need our Cats imports. In this exercise we’ll be using the Eq type class
and the Eq interface syntax. We’ll bring instances of Eq into scope as we need
them below:
import cats.Eq
import cats.syntax.eq._ // for ===
We bring the Eq instances for Int and String into scope for the implementa‐
tion of Eq[Cat]:
There are four monoids for Boolean! First, we have and with operator && and
identity true:
235
236 APPENDIX B. SOLUTIONS FOR: MONOIDS AND SEMIGROUPS
Finally, we have exclusive nor (the negation of exclusive or) with identity true:
Showing that the identity law holds in each case is straightforward. Simi‐
larly associativity of the combine operation can be shown by enumerating
the cases.
Set intersection forms a semigroup, but doesn’t form a monoid because it has
no identity element:
Set complement and set difference are not associative, so they cannot be con‐
sidered for either monoids or semigroups. However, symmetric difference
(the union less the intersection) does also form a monoid with the empty set:
We can alternatively write the fold using Monoids, although there’s not a com‐
pelling use case for this yet:
import cats.Monoid
import cats.instances.int._ // for Monoid
import cats.syntax.semigroup._ // for |+|
Now there is a use case for Monoids. We need a single method that adds
Ints and instances of Option[Int]. We can write this as a generic method
that accepts an implicit Monoid as a parameter:
import cats.Monoid
import cats.syntax.semigroup._ // for |+|
We can optionally use Scala’s context bound syntax to write the same code in
a shorter way:
We can use this code to add values of type Int and Option[Int] as re‐
quested:
add(List(1, 2, 3))
// res10: Int = 6
B.5. ADDING ALL THE THINGS PART 3 239
Note that if we try to add a list consisting entirely of Some values, we get a
compile error:
This happens because the inferred type of the list is List[Some[Int]], while
Cats will only generate a Monoid for Option[Int]. We’ll see how to get
around this in a moment.
The semantics are similar to writing a Functor for List. We recurse over the
data structure, applying the function to every Leaf we find. The functor laws
intuitively require us to retain the same structure with the same pattern of
Branch and Leaf nodes:
import cats.Functor
241
242 APPENDIX C. SOLUTIONS FOR: FUNCTORS
Branch(Leaf(10), Leaf(20)).map(_ * 2)
// error: value map is not a member of repl.Session.App0.Branch[Int]
// Branch(Leaf(10), Leaf(20)).map(_ * 2)
// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Oops! This falls foul of the same invariance problem we discussed in Section
1.6.1. The compiler can find a Functor instance for Tree but not for Branch
or Leaf. Let’s add some smart constructors to compensate:
object Tree {
def branch[A](left: Tree[A], right: Tree[A]): Tree[A] =
Branch(left, right)
Tree.leaf(100).map(_ * 2)
// res9: Tree[Int] = Leaf(200)
Tree.branch(Tree.leaf(10), Tree.leaf(20)).map(_ * 2)
// res10: Tree[Int] = Branch(Leaf(20), Leaf(40))
To make the instance generic across all types of Box, we base it on the
Printable for the type inside the Box. We can either write out the complete
definition by hand:
We need a generic Codec for Box[A] for any given A. We create this by calling
imap on a Codec[A], which we bring into scope using an implicit parameter:
C.6. TRANSFORMATIVE THINKING WITH IMAP PART 3 245
At first glance this seems tricky, but if we follow the types we’ll see there’s only
one solution. We are passed a value of type F[A]. Given the tools available
there’s only one thing we can do: call flatMap:
trait Monad[F[_]] {
def pure[A](value: A): F[A]
We need a function of type A => F[B] as the second parameter. We have two
function building blocks available: the func parameter of type A => B and the
pure function of type A => F[A]. Combining these gives us our result:
trait Monad[F[_]] {
def pure[A](value: A): F[A]
247
248 APPENDIX D. SOLUTIONS FOR: MONADS
import cats.Id
Now let’s look at each method in turn. The pure operation creates an Id[A]
from an A. But A and Id[A] are the same type! All we have to do is return the
initial value:
pure(123)
// res7: Id[Int] = 123
The map method takes a parameter of type Id[A], applies a function of type
A => B, and returns an Id[B]. But Id[A] is simply A and Id[B] is simply B!
All we have to do is call the function—no boxing or unboxing required:
D.3. WHAT IS BEST? 249
map(123)(_ * 2)
// res8: Id[Int] = 246
The final punch line is that, once we strip away the Id type constructors,
flatMap and map are actually identical:
flatMap(123)(_ * 2)
// res9: Id[Int] = 246
This ties in with our understanding of functors and monads as sequencing type
classes. Each type class allows us to sequence operations ignoring some kind
of complication. In the case of Id there is no complication, making map and
flatMap the same thing.
Notice that we haven’t had to write type annotations in the method bodies
above. The compiler is able to interpret values of type A as Id[A] and vice
versa by the context in which they are used.
The only restriction we’ve seen to this is that Scala cannot unify types and
type constructors when searching for implicits. Hence our need to re‐type
Int as Id[Int] in the call to sumSquare at the opening of this section:
This is an open question. It’s also kind of a trick question—the answer depends
on the semantics we’re looking for. Some points to ponder:
250 APPENDIX D. SOLUTIONS FOR: MONADS
• In a number of cases, we want to collect all the errors, not just the first
one we encountered. A typical example is validating a web form. It’s a
far better experience to report all errors to the user when they submit
a form than to report them one at a time.
D.4 Abstracting
We can solve this using pure and raiseError. Note the use of type parame‐
ters to these methods, to aid type inference.
import cats.Eval
We’ll start by defining a type alias for Writer so we can use it with pure
syntax:
import cats.data.Writer
import cats.instances.vector._
import cats.syntax.applicative._ // for pure
42.pure[Logged]
// res11: Logged[Int] = WriterT((Vector(), 42))
Vector("Message").tell
// res12: Writer[Vector[String], Unit] = WriterT((Vector("Message"),
()))
Finally, we’ll import the Semigroup instance for Vector. We need this to map
and flatMap over Logged:
41.pure[Logged].map(_ + 1)
// res13: cats.data.WriterT[cats.package.Id, Vector[String], Int] =
WriterT(
// (Vector(), 42)
// )
When we call factorial, we now have to run the return value to extract the
log and our factorial:
// )
// res: Int = 120
We can run several factorials in parallel as follows, capturing their logs in‐
dependently without fear of interleaving:
Await.result(Future.sequence(Vector(
Future(factorial(5)),
Future(factorial(5))
)).map(_.map(_.written)), 5.seconds)
// res: scala.collection.immutable.Vector[cats.Id[Vector[String]]] =
// Vector(
// Vector(fact 0 1, fact 1 1, fact 2 2, fact 3 6, fact 4 24, fact
5 120),
// Vector(fact 0 1, fact 1 1, fact 2 2, fact 3 6, fact 4 24, fact
5 120)
// )
Our type alias fixes the Db type but leaves the result type flexible:
Remember: the idea is to leave injecting the configuration until last. This
means setting up functions that accept the config as a parameter and check it
against the concrete user info we have been given:
254 APPENDIX D. SOLUTIONS FOR: MONADS
def checkPassword(
username: String,
password: String): DbReader[Boolean] =
Reader(db => db.passwords.get(username).contains(password))
def checkLogin(
userId: Int,
password: String): DbReader[Boolean] =
for {
username <- findUsername(userId)
passwordOk <- username.map { username =>
checkPassword(username, password)
}.getOrElse {
false.pure[DbReader]
}
} yield passwordOk
The stack operation required is different for operators and operands. For clar‐
ity we’ll implement evalOne in terms of two helper functions, one for each
case:
D.11. POST‐ORDER CALCULATOR PART 2 255
Let’s look at operand first. All we have to do is push a number onto the stack.
We also return the operand as an intermediate result:
The operator function is a little more complex. We have to pop two operands
off the stack (having the second operand at the top of the stack)i and push
the result in their place. The code can fail if the stack doesn’t have enough
operands on it, but the exercise description allows us to throw an exception
in this case:
case _ =>
sys.error("Fail!")
}
We’ve done all the hard work now. All we need to do is split the input into
terms and call runA and value to unpack the result:
evalInput("1 2 + 3 4 + *")
// res15: Int = 21
The code for flatMap is similar to the code for map. Again, we recurse down
the structure and use the results from func to build a new Tree.
import cats.Monad
The solution above is perfectly fine for this exercise. Its only downside is that
Cats cannot make guarantees about stack safety.
import cats.Monad
import scala.annotation.tailrec
loop(List(func(arg)), Nil).head
}
}
branch(leaf(100), leaf(200)).
flatMap(x => branch(leaf(x - 1), leaf(x + 1)))
// res5: Tree[Int] = Branch(
// Branch(Leaf(99), Leaf(101)),
// Branch(Leaf(199), Leaf(201))
// )
for {
a <- branch(leaf(100), leaf(200))
b <- branch(leaf(a - 10), leaf(a + 10))
c <- branch(leaf(b - 1), leaf(b + 1))
} yield c
// res6: Tree[Int] = Branch(
// Branch(Branch(Leaf(89), Leaf(91)), Branch(Leaf(109), Leaf(111))),
// Branch(Branch(Leaf(189), Leaf(191)), Branch(Leaf(209), Leaf(211))
)
// )
The monad for Option provides fail‐fast semantics. The monad for List pro‐
vides concatenation semantics. What are the semantics of flatMap for a bi‐
nary tree? Every node in the tree has the potential to be replaced with a whole
subtree, producing a kind of “growing” or “feathering” behaviour, reminiscent
of list concatenation along two axes.
import cats.data.EitherT
import scala.concurrent.Future
261
262 APPENDIX E. SOLUTIONS FOR: MONAD TRANSFORMERS
"Bumblebee" -> 8,
"Hot Rod" -> 10
)
We request the power level from each ally and use map and flatMap to com‐
bine the results:
We use the value method to unpack the monad stack and Await and fold
to unpack the Future and Either:
E.4. MONADS: TRANSFORM AND ROLL OUT PART 4 263
import scala.concurrent.Await
import scala.concurrent.ExecutionContext.Implicits.global
import scala.concurrent.duration._
The semantics of flatMap are what give rise to the behaviour for List and
Either:
265
266 APPENDIX F. SOLUTIONS FOR: SEMIGROUPAL AND APPLICATIVE
List does have a Parallel instance, and it zips the List insted of creating
the cartesian product.
import cats.instances.list._
Folding right to left copies the list, leaving the order intact:
Note that we have to carefully specify the type of the accumulator to avoid
a type error. We use List.empty[Int] to avoid inferring the accumulator
type as Nil.type or List[Nothing]:
List(1, 2, 3).foldRight(Nil)(_ :: _)
// error: type mismatch;
// found : List[Int]
267
268 APPENDIX G. SOLUTIONS FOR: FOLDABLE AND TRAVERSE
// required: scala.collection.immutable.Nil.type
// List(1, 2, 3).foldRight(Nil)(_ :: _)
// ^^^^
map(List(1, 2, 3))(_ * 2)
// res9: List[Int] = List(2, 4, 6)
filter(List(1, 2, 3))(_ % 2 == 1)
// res11: List[Int] = List(1, 3)
import scala.math.Numeric
sumWithNumeric(List(1, 2, 3))
// res12: Int = 6
and one using cats.Monoid (which is more appropriate to the content of this
book):
import cats.Monoid
sumWithMonoid(List(1, 2, 3))
// res13: Int = 6
// List(1, 4),
// List(2, 3),
// List(2, 4)
// )
With three items in the input list, we end up with combinations of three Ints:
one from the first item, one from the second, and one from the third:
process(List(2, 4, 6))
// res12: Option[List[Int]] = Some(List(2, 4, 6))
process(List(1, 2, 3))
// res13: Option[List[Int]] = None
process(List(2, 4, 6))
// res17: ErrorsOr[List[Int]] = Valid(List(2, 4, 6))
process(List(1, 2, 3))
// res18: ErrorsOr[List[Int]] = Invalid(List("1 is not even", "3 is
not even"))
import cats.Id
trait UptimeClient[F[_]] {
def getUptime(hostname: String): F[Int]
}
Note that, because Id[A] is just a simple alias for A, we don’t need to refer to
the type in TestUptimeClient as Id[Int]—we can simply write Int instead:
273
274APPENDIX H. SOLUTIONS FOR: CASE STUDY: TESTING ASYNCHRONOUS CODE
import cats.Applicative
import cats.syntax.functor._ // for map
import cats.Monoid
We have to modify the type signature to accept a Monoid for B. With that
change we can use the Monoid empty and |+| syntax as described in Section
2.5.3:
277
278 APPENDIX I. SOLUTIONS FOR: CASE STUDY: MAP‐REDUCE
import cats.Monoid
import cats.syntax.semigroup._ // for |+|
Here is an annotated solution that splits out each map and fold into a separate
line of code:
iterable.foldLeft(Monoid[B].empty)(_ |+| _)
}
}
Await.result(result, 1.second)
// res14: Int = 1784293664
We can re‐use our definition of foldMap for a more concise solution. Note
that the local maps and reduces in steps 3 and 4 of Figure 9.4 are actually
equivalent to a single call to foldMap, shortening the entire algorithm as fol‐
lows:
Await.result(result, 1.second)
// res16: Int = 1784293664
import cats.Monoid
import scala.concurrent._
import scala.concurrent.duration._
import scala.concurrent.ExecutionContext.Implicits.global
values
.grouped(groupSize)
.toVector
.traverse(group => Future(group.toVector.foldMap(func)))
.map(_.combineAll)
}
Await.result(future, 1.second)
// res18: Int = 500500000
import cats.Semigroup
import cats.instances.list._ // for Semigroup
import cats.syntax.semigroup._ // for |+|
Note we don’t need a full Monoid because we don’t need the identity element.
We should always try to keep our constraints as small as possible!
283
284 APPENDIX J. SOLUTIONS FOR: CASE STUDY: DATA VALIDATION
We want to report all the errors we can, so we should prefer not short‐
circuiting whenever possible.
In the case of the and method, the two checks we’re combining are indepen‐
dent of one another. We can always run both rules and combine any errors
we see.
In the first we represent checks as functions. The Check data type becomes a
simple wrapper for a function that provides our library of combinator methods.
For the sake of disambiguation, we’ll call this implementation CheckF:
import cats.Semigroup
import cats.syntax.either._ // for asLeft and asRight
import cats.syntax.semigroup._ // for |+|
}
}
Let’s test the behaviour we get. First we’ll setup some checks:
check(5)
// res5: Either[List[String], Int] = Left(List("Must be < -2"))
check(0)
// res6: Either[List[String], Int] = Left(List("Must be > 2", "Must be
< -2"))
Excellent! Everything works as expected! We’re running both checks and ac‐
cumulating errors as required.
What happens if we try to create checks that fail with a type that we can’t
accumulate? For example, there is no Semigroup instance for Nothing. What
happens if we create instances of CheckF[Nothing, A]?
We can create checks just fine but when we come to combine them we get an
error we might expect:
While the ADT implementation is more verbose than the function wrapper
implementation, it has the advantage of cleanly separating the structure of
the computation (the ADT instance we create) from the process that gives it
meaning (the apply method). From here we have a number of options:
Because of its flexibility, we will use the ADT implementation for the rest of
this case study.
The implementation of apply for And is using the pattern for applicative func‐
tors. Either has an Applicative instance, but it doesn’t have the semantics
we want. It fails fast instead of accumulating errors.
import cats.Semigroup
import cats.data.Validated
import cats.syntax.apply._ // for mapN
This reuses the same technique for and. We have to do a bit more work in
the apply method. Note that it’s OK to short‐circuit in this case because the
choice of rules is implicit in the semantics of “or”.
import cats.Semigroup
import cats.data.Validated
import cats.syntax.semigroup._ // for |+|
import cats.syntax.apply._ // for mapN
import cats.data.Validated._ // for Valid and Invalid
J.6 Checks
If you follow the same strategy as Predicate you should be able to create
code similar to the below:
import cats.Semigroup
import cats.data.Validated
object Check {
final case class Map[E, A, B, C](
check: Check[E, A, B],
func: B => C) extends Check[E, A, C] {
It’s the same implementation strategy as before with one wrinkle: Validated
doesn’t have a flatMap method. To implement flatMap we must momentar‐
ily switch to Either and then switch back to Validated. The withEither
method on Validated does exactly this. From here we can just follow the
types to implement apply.
import cats.Semigroup
import cats.data.Validated
// other methods...
}
J.9 Recap
Here’s our final implementaton, including some tidying and repackaging of the
code:
import cats.Semigroup
import cats.data.Validated
import cats.data.Validated._ // for Valid and Invalid
import cats.syntax.semigroup._ // for |+|
import cats.syntax.apply._ // for mapN
J.9. RECAP 293
object Predicate {
final case class And[E, A](
left: Predicate[E, A],
right: Predicate[E, A]) extends Predicate[E, A]
import cats.Semigroup
import cats.data.Validated
import cats.syntax.apply._ // for mapN
import cats.syntax.validated._ // for valid and invalid
object Check {
final case class Map[E, A, B, C](
check: Check[E, A, B],
func: B => C) extends Check[E, A, C] {
J.9. RECAP 295
def apply(a: A)
(implicit s: Semigroup[E]): Validated[E, C] =
check(a) map func
}
def apply(a: A)
(implicit s: Semigroup[E]): Validated[E, C] =
check(a).withEither(_.flatMap(b => func(b)(a).toEither))
}
def apply(a: A)
(implicit s: Semigroup[E]): Validated[E, C] =
check(a).withEither(_.flatMap(b => next(b).toEither))
}
def apply(a: A)
(implicit s: Semigroup[E]): Validated[E, B] =
func(a)
}
def apply(a: A)
(implicit s: Semigroup[E]): Validated[E, A] =
pred(a)
}
def apply[E, A, B]
296 APPENDIX J. SOLUTIONS FOR: CASE STUDY: DATA VALIDATION
Here’s our reference solution. Implementing this required more thought than
we expected. Switching between Check and Predicate at appropriate places
felt a bit like guesswork till we got the rule into our heads that Predicate
doesn’t transform its input. With this rule in mind things went fairly smoothly.
In later sections we’ll make some changes that make the library easier to use.
(name, domain).validNel[String]
case _ =>
"Must contain a single @ character".
invalidNel[(String, String)]
})
def createUser(
username: String,
email: String): Validated[Errors, User] =
(checkUsername(username), checkEmail(email)).mapN(User)
createUser("Noel", "noel@underscore.io")
// res5: Validated[Errors, User] = Valid(User("Noel", "noel@underscore
.io"))
createUser("", "dave@underscore.io@io")
// res6: Validated[Errors, User] = Invalid(
// NonEmptyList(
// "Must be longer than 3 characters",
// List("Must contain a single @ character")
298 APPENDIX J. SOLUTIONS FOR: CASE STUDY: DATA VALIDATION
// )
// )
One distinct disadvantage of our example is that it doesn’t tell us where the
errors came from. We can either achieve that through judicious manipulation
of error messages, or we can modify our library to track error locations as well
as messages. Tracking error locations is outside the scope of this case study,
so we’ll leave this as an exercise to the reader.
J.11 Kleislis
Here’s an abbreviated definition of run. Like apply, the method must accept
an implicit Semigroup:
import cats.Semigroup
import cats.data.Validated
// other methods...
}
Here is the preamble we suggested in the main text of the case study:
Our username and email examples are slightly different in that we make use
of check() and checkPred() in different situations:
case _ =>
Left(error("Must contain a single @ character"))
})
Finally, we can see that our createUser example works as expected using
Kleisli:
def createUser(
username: String,
email: String): Either[Errors, User] = (
checkUsername.run(username),
checkEmail.run(email)
).mapN(User)
J.12. KLEISLIS PART 2 301
createUser("Noel", "noel@underscore.io")
// res2: Either[Errors, User] = Right(User("Noel", "noel@underscore.io
"))
createUser("", "dave@underscore.io@io")
// res3: Either[Errors, User] = Left(
// NonEmptyList("Must be longer than 3 characters", List())
// )
Hopefully the description above was clear enough that you can get to an im‐
plementation like the one below.
303
304 APPENDIX K. SOLUTIONS FOR: CASE STUDY: CRDTS
Implementing the instance for Set provides good practice with implicit meth‐
ods.
object wrapper {
trait BoundedSemiLattice[A] extends CommutativeMonoid[A] {
def combine(a1: A, a2: A): A
def empty: A
}
object BoundedSemiLattice {
implicit val intInstance: BoundedSemiLattice[Int] =
new BoundedSemiLattice[Int] {
def combine(a1: Int, a2: Int): Int =
a1 max a2
Here’s the complete code for the instance. Write this definition in the com‐
panion object for GCounter to place it in global implicit scope:
Here’s the code for the instance. Write the definition in the companion object
for KeyValueStore to place it in global implicit scope: