# Three things I don't understand about monads

Monads are a remarkably powerful tool for building specialized programming languages. Some examples include:

But there's a bunch of things I don't understand about monads. In each case, my confusion involves some aspect of the underlying math that "bubbles up" to affect the design of specialized languages.

(Warning: Obscure monad geeking ahead.)

### Commutative monads

A "commutative monad" is any monad where we can replace the expression:

```
do a <- ma
b <- mb
f a b
```

...with:

```
do b <- mb
a <- ma
f a b
```

...without changing the meaning. Examples of commutative monads include `Reader`

and `Rand`

. This is an important property, because it might allow us to parallelize the commonly-used `sequence`

function across huge numbers of processors:

```
sequence :: (Monad m) => [m a] -> m [a]
```

Simon Peyton Jones lists this problem as Open Challenge #2, saying:

Commutative monads are very common. (Environment, unique supply, random number generation.) For these, monads over-sequentialise.

Wanted: theory and notation for some cool compromise.

### Commutative monad morphisms

~~Monad morphisms are the category theory equivalent of Haskell's monad transformers.~~ *Haskell's monad transformers can be expressed as monad layerings, which correspond to the monad morphisms of category theory.*

Many complicated monads break down into a handful of monad transformers, often in surprising ways.

But composing monad transformers is a mess, because they interact in poorly-understood ways. In general, the following two types have very different semantics:

```
FooT (BarT m)
BarT (FooT m)
```

If `FooT`

and `BarT`

commute with each other, however, the two types would be equivalent. This is helpful when building large stacks of monad transformers.

Chung-chieh Shan encountered a related problem when applying monad morphisms to build a theory of natural language semantics:

It remains to be seen whether monads would provide the appropriate conceptual encapsulation for a semantic theory with broader coverage. In particular, for both natural and programming language semantics, combining monads---or perhaps monad-like objects---remains an open issue that promises additional insight.

### Monad morphisms and abstract algebra

Dan Piponi has been drawing some fascinating connections between monad morphisms and abstract algebra. See, for example:

This approach seems to throw a lot of light on monad morphisms---but at least in my case, the light only highlights my confusion.

Of the three problems listed here, this is the one most likely to be discussed in a textbook somewhere. And a solution to this problem would likely help significantly with the other two.

So, my question: Does anybody have any books, papers or ideas that might help untangle this mess?

*Update: Be sure to see the comment thread on the second Dan Piponi post above and Chung-chieh Shan's excellent bibliography on monad transformers.*

Want to contact me about this article? Or if you're looking for something else to read, here's a list of popular posts.

`FooT`

and`BarT`

commute (sometimes? often? always?) depends on the algebraic properties of`Foo`

and`Bar`

. There's all sorts of neat stuff going on that I can't quite grasp. For example,`(ListT m)`

is only a monad when`m`

is a commutative monad. And as Dan showed, this is related to properties of freely-generated semirings. I suspect that there's something deeper to be said about these issues, and that it might be important for monad-based DSLs. Anyway, here's a list of resources that might be relevant: - Mark Jones and Luc Duponcheel's Composing monads, an early paper on monad transformers that noticed some interesting limits to what could be composed. - Edmund Robinson's Variations on Algebra: monadicity and generalisations of equational theories, which describes a fascinating relationship between initial algebras and monads. (Thanks, alpheccar!) - According to Michi, enriched categories provide some insight into these kinds of layerings. So far, I've found Basic Concepts of Enriched Category Theory and a Wikipedia article, but I haven't dug into this area yet (it's getting a bit heavy for my current knowledge of category theory).inventedto talk about algebras, and are really beautiful when you need to do things like enrich a syntax with variables (eg, for unification algorithms). Michi is right about enriched category theory being relevant here. One of the bad things about monads as they are commonly used is that there's no theory for theoperationsin a monad, and that's the most important part! Power and Plotkin have been looking at how to derive a monad given a set of algebraic operations (for example, if you've got get and set, can you derive the state monad?), and enriched categories show up.