### An Algebraic Data Type's Monad

I watched Dr. Emily Reihl’s Compose Conf talk^{1} last night and a new intuition emerged. The purpose of the talk was to explicate the categorical notion of a monad, and while watching it, I was struck with the realization of how a monad arises from an algebraic data type.

## Prereqs

In her talk, she first discusses $T$ as a computation, and defines a $T$ as a monad: something that can take an $A$ and lift it to a $T(A)$, like this:

*NB: There is another operation that comes with a monad, bind, but we’ll skip that for now.*

The canonical example used through the first half of the talk is a $List$: A function from $A \rightarrow T(A)$ could be a function from an $A$ to a $List$ of $A$’s where $T$ is the *computation* which constructs a list of $A$’s. That is, $A \rightarrow T(A)$ is simply a more general version of $A \rightarrow List(A)$.

She goes on to use the notation of $\leadsto$ to denote a “program” which contains one of these lift operations, but with $\leadsto$, we elide the $T$:

This notation is meant to denote a “weak” map between $A$ and $B$, in that it’s not a complete $A \rightarrow B$, due to the fact that it requires the computation $T$. This lift from $A$ to $T$ of $B$ is called a *Kleisli* arrow.

## An ADT Monad

Later in the talk, she defines a function from $A$ to $A + \bot$:

This should look familiar — it contains a $+$ after all! It’s an algebraic data type (ADT) — a sum type to be specfic. It can give us either an $A$ or ${\bot}$; $\bot$ means “bottom” or `false`

in this context. It would look something like this in Haskell:

```
data Maybe a = Nothing | Just a
f :: a -> Maybe a
```

And as we know, `Maybe`

admits a monad where if we have an `a`

, we apply our lift to it to get a `Just a`

. In Haskell, this lift is called `return`

, and made available in the Monad typeclass:

```
return :: Monad m => a -> m a
```

Which, if we squint, looks an awful lot like `A -> T(A)`

. For edification purposes, our definition of `return`

for `Maybe`

and the other requisite pieces of a Monad in Haskell are below.

```
instance Monad Maybe where
return = Just
(Just x) >>= f = f x
Nothing >>= _ = Nothing
```

If you’re still squinting, you can start to see how:

- Our ADT becomes $T$, the
*computation*which can give us either our`a`

, or`Nothing`

. - Using Dr. Reihl’s notation, we could denote
`f`

mathematically as $f : A \leadsto A$

#### References

- A Categorical View of Computational Effects
- What does the $\leadsto$ denote?
- Kleisli Category - Take a look at definition 2.4 in the Kleisli morphisms section.