Adam Foltzer's Blog

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 (printf "Two\n"):

> ((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

Nesting 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 begin example.

((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 x:

> ((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 mybegin and mylet are the same. Let’s call it what it is, which is bind (Haskell: >>=).

> (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 begin and 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.