A programmable semicolon explained

Don Stewart, for example, uses the folksy characterization of monads as providing us with programmable semicolons. How does this mystifying concept work?

Say we want to compute all Pythagorean triples such that a, b, and c are at most 25. We might use the following predicate to test candidate triples:

p a b c = a*a + b*b == c*c

Then the definition of triples is

triples = do
 a <- [1..25]
 b <- [a..25]
 c <- [b..25]
 guard (p a b c)
 return (a,b,c)

*Main> triples
[(3,4,5),(5,12,13),(6,8,10),(7,24,25),(8,15,17),(9,12,15),(12,16,20),(15,20,25)]

Although triples uses imperative-looking do-notation, it's not in the IO monad but the list monad:

*Main> :type triples
triples :: [(Integer, Integer, Integer)]

How does triples separate the wheat from the chaff with no conditionals? What's the guard thingy? This post is supposed to be about programmable semicolons, but the above example doesn't have any! Let's peek under the hood to answer these questions.

Semicolons are optional thanks to the layout rule, but we could have been explicit:

triples = do {
 a <- [1..25];
 b <- [a..25];
 c <- [b..25];
 guard (p a b c);
 return (a,b,c)
}

Peeling back a few more layers of the onion, we first “desugar” triples by mechanically applying—so easy even a machine can do it!—the definition of do-notation:

triples =
 [1..25]         >>= \a ->
 [a..25]         >>= \b ->
 [b..25]         >>= \c ->
 guard (p a b c) >>
 return (a,b,c)

In the spots where the semicolons are (whether implicit or explicit), notice that we also get applications of the bind operator, concatMap in the list monad, and hence a programmable semicolon! Equational reasoning allows us to substitute “equals for equals” to produce an equivalent definition:

triples =
 concatMap (\a ->
   concatMap (\b ->
     concatMap (\c ->
       guard (p a b c) >> return (a,b,c))
       [b..25])
     [a..25])
   [1..25]

Somehow guard must be doing the work of

if p a b c then [(a,b,c)] else []

In the list monad, return is

return x = [x]

That is, it wraps its argument in a singleton list as with [(a,b,c)] above.

Now consider the definition of guard:

guard           :: (MonadPlus m) => Bool -> m ()
guard True      =  return ()
guard False     =  mzero

In the context of the list monad, it is equivalent to

guard cond = if cond then [()] else []

Substituting the definitions of guard and >>:

triples =
 concatMap (\a ->
   concatMap (\b ->
     concatMap (\c ->
       concatMap (\_ -> [(a,b,c)])
         (if p a b c then [()] else []))
       [b..25])
     [a..25])
   [1..25]

Now we see how guard blocks invalid triples: by nullifying the innermost concatMap. For each valid triple, guard provides a ticket that allows it to pass. The nested applications of concatMap throw away the empty lists and result in a flat list of Pythagorean triples.