# Embracing Nondeterminism Part III: Imperative Computation

Estimated reading time: 21m 28s

Remember **functors** and **applicatives**? In my last post Embracing Nondeterminism Part II: Permitting or Halting Computation we explored how functors and applicatives abstract over **desired** and **undesired cases** of **contexts** in order to express control flow and permit independent computation. In this post we will explore **monads** and how to leverage their specific abstraction to express **imperative** control flow.

This post is part of a series:

- Embracing Nondeterminism Part I: Contexts and Effects
- Embracing Nondeterminism Part II: Permitting or Halting Computation
Embracing Nondeterminism Part III: Imperative Computation

*The code that accompanies this post may be found here.*

## Motivating monads as a design pattern

Recall the `Functor`

and `Applicative`

typeclasses:

```
trait Functor[F[_]] {
def map[A, B](fa: F[A])(f: A => B): F[B]
}
object Functor {
def apply[F[_]: Functor]: Functor[F] = implicitly[Functor[F]]
}
trait Applicative[F[_]] extends Functor[F] {
def pure[A](a: A): F[A]
def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
def map[A, B](fa: F[A]): F[B] =
ap(pure(f))(fa)
def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C] =
ap(ap(pure(f.curried))(fa))(fb)
def sequence[A](listFa: List[F[A]]): F[List[A]] =
.foldLeft(pure(List[A]()))((fListA, fa) => map2(fa, fListA)(_ :: _))
listFa}
object Applicative {
def apply[F: Applicative]: Applicative[F] = implicitly[Applicative[F]]
}
```

See

`Functor`

and`Applicative`

’s definitions in the sample repository.

`Functor`

abstracts over contexts’ **unknown cases** by *lifting* a function via `map()`

and applying it to instances of the term produced by the context if they exist. Control flow can’t be expressed using `map()`

because it does not permit the case of the context to be modified.

`Applicative`

can create contexts in the **desired case** via `pure()`

. It can also apply *lifted* functions to *lifted* arguments via `ap()`

if *both* contexts are in their **desired case**. `Applicative`

is capable of expressing control flow through `ap()`

because supplying either the lifted function or lifted argument in an **undesired case** will not permit further computation. The context in the **undesired case** is *propagated* instead.

The problem however is that `Applicative`

requires that *both* the lifted function and lifted argument supplied to `ap()`

be computed *before* deciding whether to permit or halt further computation. This means that regardless of whether one of the function or argument contexts successfully computes, if the other one fails then the succeeding computation will be discarded. Both of these contexts’ computation are independent, and `Applicative`

will only use them if they are both are in their **desired case**.

All functions derived from `ap()`

represent *all-or-nothing* operations accordingly, and there is no practical way of ordering the computation of the arguments or preventing computation of all arguments if any preceding arguments fail to compute. Therefore, totally imperative programming is not possible using `Applicative`

.

## Introducing imperative control flow

In order to restrict computation such that subsequent computation occurs only if previous computation succeeds, we must introduce a new abstraction over the cases of contexts.

What function might limit subsequent computations from running if a previous one has failed? There is one, and you’ve probably seen it out in the wild:

`def flatMap[F[_], A, B](fa: F[A])(f: A => F[B]): F[B]`

What `flatMap()`

does is allow for the injection of a context into a pipeline of computations to either permit computation to proceed or force it to halt. The function argument `f`

, which you supply, has full control of what case the returned context `F[B]`

should be in. If `F[B]`

is in the **undesired case**, then all further computations are skipped, *propagating* this **undesired case** instead.

Take for example this definition of a `filter()`

function from the sample repository’s `sbt console`

:

```
> :load console/imports.scala
scala
> def filter[A](fa: Option[A])(f: A => Boolean) = fa.flatMap {
scala| case a if f(a) => Some(a)
| case _ => None
| }
def filter[A](fa: Option[A])(f: A => Boolean): Option[A]
> filter(Some(4))(_ % 2 == 0)
scalaval res1: Option[Int] = Some(4)
> filter(Some(3))(_ % 2 == 0)
scalaval res2: Option[Int] = None
```

This example is only very simple. But it demonstrates the key enabling feature of `flatMap()`

: we are able to *choose* whether the context remains in its **desired case**. If we continue with this example, we can try chaining `map()`

to the context returned by it.

```
> filter(Some(4))(_ % 2 == 0).map(n => s"The square of even number $n is ${n * n}")
scalaval res3: Option[String] = Some(The square of even number 4 is 16)
> filter(Some(3))(_ % 2 == 0).map(n => s"The square of even number $n is ${n * n}")
scalaval res4: Option[String] = None
```

Thus we are able to gate `map()`

behind the case of the context we return from the `flatMap()`

we used in `filter()`

, enabling imperative control flow.

## Monads

The `flatMap()`

function is implemented using a new structure, a specialization of an applicative functor called a **monad**.

Monads are a specialization that arises in the type of `A`

contained within a context `F[_]`

:

- If
`A`

is an opaque type, then`F[A]`

is a**functor**. - If
`A`

is known to have type`A => B`

, that is, then`A`

is a function`F[A => B]`

is an**applicative**functor. - If
`A`

is known to have type`F[A]`

, then this means that`F[F[A]]`

is*nested within itself*and thus a**monad**.

The `Monad`

typeclass defines two functions, which by default are defined in terms of each other:

```
trait Monad[F[_]] extends Applicative[F] {
def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B] =
flatten(map(fa)(f))
def flatten[A](ffa: F[F[A]]): F[A] =
flatMap(fa => fa)
}
object Monad {
def apply[F[_]: Monad]: Monad[F] = implicitly[Monad[F]]
}
```

This means that in order to implement an instance of the `Monad`

typeclass, you must implement one of either `flatMap()`

or `flatten()`

or calling one will recurse until the stack overflows. Some contexts are best defined using one over the other, and you have the choice to pick between the two.

See here for the definition in the sample repository.

### Composing monads

`Monad`

also defines a special composition operator. Recall that functions may be composed together, as in `h = g ∘ f`

or *“h is g after f”*. This may be expressed in two ways in vanilla Scala. Try below using the sample repository’s `sbt console`

:

```
> val f: Int => String = n => (n * n).toString
scalaval f: Int => String = $Lambda$5252/0x000000010195e040@7a76dc63
> val g: String => Int = n => n.length
scalaval g: String => Int = $Lambda$5254/0x000000010195f840@3843085
> val h = g.compose(f)
scalaval h: Int => Int = scala.Function1$$Lambda$5244/0x0000000101958840@388b1b42
> h(3)
scalaval res1: Int = 1
> h(25)
scalaval res2: Int = 3
> val hh = f.andThen(g)
scala
> hh(3)
scalaval res3: Int = 1
> hh(25)
scalaval res4: Int = 3
```

Scala out of the box affords the `compose()`

and `andThen()`

functions for composing functions of the form of `A => B`

together. But these composition functions don’t work for the signature of `flatMap()`

, which operates on functions of the form of `A => F[B]`

.

There is a form of composition for monads known as *Kleisli composition*. This composition will lift the following function into the context returned by the previous function and apply it to the term contained within the context if the context is in the **desired case**. Kleisli composition is expressed using the *fish* or *arrow operator* `>=>`

which is defined in the sample repository as an extension operator on functions of the form `A => F[B]`

where `F[_]`

has an instance of `Monad`

:

```
implicit class KleisliCompositionOps[F[_], A, B](val f: A => F[B]) extends AnyVal {
def >=>[C](g: B => F[C])(implicit F: Monad[F]): A => F[C] =
(x: A) => F.flatMap(f(x))(g)
}
```

See here for the definition in the sample repository.

Kleisli composition is useful for monads in that from two or more `flatMap()`

-compatible functions a single function may be created that takes an unlifted argument and produces an output context as the result of applying each function in sequence first to the unlifted argument and then to each individual functions’ output contexts.

```
> :load console/imports.scala
scala
> val squareEvens: Int => Either[String, Int] = {
scala| case n if n % 2 == 0 => Either.right[String, Int](n * n)
| case n => Either.left[String, Int](s"$n is an odd number")
| }
val squareEvens: Int => Either[String,Int] = $Lambda$5278
> val piEvenLastDigit: Int => Either[String, Int] = { n =>
scala| val nPi = n * scala.math.Pi
| val lastDigit = nPi.toString.last.asDigit
| if (lastDigit % 2 == 0) {
| Either.right[String, Int](lastDigit)
| } else {
| Either.left[String, Int](s"$n * Pi's last digit is an odd number")
| }
| }
> val evensSquaredWithEvenLastDigitsOfPi = squareEvens >=> piEvenLastDigit
scalaval evensSquaredWithEvenLastDigitsOfPi: Int => Either[String,Int] = Monad$Syntax$KleisliCompositionOps$$$Lambda$5241
> evensSquaredWithEvenLastDigitsOfPi(2)
scalaval res1: Either[String,Int] = Right(2)
> evensSquaredWithEvenLastDigitsOfPi(23)
scalaval res2: Either[String,Int] = Left(23 is an odd number)
> evensSquaredWithEvenLastDigitsOfPi(48)
scalaval res3: Either[String,Int] = Left(2304 * Pi's last digit is an odd number)
```

Above we are using the composed function directly, but because it has the form of `A => F[B]`

we are able to apply it using `flatMap()`

as well:

```
> Either.right[String, Int](2).flatMap(evensSquaredWithEvenLastDigitsOfPi)
scalaval res4: Either[String,Int] = Right(2)
> Either.right[String, Int](19).flatMap(evensSquaredWithEvenLastDigitsOfPi)
scalaval res5: Either[String,Int] = Left(19 is an odd number)
> Either.right[String, Int](4).flatMap(evensSquaredWithEvenLastDigitsOfPi)
scalaval res6: Either[String,Int] = Left(16 * Pi's last digit is an odd number)
> Either.left[String, Int]("Nothing's gonna happen").flatMap(evensSquaredWithEvenLastDigitsOfPi)
scalaval res7: Either[String,Int] = Left(Nothing's gonna happen)
```

Thus Kleisli composition is to `flatMap()`

as function composition is to `map()`

, with the key difference being that the case of the context may be changed by any one of the composed functions. Kleisli composition is powerful in that entire processes may be composed into step-by-step operations and applied as a single unit to a context via `flatMap()`

or directly to an unlifted argument.

### The *for comprehension* and imperative programming

Scala provides a syntax sugar over `flatMap()`

in the form of the *for comprehension*. Any type that provides both the `map()`

and `flatMap()`

functions are able to participate in this syntax sugar, and it allows for monadic operations to be expressed as if they were written as procedural code. This means that you don’t have to rely on Kleisli composition alone to express complex flows of logic, and that you also aren’t limited to single-argument input/output pipelines of functions.

As a simple example, here are the above functions leveraged using a for comprehension:

```
> :load console/imports.scala
scala
> val squareEvens: Int => Either[String, Int] = {
scala| case n if n % 2 == 0 => Either.right[String, Int](n * n)
| case n => Either.left[String, Int](s"$n is an odd number")
| }
val squareEvens: Int => Either[String,Int] = $Lambda$5278
> val piEvenLastDigit: Int => Either[String, Int] = { n =>
scala| val nPi = n * scala.math.Pi
| val lastDigit = nPi.toString.last.asDigit
| if (lastDigit % 2 == 0) {
| Either.right[String, Int](lastDigit)
| } else {
| Either.left[String, Int](s"$n * Pi's last digit is an odd number")
| }
| }
> val evensSquaredWithEvenLastDigitsOfPi: Int => Either[String, Int] =
scala| n => for {
| squaredEvenN <- squareEvens(n)
| piEvenLastDigitN <- piEvenLastDigit(squaredEvenN)
| } yield piEvenLastDigitN
val evensSquaredWithEvenLastDigitsOfPi: Int => Either[String,Int] = $Lambda$5263
> evensSquaredWithEvenLastDigitsOfPi(2)
scalaval res1: Either[String,Int] = Right(2)
> Either.right[String, Int](2).flatMap(evensSquaredWithEvenLastDigitsOfPi)
scalaval res2: Either[String,Int] = Right(2)
> Either.left[String, Int]("Nothing's gonna happen").flatMap(evensSquaredWithEvenLastDigitsOfPi)
scalaval res3: Either[String,Int] = Left(Nothing's gonna happen)
```

The key thing that a for comprehension allows for is multiple arguments to be lowered from contexts and applied to a multi-argument function that returns another context. An example of such an operation might look like this:

```
def sendMarketingUpdate(updateId: Int, userId: Int): Future[MarketingUpdateStatus] =
for {
<- loadUser(userId)
user <- loadTemplate(updateId)
marketingTemplate <- composeEmailForUser(user, marketingTemplate)
composedEmail <- sendEmail(composedEmail)
result } yield result.toMarketingUpdateStatus
```

Because `composeEmailForUser()`

requires both a `user`

and `marketingTemplate`

, this operation function is more easily expressed using a for comprehension than Kleisli composition.

However you don’t have to abandon applicative functions when using for comprehensions. The above function may be written to independently load the user and template:

```
def sendMarketingUpdate(updateId: Int, userId: Int): Future[MarketingUpdateStatus] =
for {
(user, marketingTemplate) <- (loadUser(userId), loadTemplate(updateId)).tupled
<- composeEmailForUser(user, marketingTemplate)
composedEmail <- sendEmail(composedEmail)
result } yield result.toMarketingUpdateStatus
```

The code can be trimmed just a little bit more, as well:

```
def sendMarketingUpdate(updateId: Int, userId: Int): Future[MarketingUpdateStatus] =
for {
<- (loadUser(userId), loadTemplate(updateId)).mapN(composeEmailForUser)
composedEmail <- sendEmail(composedEmail)
result } yield result.toMarketingUpdateStatus
```

This means that with applicative functions, you can express imperative code to some degree by gating functions dependent on a set of inputs, such as `composeEmailForUser()`

, and lean on monad’s `flatMap()`

for when you need absolute ordering of computations. These two styles of computation thus complement each other.

## Becoming a Monad

In order to become a `Monad`

, an effect type must implement the typeclass. Let’s implement instances for the usual suspects, `Option`

, `Either`

, and `List`

. As `Monad`

is a specialization of `Applicative`

and thus also `Functor`

, we can simply upgrade our `Applicative`

instances to become `Monad`

s:

```
implicit val optionMonad: Monad[Option] = new Monad[Option] {
// keep existing definitions
override def flatten[A](ffa: Option[Option[A]]): Option[A] =
match {
ffa case Some(fa) => fa
case None => None
}
}
implicit def eitherMonad[X]: Monad[Either[X, *]] = new Monad[Either[X, *]] {
// keep existing definitions
override def flatten[A](ffa: Either[X, Either[X, A]]): Either[X, A] =
match {
ffa case Right(fa) => fa
case Left(x) => Left(x)
}
}
implicit val listMonad: Monad[List] = new Monad[List] {
// keep existing definitions
override def flatten[A](ffa: List[List[A]]): List[A] =
ffa.foldLeft(List[A]()) { (outerResult, as) =>
.foldLeft(outerResult) { (innerResult, a) =>
as:: innerResult
a }
}
.reverse
}
```

See the instances of

`Monad`

for`Option`

,`Either`

, and`List`

in the sample repository.

In the above example, I implemented the `Monad`

instances using `flatten()`

. These could alternatively be implemented using `flatMap()`

. You might try to do this if you wish as an exercise.

## Monad laws

How do we know that `Option`

, `Either`

, and `List`

’s `Monad`

instances are well-behaved as monads? Like functors, monads are formally defined in the higher math of category theory and expected to conform to a set of laws.

There are **three monad laws**, which must hold for all monads in addition to the applicative and functor laws.

**Preservation of left identity**: Kleisli composition of`pure()`

with a function of form`f: A => F[B]`

applied to an unlifted argument`a: A`

is the same as applying the unlifted argument directly to`f: A => F[B]`

.**Preservation of right identity**: Kleisli composition of a function of form`f: A => F[B]`

with`pure()`

applied to an unlifted argument`a: A`

is the same as applying the unlifted argument directly to`f: A => F[B]`

.**Associativity**: Kleisli composition of three functions`f: A => F[B]`

,`g: B => F[C]`

, and`h: C => F[D]`

applied to an argument`a: A`

produces the same result regardless of grouping:`(f >=> g) >=> h`

is the same as`f >=> (g >=> h)`

.

Note that `pure()`

is interpreted as the identity element of the monad, as it merely lifts a value into its context, unmodified.

### Defining monad laws as properties

The monad laws may be defined as `scalacheck`

properties, as previously for applicatives. These properties assert “for all” instances of a particular monad `F[_]`

, the properties should hold. We know we have a well-behaved monad if the property checks pass.

```
trait MonadLaws { this: Laws with ApplicativeLaws =>
implicit def arbitraryFA[F[_]: LiftedGen, A: Arbitrary]: Arbitrary[F[A]] = Arbitrary(arbitrary[A].lift)
/** Defined per Monad laws taken from the Haskell wiki:
* [[https://wiki.haskell.org/Monad_laws#The_three_laws]]
*
* These laws extend the Applicative laws, so `checkApplicativeLaws[F]()` should be
* executed alongside this function.
*
* The laws as defined here leverage Kleisli composition, which is defined
* using the operator `>=>` in terms of `flatMap()`, to better highlight the
* left and right identities and associativity that should be exhibited by
* the composition of monadic operations.
*
* @param TT The type tag of the context
* @tparam F The context type being tested
*/
def checkMonadLaws[F[_]: Monad: LiftedGen]()(implicit TT: TypeTag[F[Any]]): Unit = {
property(s"${TT.name} Monad composition preserves left identity") {
// The identity of Kleisli composition simply lifts a value into the
// context. Kleisli composition of a function after `pure()` when applied
// to a value will produce the same result as applying the function
// directly to the value.
forAll(for {
<- arbitrary[Int]
a <- arbitrary[Int => F[String]]
h } yield (a, h)) { case (a, h) =>
val leftIdentity = ((_: Int).pure[F]) >=> h
leftIdentity(a) mustBe h(a)
}
}
property(s"${TT.name} Monad composition preserves right identity") {
// The identity of Kleisli composition simply lifts a value into the
// context. Kleisli composition of `pure()` after a function when applied
// to a value will produce the same result as applying the function
// directly to the value.
forAll(for {
<- arbitrary[Int]
a <- arbitrary[Int => F[String]]
h } yield (a, h)) { case (a, h) =>
val rightIdentity = h >=> ((_: String).pure[F])
rightIdentity(a) mustBe h(a)
}
}
property(s"${TT.name} Monad composition is associative") {
// `flatMap()` and thus Kleisli composition are both associative.
// This means that your program may be factored with these operations
// in any arbitrary grouping and the output will be the same.
forAll(for {
<- arbitrary[Double]
a <- arbitrary[Double => F[String]]
f <- arbitrary[String => F[Int]]
g <- arbitrary[Int => F[Boolean]]
h } yield (a, f, g, h)) { case (a, f, g, h) =>
val assocLeft = (f >=> g) >=> h
val assocRight = f >=> (g >=> h)
assocLeft(a) mustBe assocRight(a)
}
}
}
}
```

See here for the definition of the trait.

Our laws specs can now extend this trait and assert that their tested contexts conform to the monad laws. For example, the laws spec for `Option`

:

```
class OptionLaws extends Laws with FunctorLaws with ApplicativeLaws with MonadLaws {
import Option.Instances._
implicit val optionLiftedGen: LiftedGen[Option] = new LiftedGen[Option] {
override def lift[A](gen: Gen[A]): Gen[Option[A]] =
.lzy(
Gen.oneOf(
Gen.const(None),
Gen.map(Some(_)),
gen)
)
}
[Option]()
checkFunctorLaws[Option]()
checkApplicativeLaws[Option]()
checkMonadLaws}
```

### Implications of the monad laws

You may have noticed that the characteristics of the monad laws are somewhat different from the functor and applicative laws. They build using composition directly, specifically Kleisli composition, but don’t assert that function composition generally is retained within their contexts the same way that functor or applicative’s laws do.

**Let’s reiterate the laws:**

*Left identity**Right identity**Associativity*

These laws specifically also define another typeclass called a **monoid**, which is a specialization of a **semigroup** that adds an *identity* or *empty* element. The identity element is special in that combining it with any other element produces that other element.

```
trait Monoid[M] extends Semigroup[M] {
def empty: M
}
object Monoid {
def apply[M: Monoid]: Monoid[M] = implicitly[Monoid[M]]
}
```

Monoids are nearly as common as semigroups, as not all semigroups are monoids, and you’ve probably used quite a few of them:

`List`

’s identity element is the empty`List()`

.`String`

’s identity element is the empty`""`

.`Int`

’s identity element is`0`

.`Set`

’s identity element is the empty`Set()`

.

The key difference between monads and these monoids above is that monads form an *additive function* in contrast to *additive data*. Functions of the form `A => F[B]`

are combinable using `>=>`

to produce new functions of the same form, and this operation is associative, which means that monads form semigroups under Kleisli composition. They form monoids as the `pure()`

function satisfies the identity element in that it doesn’t alter its argument when composed to either the left or right side of a function of the form `A => F[B]`

.

To be really pedantic, monads are functors. All functors in Scala are functors from Scala types into other Scala types, making them endofunctors because they map back into the same category: the category of Scala types.

This affirms an infamous joke:

Haskell gets some resistance due to the complexity of using monads to control side effects. Wadler tries to appease critics by explaining that

“a monad is a monoid in the category of endofunctors, what’s the problem?”– From James Iry’s “A Brief, Incomplete, and Mostly Wrong History of Programming Languages”

In addition to being monoids, Scala’s
`List`

and
`Set`

are also monads and I have asserted that they are well behaved with property checks.
`Option`

and `Either`

are also monads. You’ve probably been using them as such without realizing!

The real takeaway from the monad laws is that you get *imperative computation as a composable structure*. You retain referential transparency in that associativity guarantees that your operations may be grouped arbitrarily, allowing you to factor the steps of your program with a large degree of freedom.

## What is enabled by monads?

The `flatMap()`

function primarily enables imperative programming through abstraction. It strictly requires that its current context be evaluated into its **desired case** before applying its function argument against the term it contains. If the context is in the **undesired case**, then all subsequent computation halts and this case *propagates* instead. Thus, in contrast to applicative’s *all-or-nothing* operations, monads offer *one-after-another* operations. Both evaluation styles complement each other and may be freely mixed, of course.

### Beware the imperative trap

Because monads allow you to express functional programming in a style that closely mirrors procedural code, especially within the syntax of the for comprehension, it’s very easy to fall into a trap of procedural spaghetti even though you’re using a functional programming abstraction. This occurs because for comprehensions allow you to expose multiple terms and pass them around at varying points within the for comprehension, mimicking procedural state-passing:

```
def performTransaction(accountNo: Long, amount: Currency): Future[Unit] =
for {
<- loadAccount(accountNo)
account <- beginTransaction(account)
transaction <- getBalance(account)
balance = balance + amount
newBalance <- {
_ if (newBalance < Currency.from(0)) {
endTransaction(transaction)
.flatMap(_ => failTransaction("Insufficient funds"))
} else {
updateBalance(newBalance)
.flatMap(_ => endTransaction(transaction))
}
}
} yield ()
```

This code would be hard to refactor as there’s a lot of arguments being passed around. It’s procedural code wrapped in a for comprehension! A smell in particular is a `Unit`

-return, as it indicates something is causing side-effects with no way to sense what actions have been performed or what state the total operation finished in.

## Going forward

These three abstractions, **functors**, **applicatives**, and **monads**, are just the beginning to a rich series of tools that you can leverage to express solid, maintainable, and provable programs. But you may have noticed a few capabilities are missing so far in this series, such as how to:

*Raise errors*, specifically as**undesired cases**, agnostic of context.*Recover from errors*, transforming**undesired cases**to**desired**, agnostic of context.*Attempt an alternate operation*if the first one fails.*Collect effectful operations*agnostic of container.- Allow for
*partial successes and failures*within collective operations. *Compose effect types*to take advantage of their combined characteristics.*Encode DSLs*as effects.

In my next post, we will explore **raising and recovering from errors** agnostic of context, so that your code may abstract against typeclasses but still be able to force and recover from **undesired cases**.

Please share with me your thoughts and feedback!