# Monads

#### March 6, 2024

Monads are **data types**^{1} that expose methods for *chaining*, typically for the sake of **abstracting state**.

More concretely, a monad is a type m where there exist the two^{2} functions:

```
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m b
```

The above signatures might be confusing, because they make use of several of Haskell’s language features.

*Infix Operators*:is a two-argument function that can be called with infix notation (i.e.`(>>=)`

)`x >>= y`

*Parametric*Polymorphism: m is a generic type that takes single type parameter^{3}; in this case, the paramaters themselves (and`a`

) are also generic`b`

*Currying*: every function in Haskell takes a single argument; the illusion of multiple-argument functions is made when functions return other functions:doesn’t actually take two arguments`(>>=)`

The bottom line is that ** m** is a data type that is generic over exactly one other type (i.e. the “vector” in “vector<T>”, the “Maybe” in “Maybe a”, or the “[]” in “[a]”), and the class statement declares that any

**is a monad so long as it declares itself an instance of**

`m`

**and provides the functions**

`Monad`

**and**

`(>>=)`

**.**

`return`

This is all pretty abstract, and it’s not clear how these type-signatures imply chaining or state-abstraction.

## Contextualization

Say we have a chain of functions that transform some data of type ** A** to type

**by sequentially applying the functions f, g, and h.**

`D`

```
f g h
A -----> B ------> C -----> D
f :: A -> B
g :: B -> C
h :: C -> D
(\x -> h (g (f x))) :: A -> D
```

Say we want to maintain some shared state of type ** E** over these function calls (

**,**

`f`

**, and**

`g`

**, can read or modify that data, as if it were a global variable).**

`h`

```
f g h
A -----> B ------> C -----> D
E _/ \______/ \_______/ \__ E
f :: A -> B
g :: B -> C
h :: C -> D
```

This drawing doesn’t quite work out, though, since the external arrows hovering below the function calls (passing ** E** between functions whose signatures don’t involve

**) are impure. It isn’t possible to have a pure function**

`E`

**that can read/write external data. So in order to have this “global” state, the passing of**

`f :: A -> B`

**must be embedded within the type-signatures/function-calls.**

`E`

In this case, this can be done by introducing a tuple.

```
f g h
(A, E) -----> (B, E) -----> (C, E) -----> (D, E)
f :: (A, E) -> (B, E)
g :: (B, E) -> (C, E)
h :: (C, E) -> (D, E)
(\x -> h (g (f x))) :: (A, E) -> (D, E)
```

We can also define a monad called ** EState** that can do a similar computation.

```
f >>= g >>= h
A -----> EState B -----> EState C -----> EState D
f :: A -> EState B
g :: B -> EState C
h :: C -> EState D
(>>= g) :: EState B -> EState C
(>>= h) :: EState C -> EState D
(\x -> f x >>= g >>= h) :: A -> EState D
```

This almost exactly lines up with the tuple version, except the definitions of ** f**,

**, and**

`g`

**, namely that their parameters are not wrapped in**

`h`

**(which creates an assymmetry in the composition). This is explained by the definition of**

`EState`

**.**

`EState`

```
newtype EState a = EState (E -> (a, E))
runEState :: EState a -> E -> (a, E)
runEState (EState run) = run
-- The above could be replaced by (using record notation):
-- newtype EState a = EState { runEState :: (E -> (a, E)) }
instance Monad EState where
-- (>>=) :: EState a -> (a -> EState b) -> EState b
(>>=) esa f = EState internal
where -- internal :: E -> (b, E)
internal state = let (a, state') = runEState esa state
in runEState (f a) state'
-- return :: a -> EState a
return x = EState (\state -> (x, state))
```

The key realization here is that ** EState A** does not store the same data as

**.**

`(A, E)`

**stores a concrete value of**

`(A, E)`

**and**

`A`

**, while**

`E`

**is a stores a function of type**

`EState a`

**. Bind (**

`(E -> (a, E))`

**) tacks on a function call (the RHS) onto the function encapsulated into the**

`(>>=)`

**.**

`EState`

The following more clearly illustrates the underlying type of the monad.
The resulting ** EState D** value encapsulates a function which is the (indirect) composition of

**,**

`f`

**, and**

`g`

**. Applying that underlying function (to the initial state) passes the state through the whole**

`h`

**-**

`f`

**-**

`g`

**pipeline, and yields the resulting value and state.**

`h`

```
f :: A -> EState B
x :: A
(f x) :: EState B -- (E -> (B, E))
(>>=) :: Monad m => m b -> (b -> m c) -> m c
g :: B -> EState C
(f x >>= g) :: EState C -- (E -> (C, E))
-- f x >>= g = EState internal
-- where internal state = let (a, state') = runEState (f x) state
-- in runEState (g a) state' -- add g to the chain
h :: C -> EState D
(f x >>= g >>= h) :: EState D -- (E -> (D, E))
-- f x >>= g >>= h = EState internal
-- where internal state = let (b, state') = runEState (f x >>= g) state
-- in runEState (h b) state' -- add h to the chain
-- which is equivalent to...
-- f x >>= g >>= h = EState internal
-- where internal state = let (a, state') = runEState (f x) state
-- (b, state'') = runEState (g a) state'
-- in runEState (h b) state'' -- add h to the chain
```

The only piece that’s left is how the state can be read/written.
This is also done by chaining ** EState**s.

```
get :: EState E
get = EState (\state -> (state, state))
put :: E -> EState ()
put newState = EState (\_ -> ((), newState))
```

** get** and

**use their knowledge of the underlying structure of**

`put`

**to make an interface**

`EState`

^{4}for users to reach into the internal value (in this case, adding functions to the chain that read/write the state instead of just ignoring it).

Below is an example of how they can be used.

```
type E = Int
-- square the state, then return it
squareTheState :: EState Int
squareTheState = get >>= \s -> (put (s * s) >>= \_ -> return (s * s))
-- get >>= \s -> (put (s * s) >>= \_ -> return (s * s) = EState internal
-- where internal state = let (a, state') = runEState get state
-- in runEState (lambda1 a) state'
-- lambda1 s = EState internal1
-- where internal1 state1 = let (a1, state1') = runEState (put (s * s)) state1
-- in runEState (lambda2 a1) state1'
-- lambda2 _ = EState internal2
-- where internal2 state2 = runEState (return (s * s)) state2
```

### Do-Notation

Bind (** (>>=)**) is so commonly used (and creates such a syntactic inconvenience) that there’s a special syntax for it.

```
do x <- y
(...)
-- is the same as
y >>= \x -> (...)
```

And

```
do y
(...)
-- is the same as
y >>= \_ -> (...)
```

The following is an equivalent definition of ** squareTheState**, written with do-notation instead of bind.

```
squareTheState :: EState Int
squareTheState = do s <- get
put (s * s)
return (s * s)
```

### Key Takeaway

Monads allow us to abstract away the management of “state” via chaining. We can have the effect of the below ascii-image (where an external factor controls the execution of pure functions) by wrapping the return-values of functions in monads, and, as a result, not have to worry about the underlying chaining-details when actually writing the functions.

```
f g h
A -----> B ------> C -----> D
_/ \______/ \_______/ \__
```

## Monads in Action

### Non-Function Data

Like ** EState**, many monads in standard libraries encapsulate functions:

- IO
- State
- Reader
- Writer

There’s no constraint on what can be a monad, though, so long as it fulfills the minimal required functions.

** Maybe** and

**are both ambivalent: when chained together, they always propagate the first failure.**

`Either`

```
instance Monad Maybe where
(Just x) >>= k = k x
Nothing >>= _ = Nothing
instance Monad (Either e) where
Left l >>= _ = Left l
Right r >>= k = k r
```

### Not Confusing At All

There are some particularly fringe monad^{5} instances in the standard libraries too: it seems that if there is any remotely^{6} logical implementation for a given data type, it becomes a monad.

This can occasionally be useful, but it seems dangerously close to obfuscation at times.

For instance, ** []** is a Monad.
Try to guess what the following lines do without looking at the definition.

```
[[1.3, 5.6, 7.8], [1.0, 3.4, 1.4]] >>= reverse
[1, 2, 3] >>= \x -> replicate x x
["abc", "def", "ghi"] >>= id
```

^{7}

Functions (the type ** ((->) r)**) are also monads:

**is the flipped Σ combinator (which is not all that useful).**

`(>>=)`

```
(>>=) :: m a -> (a -> m b) -> m b
(>>=) :: (r -> a) -> (a -> r -> b) -> r -> b -- for ((->) r)
duplicateHead :: [a] -> [a]
duplicateHead = head >>= (:)
adjacentDifference :: Num a => [a] -> [a]
adjacentDifference = tail >>= zipWith (-)
```

The term “monad” comes from category theory, where it has a slightly different definition (it’s defined in terms of categories, not data). All definitions of category-theory constructs in this post refer to their Haskell equivalents. ↩︎

In Haskell,

must also be instances of`Monads`

. ↩︎`Applicative`

The type itself (when used in a signature) takes the parameter: this is another way of saying “m has kind * -> *” ↩︎

In general, due to the definition of Monad, only the monadic value (the

in`a`

) is accessible using the built-in Monadic functions (`m a`

,`>>=`

, and their variants). ↩︎`return`

The same is true for Applicative and Functor, and probably many more such typeclasses. Some of these actually are pretty useful: the instance of Applicative for functions defines the

operator to be the S combinator, and`<*>`

to be the Φ combinator. See Conor Hoekstra’s Combinator Table for more. ↩︎`liftA2`

A long-time Haskeller might argue that most instances are trivially derivable from the type signatures. This might be true, but that rarely implies that they’re trivially understood in context of other complex code. With great power comes great responsibility. ↩︎

The type-signature makes it easier:

. It’s a flipped version of concatMap. ↩︎`[a] -> (a -> [b]) -> [b]`