Monads in Elm

Sometimes people ask, “Does Elm have monads?” And sometimes they ask, “What is a monad? I’ve heard that it is something mysterious and difficult.” This short essay attempts to answer these questions. We begin with an example.

1 Chaining Things Together

Elm has functions like these

andThen : (a -> Maybe b) -> Maybe a -> Maybe b
andThen : (a -> Parser b) -> Parser a -> Parser b

They are used to chain things together — things of type Maybe a or type Parser a in the case at hand. As an example, consider the problem of extracting the head of a list. For this we use the function

List.head : List a -> Maybe a

where

type Maybe a = Just a | Nothing

When a list is nonempty, List.head returns a value of type Just a. In the contrary case, it returns Nothing. The example below illustrates this.

> List.head [1,2,3]
  Just 1 : Maybe number
> List.head []
  Nothing : Maybe a

Now consider a deeply nested list, say [[1,2,3]]. To extract the head of a list, it seems natural to use the function List.head twice. Here is a start:

> [[1,2,3]] |> List.head
Just [1,2,3]

The notation x |> f means f x. Then g (f x) can be written as a "pipeline," namely, as

x |> f |> g

Notice that [[1,2,3]] |> List.head has Just [1,2,3] as value. This is a Maybe list, and so has the wrong type for a second application of List.head. The solution is to use the function

Maybe.andThen : (a -> Maybe b) -> Maybe a -> Maybe b

Then successive applications of List.head can be chained:

> [[1,2,3]] |> List.head |> Maybe.andThen List.head
Just 1 : Maybe number

The result, Just 1, is a still a value of type Maybe number. This is as expected, because we could have computed

> [[]] |> List.head |> Maybe.andThen List.head
Nothing : Maybe b

Notice how the Nothing value is propagated down the pipeline.

2 A Pattern

The general pattern for andThen, whether it be Maybe.andThen or Parser.andThen, or something else, is

andThen : (a -> M b) -> M a -> M b

Here M, like Maybe or Parser, is a type constructor. Or, in Haskell terminology, a functor. Consider the function defined by permuting the arguments of andThen:

b : M a ->  (a -> M b) -> M b

Up to small differences of notation, this is the bind function in Haskell. It is usually written as an operator, so that

(>>=) : M a -> (a -> M b) -> M b

Bind is the function that makes a monad a monad.

For a type constructor (or functor) M to be a monad, it suffices for there to be an associated bind function which satisfies certain properties to be discussed below. Said in the language of Elm, a monad is a type constructor that has an andThen function satisfying certain properties.

3 Composition

Consider functions f: a -> b and g : b -> c. One can form the composite function g o f : a -> c. More generally, composition can be formed whenever the type of the codomain of f is the same as the type of the domain of g.

Composition is a good thing. Why? Because composition is what gives us the power to make big things out of smaller things. In programming, that is important because we can reduce complicated things to simpler ones, thereby keeping both the code and ourselves sane.

Consider next the “monadic” functions

f : a -> M b
g : b -> M c

We cannot compose them as is because the types of the domain and codomain do not match. But observe what we can do with the help of the andThen function:

g o' f = \x -> andThen g (f x)

The result is a new composition operator. It can be written in a more suggestive form that “follows the prose:”

g o' f = \x -> (f x) |> andThen g

Or one can also write it using the bind operator

g o' f = \x -> (f x) >>= g

That is, we use >>- to “shove” the value f x of type M b into the function g, which has type b -> M c.

Aside. The construction of a new composition law is the point of view of the so-called Kleisli categories. Monadic functions form a category if one uses o' instead of o for composition.

4 Properties

There is a bit more to the monad story than has be recounted so far. The new composition law, like the usual one, should satisfy the identities

id o' f = f o' id = f

and

f o' (g o' h) = (f o' g) o' h

These identities translate back to identities for andThen, M, and a function a -> M a that in Haskell is called return. For Maybe in Elm, that is the function that sends a value x of type a to Just x. For Parser, it is the function succeed : a -> Parser a.

5 Summary

• Elm has monads.
• Monads are good because they make it possible to compose functions where this seems to be impossible.
• Monads are not mysterious: they are type constructors (or functors) with certain additional properties, one of which is to make a composition operation possible.

6 References

• Kleisli categories, in Bartosz Milewski’s Programming Cafe: Category Theory, Haskell, Concurrency, C++. Studying this reference was what finally turned on the lightbulb for me. My advice is to skip over the C++ parts and concentrate on the Haskell parts. Even better: his book (PDF).
• Joël Quenneville, The Mechanics of Maybe. I’ve adapted the example of deeply nested lists from this article.