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.

### 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" `F`s or the two "outer" `F`s. This is easy to see with the `List` monad. If we have a `List` of `List`s of `List`s, 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)
``````

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)
}```

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

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.

##### 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 `M`s 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.

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)

def unit[A](a: => A): Reader[R,A] = ???
}
}```

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] =

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] =

And the meaning of `unit` is to ignore the argument:

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

"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 `Monoid`s. 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).

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 => _`.

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`.

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

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.