Chapter 11: Monads

Contents

• Notes: Chapter notes and links to further reading related to the content in this chapter
• FAQ: Questions related to the chapter content. Feel free to add questions and/or answers here related to the chapter.
• Links: Links to more reading

Notes

Monad laws through join

There is a formulation of the monad laws that we don't discuss in the chapter. We talk about the associative law in terms of flatMap and compose (Kleisli composition), but we can also state it in terms of join:

join(join(x)) == join(map(x)(join))

That is, if we have a value x of type F[F[F[A]]], we can join twice to get F[A], or we can map join over the outer F and then join the result of that.

This is saying that in "flattening" F[F[F[A]]] to F[A], it should not matter whether we first join the two "inner" Fs or the two "outer" Fs. This is easy to see with the List monad. If we have a List of Lists of Lists, like this...

val x: List[List[List[Int]]] =
  List(List(List(1,2), List(3,4)), List(List(5,6), List(7,8)))

...it should not matter whether we flatten the inner lists or the outer lists first:

scala> val y1 = x.flatten
y1: List[List[Int]] = List(List(1, 2), List(3, 4), List(5, 6), List(7, 8))

scala> val y2 = x.map(_.flatten)
y2: List[List[Int]] = List(List(1, 2, 3, 4), List(5, 6, 7, 8))

scala> y1.flatten
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

scala> y2.flatten
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

This is the same as saying that in the expression ((1 + 2) + (3 + 4)) + ((5 + 6) + (7 + 8)), it doesn't matter whether we remove the inner brackets first to get (1 + 2 + 3 + 4) + (5 + 6 + 7 + 8) or the outer brackets first to get (1 + 2) + (3 + 4) + (5 + 6) + (7 + 8). In both cases we end up with 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8. The reason it doesn't matter is that + is associative. So then it's easy to see how the monad law is an associative law.

The identity laws in terms of join are similarly simple:

join(unit(x)) == x      // left identity
join(map(x)(unit)) == x // right identity

In terms of the list monad as above, the identity laws are saying that we can add brackets either on the inside or the outside. Whichever we do, join will behave the same way:

scala> val x = List(1,2,3)
x: List[Int] = List(1, 2, 3)

scala> List(x).flatten
res0: List[Int] = List(1, 2, 3)

scala> x.map(List(_)).flatten
res1: List[Int] = List(1, 2, 3)

Monads in Category Theory

In Category Theory, a Monad is a functor equipped with a pair of natural transformations satisfying the laws of associativity and identity.

What does this mean? If we restrict ourselves to the category of Scala types (with Scala types as the objects and functions as the arrows), we can state this in Scala terms.

A Functor is just a type constructor for which map can be implemented:

trait Functor[F[_]] {
  def map[A,B](fa: F[A])(f: A => B): F[B]
}

A natural transformation from a functor F to a functor G is just a polymorphic function:

trait Transform[F[_], G[_]] {
  def apply[A](fa: F[A]): G[A]
}

The natural transformations that form a monad for F are unit and join:

type Id[A] = A

def unit[F](implicit F: Monad[F]) = new Transform[Id, F] {
  def apply(a: A): F[A] = F.unit(a)
}

def join[F](implicit F: Monad[F]) = new Transform[({type f[x] = F[F[x]]})#f, F] {
  def apply(ffa: F[F[A]]): F[A] = F.join(ffa)
}

Monads and monoids

Monoids and monads are connected in various ways in category theory.

The monad for monoids

The List monad can be seen as a theory about monoids. Specifically, the _.flatten (monadic join) and List(_) (monadic unit) functions witness that we can add and remove parentheses in a monoid expression. That is, the parenthesization of an expression like 1 + 2 + 3 + 4 doesn't matter. The monad associativity law means that we can remove parentheses in any order we like, and the identity law means we can add them wherever we want.

See Rúnar's article, "More on monoids and monads" for more information about this connection.

Kleisli categories

Both monoids and monads form categories. In fact, we can see a category as a generalized monoid. Observe that with a monoid M, we can view each element of the monoid as a function of type M => M. For example, in the Int monoid with addition, these elements are (_ + 0), (_ + 1), (_ + (-1)), etc. Then the composition of these functions is the operation of the monoid. We can generalize this notion to consider not just the type M, but all types (A, B, C, etc.) and functions not just of type M => M, but A => B for any types A and B. Then ordinary function composition is an associative operation, with an identity element which is the identity function that just returns its argument. This more general notion does not form a monoid, but a category which is more general. Specifically, it's the category of Scala types with function composition. Even more generally, whenever we have arrows (a generalized notion of functions) whose composition is associative and has an identity element, we have a category.

A monad F can be described by what's called a Kleisli category. The objects of this category are the ordinary Scala types, but the arrows are Kleisli arrows. That is, every arrow in this category is not of the general form A => B, but of the more specific form A => F[B]. The composition of these arrows is Kleisli composition (given by the compose combinator in the chapter) and the identity for Kleisli composition is monadic unit. Every monad forms a Kleisli category in this way.

A monad is a monoid in a category of endofunctors

A monad is also a kind of monoid. If we think of a type like (M, M) => M as M² => M (taking 2 Ms or the product of M with itself), and M as 1 => M (where 1 is the Unit type), then we can think of a type like F[F[A]] => F[A] as F²[A] => F[A] or just F² ~> F (where ~> denotes a natural transformation) and A => F[A] as 1[A] => F[A] (where 1 is the identity functor) or just 1 ~> F:

	zero/unit	op/join
Monoid[M]	1 => M	M² => M
Monad[F]	1 ~> F	F² ~> F

It's now clear that these are the same kind of thing, except Monoid[M] is operating in a category where the objects are Scala types and the arrows are Scala functions, and Monad[F] is operating in a category where the objects are Scala functors and the arrows are natural transformations.

See this StackOverflow question and its answers: http://stackoverflow.com/questions/3870088/a-monad-is-just-a-monoid-in-the-category-of-endofunctors-whats-the-problem.

Reader monad

At the end of the chapter we have an exercise for the reader to implement the following monad:

case class Reader[R, A](run: R => A)

object Reader {
  def readerMonad[R] = new Monad[({type f[x] = Reader[R,x]})#f] {
    def unit[A](a: => A): Reader[R,A] = ???
    def flatMap[A,B](st: Reader[R,A])(f: A => Reader[R,B]): Reader[R,B] = ???
  }
}

This is the reader monad. It is called that because it has the ability to read a value of type R. In addition to the operations common to all monads (flatMap, join, map, unit, etc), it has a primitive operation, read:

def read[R]: Reader[R, R] = Reader(r => r)

Note that this is just the identity function!

In the Scalaz library, this operation is called ask and is generalized to any reader-like structure (any implementation of MonadReader) rather than being specific to Reader.

The meaning of map in Reader is function composition:

def map[R,A,B](f: A => B): Reader[R, A] => Reader[R, B] =
  r => Reader(f compose r.run)

The meaning of join is to pass the same argument as both parameters to a binary function:

def join[R,A](x: Reader[R, Reader[R, A]]): Reader[R, A] =
  Reader(r => x.run(r).run(r))

And the meaning of unit is to ignore the argument:

def unit[R,A](a: A): Reader[R, A] = Reader(_ => a)

The reader monad subsumes (and is simpler than) dependency injection. See Rúnar's talks on dependency injection with the reader monad:

"Dead-simple dependency inection", from the 2012 Northeast Scala Symposium in Boston

"Lambda: the ultimate dependency injection framework", from the 2012 YOW! Summer Conference in Brisbane

See also Tony Morris's talk "Dependency injection without the gymnastics" from ETE 2012.

Eilenberg-Moore categories

Another categorical view of monads is through Eilenberg-Moore categories. The EM category of a monad is the category of its algebras.

For example, the algebras for the List monad are Scala Monoids. The EM category of the List monad is the category with monoids as its objects and monoid morphisms (see chapter 10) as its arrows.

In general, the EM category for a monad can be found by the following method (source: Theory Lunch):

1. An F-algebra for the monad F is a type A together with a function a: F[A] => A such that a(unit(x)) == x and a(join(x)) == a(map(x)(a)).
2. A morphism of F-algebras from an F-algebra a: F[A] => A to an F-algebra b: F[B] => B is a function f: A => B such that b(map(x)(f)) == f(a(x)).
3. The Eilenberg-Moore category for the monad F is the category with F-algebras as objects, and morphisms between F-algebras as arrows. The identity arrow is just the identity function, and composition of arrows is ordinary function composition.

We can see how a Monoid[A] is precisely a List-algebra by this definition:

def fold[A](implicit M: Monoid[A]): List[A] => A =
  _.foldRight(M.zero)(M.op)

It is a List-algebra because fold(List(x)) == x (that is, putting something in a list and then folding that list is a no-op). And fold(x.flatten) == fold(x.map(fold.apply)) (that is, concatenating a bunch of lists and folding the concatenated list is the same as folding a bunch of lists and then folding the list of the results of those folds).

This is a sense in which "List is the monad for monoids."

We can find the EM category for Option (thanks, Edward Kmett) easily. Every Option-algebra of type Option[A] => A is given by some value a of type A and is implemented by _.getOrElse(a). So an object in the EM category for Option is a Scala type A together with a distinguished value a:A. An arrow in this category takes that value a:A to another value b:B. So it's a function f: A => B that satisfies o.map(f).getOrElse(b) == f(o.getOrElse(a)) for all o: Option[A]. That is, it's just a function that returns b when given a. In other words, Option is the monad for pointed sets.

The EM category for the Reader[R,_] or R => _ monad is the category with objects that are each given by a value r:R, implemented by _(r).

The monad whose EM category is just the category of Scala types is Id (the identity monad).

Adjunctions

An adjunction consists of a pair of functors in a certain relationship to one another. Stated in Scala, it is an implementation of this interface:

trait Adjunction[F[_], G[_]] {
  def unit[A](a: A): G[F[A]]
  def counit[A](fga: F[G[A]]): A

  def F: Functor[F]
  def G: Functor[G]
}

counit is pronounced "co-unit", not "cow-knit".

We say that F is left adjoint to G, written F ⊣ G in mathematical notation.

There are two laws of adjunctions:

1. counit(F.map(x)(unit)) == x
2. G.map(unit(x))(counit) == x

Another way to view an adjunction is that there is an isomorphism between the types F[A] => B and A => G[B]:

def leftAdjunct[A,B](k: F[A] => B): A => G[B] =
  a => G.map(unit(a))(k)
def rightAdjunct[A,B](k: A => G[B]): F[A] => B =
  fa => counit(F.map(fa)(k))

An adjunction has the property that G[F[_]] is a monad:

def join[A](g: G[F[G[F[A]]]]): G[F[A]] =
  G.map(g)(counit)
def map[A,B](g: G[F[A]])(f: A => B): G[F[B]] =
  G.map(F.map(f))
def flatMap[A,B](g: G[F[A]])(f: A => G[F[B]]): G[F[B]] =
  join(map(g)(f))

For example, the State monad is formed by the adjoint functors (_, S) and S => _.

In fact, every monad is formed by an adjunction.

Comonads

Dually, the composite functor F[G[A]] is a comonad. A comonad is exactly like a monad, except the direction of the function arrows is reversed:

trait Comonad[F[_]] {
  def counit[A](a: F[A]): A
  def extend[A,B](a: F[A])(f: F[A] => B): F[B]
}

Instead of a unit that goes from A to F[A], we have a counit that goes from F[A] to A. And instead of a flatMap that takes a function of type A => F[B], we have extend that takes a function going the other way: F[A] => B.

A simple example of a comonad is the reader comonad:

type Coreader[R,A] = (A,R)

val readerComonad[R] = new Comonad[({type f[x] = Coreader[R,x]})#f] {
  def counit[A](a: (A,R)) = a._1
  def extend[A,B](a: (A,R))(f: (A,R) => B) = 
    (f(a), a._2)
}

How is this a reader? What is it reading? Well, there is a primitive read operation:

def read[R](ar: (A,R)): R = ar._2

The reader comonad models computations that have a context (or configuration) of type R. The value computed so far is the A, and we can always read the context to copy it into our working memory. It supports the same operations as the reader monad and serves essentially the same purpose.

Note that unlike the reader monad which is a function R => A, the reader comonad is a pair (A, R). The latter is left adjoint to the former and their adjunction forms the State monad.

But their adjunction therefore also forms a comonad! The "dual" of the State monad in this sense is the Store comonad

case class Store[S](s: S, f: S => A)

The Store comonad essentially models a Moore machine. The current state of the machine is s, and the output function is f. Note that the output depends only on the current state.

The type A => Store[S, A] is one possible representation of a Lens.

Other useful comonads include Rose Trees, Nonempty lists, zippers over lists, zippers over trees, and cofree comonads.

Links

• The essence of functional programming by Philip Wadler.
• Notions of computation and monads by Eugenio Moggi.

FAQ

Feel free to add your questions here.