Monday, July 06, 2009

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.

4 comments:

  1. Anonymous10:35 AM

    I think of monads as providing a programmable assignment statement rather than a "programmable semicolon" (which is simply a degenerate case).

    ReplyDelete
    Replies
    1. Not all monads deal with assignment. For instance, the Writer monad deals with only output, and the Error monad with the throwing of exceptions. However, all monads must describe, through their bind operation, how to sequentially compose two statements, which is the function of the semicolon in most languages.

      Delete
  2. In the last triplet definition (if p a b c then [()] else [])) should be corrected to (if p a b c then [(a,b,c)] else [])).

    ReplyDelete
    Replies
    1. No, it shouldn't. The innermost application of concatMap is what performs that transformation.

      Delete