And then out of nowhere, a monad appears!
In this post, I walk through two typical Scheme programming challenges, and then show how they naturally give rise to a monad. Really, they’re not so scary. As Simon Peyton Jones said of designing Haskell:
Our biggest mistake: using the scary term “monad” rather than “warm fuzzy thing”.
Here’s the first part of the challenge: can you recreate the behavior of Scheme’s
begin using only
lambda and procedure application? Let’s start with a simple example:
> (begin (printf "One\n") (printf "Two\n")) One Two
In this example,
begin enforces the order in which the two
printf expressions are evaluated. To get the same behavior just from
lambda and application, we need to take advantage of the fact that Scheme is a call-by-value language. This is, the arguments to any function are always applied before the body of the function is evaluated.
So, we need to arrange our expression so that
(printf "One\n") is an argument to a procedure that contains
> ((lambda (_) (printf "Two\n")) (printf "One\n")) One Two
Success! Note that there’s nothing special about the underscore; it simply means that we do not care about the value of
(printf "One\n"). We only care that it gets evaluated for its printing effect.
This would be nicer to read if the evaluation order of our statements read from left-to-right, as with
begin. The only reason our example reads backwards is the order of procedure application:
(function argument). To get the order we want, we define a backwards procedure application:
> (define mybegin (lambda (x f) (f x))) > (mybegin (printf "One\n") (lambda (_) (printf "Two\n"))) One Two
This reads a lot better. How about adding a third expression?
> (mybegin (printf "One\n") (lambda (_) (mybegin (printf "Two\n") (lambda (_) (printf "Three\n"))))) One Two Three
Now for the second part of the challenge: recreate the behavior of Scheme’s
let using the same toolbox of
lambda and procedure application. Here’s our example:
> (let ([x 5]) (+ x 3)) 8
let in this way enforces the order of evaluation similarly to
begin. In this example,
5 must be evaluated before
(+ x 3). So, we can start with the same basic structure as our
((lambda (_) (+ x 3)) 5)
This isn’t quite right, though, since
let does more than
begin. Rather than throwing away the value of, say,
(printf "One\n") by binding it to an unused underscore, we need to evaluate
5 and then bind it to
> ((lambda (x) (+ x 3)) 5) 8
Let’s use the same trick we used for
mybegin to make this nicer to read:
> (define mylet (lambda (x f) (f x))) > (mylet 5 (lambda (x) (+ x 3))) 8
It also works nicely with larger examples:
> (mylet 5 (lambda (x) (mylet x (lambda (y) (+ x y))))) 10
Why, then, bother with two names for the same thing? After all, the definitions of
mylet are the same. Let’s call it what it is, which is
> (define bind (lambda (x f) (f x)))
With a definition for
bind, we nearly have a monad. We also need a function
return in order to really say we have a monad. Loosely speaking,
return is a function that brings a value into a monad’s world in the most trivial way possible. Our monad’s world is simply the world of Scheme values, so what could be more trivial than the identity function?
> (define return (lambda (a) a))
Here are our examples, happily living in the identity monad:
> (bind (printf "One\n") (lambda (_) (bind (printf "Two\n") (lambda (_) (return (printf "Three\n")))))) One Two Three > (bind 5 (lambda (x) (return (+ x 3)))) 8 > (bind 5 (lambda (x) (bind x (lambda (y) (return (+ x y)))))) 10
The identity monad by itself isn’t terribly useful. After all, we already have
let! What we’ve done, though, is provide a hook into how we evaluate expressions in sequence. In “Real World Haskell”, Bryan O’Sullivan, Don Stewart, and John Goerzen describe monads as the “programmable semicolon”, and it’s easy to see why. We’ve taken the most basic notion of sequencing, “do this, then do that”, and encoded it with a handful of functions. The upshot is that more complex notions of sequencing are nearly as easy and follow the same structure, but that’s for a future post.