This is a short, fast, and somewhat loose post to connect the dots between monads in math and monads in functional programming hopefully in a way that illuminates both and makes sense to readers from all parts of the math-programming spectrum.
Monads are an idea from category theory that have an equivalent but slightly different formulation in functional programming. A monoid is a set with a way to mush (multiply/mappend) two values together to make another value of the same type. A monad is a function with a way to mush two applications of itself together into one. So a monad is a function that behaves like a monoid. Monoids are ubiquitous: integers with addition, integers with multiplication, strings (of characters) with concatenation, booleans with
or, booleans with
and. The canonical example of a monad is
Listis a function that, given any datatype (set of values)
d, returns another datatype
List dwhose values are lists of things of type
Listis a monad because we can always mush a list of lists into a list no matter what those lists are lists of. In general, a function
Mis a monad if it has a mushing map
M M -> M, that is, a map
M (M d) -> M dthat works for all
Another monad is
Maybe: a value of type
Maybe Integeris either something of type
Just Integeror it is
Nothingis one of its possible values, you can perform operations that fail, but still return legitimate values, and then handle them in your program without having to anticipate failure (if…else…) at every turn. The mushing map
Maybe (Maybe d) -> Maybe dis obvious:
Nothingof anything and anything of
Just (Just d)maps to
Just d; you only succeed if everything succeeds.
Functional programmers use a slightly different formulation of monads because they want to compose functions that don’t exactly start and end in the right places. They want to do things like compose two functions
f:a —> Maybe band
g:b —> Maybe c, each of which might fail, without having to repeat the logic each time of how to handle failure. In terms of a general monad
M, this means that given functions
f: a —> M band
g:b —> M c, we want a way to stick an
gonly knows how to eat a
b. The trick is: apply
gto make a new function
M g: M b —> M (M c)which knows how to eat an
M b, then use the mushing map
M M —> Mto turn the resulting
M (M c)into an
M c. This operation, called
>>=in Haskell, is what functional programmers consider the defining characteristic of a monad.
A quick example before we see what “apply
Mto a function” means in general. Suppose
readLog: LogFile -> List Stringis a function that takes a web log and produces a list of urls and
tokenize: String -> List Stringtokenizes a url by splitting it on ‘/’ so
tokenize 'yes.com/no/maybe?q=unsure' = ['yes.com','no','maybe?q=unsure']. Monad-composing these applies
tokenizeto every element of our list of urls–that’s what “apply
tokenize” means when
List–then mushes the resulting list of lists into a list. Monads aren’t fancy, they just abstract a common pattern so you can program at a high level without repeating yourself.
So, what does “apply
Mto a function” mean and how is this related to category theory? A category (in the sense of Eilenberg and Mac Lane) consists of three things: objects, functions, and composition. A map between categories is called a functor; a functor
F:C -> Dhas to map objects to objects, functions to functions, and composition to composition. The last two parts mean that
h: a -> band
k:b -> cin
F h: F a -> F band
F k: F b -> F cin
Dand that this mapping of functions must satisfy
F(k.h) = (F k).(F h): if you compose first in
Cand then apply
F, you must get the same thing as if you first apply
F, then compose in
D. So, the punchline is: the set of all datatypes is a category and “functions on datatypes” like
Maybeare functors from this category to itself. Since they are functors, you can apply them not only to datatypes, but also to functions between datatypes: that’s what “apply
Mto a function” means. A monad is a functor from a category to itself that has a mushing map
M M —> M. That
Maybeare functors means that they map functions like
List h:List a —> List band
List k:List b —> List c(and similarly for
Maybe)* that you can compose as usual because they, too, start and end in the right places, but the fact that they are monads means that you can also use them to “compose” functions like
f:a —> Maybe band
g:b —> Maybe cthat don’t.
List h [x, y, z] = [h x, h y, h z]; when
Maybe h (Just h) = Just (h x)and
Maybe h Nothing = Nothing.
- Inspiration and references. This post is inspired by Beckman’s Don’t Fear the Monad, a very beginner-friendly video which goes more thoroughly through monoids and monads as a tool for composition. Another wonderfully intuitive and thorough introduction to monads in programming is You Could Have Invented Monads! (And Maybe You Already Have). For more technical connectings of dots between ideas in category theory and ideas in Haskell, see Notions of Computations as Monoids and Category Theory for Programmers.
- List again, List again, jiggity jig. Mathematicians:
List dis a monoid–the free monoid on the set
Listis the free monoid functor: that’s why we get a monad. Non-mathematicians: every free functor comes with a forgetful functor and the two together always make a monad.
- Haskell punchline. F
or g: b -> M c, if we call the mushing map
fmap ginstead of
M g, we said that (>>= g) = join . (fmap g). See Control.Monad and page 10 of Notions of Computations as Monoids.
- Neglected. Monoids also have an identity element/mempty value mushing with which is the identity map. The analogous thing for monads is a map
d -> M d, called
returnin Haskell, which is similarly an identity for mushing.
- Thank yous. This conversation started as an email exchange with my dad and continued at the white board with my colleague Scott. I reap maximum joy from these conversations so thank you both.