There's lots going on in Haskell's "do" notation for monads. Reading carefully again through the tutorial at "
Mike's World-O-Programming" I recently had a bit of trouble that I managed to dig myself out of with a mechanical application of a process, "de-sugar and reduce" that I want to present here. The process is a little painstaking. But it helped me discover some things I'd never really thought through before.
To see what this looks like in action, I need a monad with bit of very simple "do" notation, cribbed from the tutorial at "Mike's":
data ArithmeticError =
DivideByZero
| NotDivisible
deriving Show
-- Roll "My" Either and Monad instance to avoid ghci errors.
data MyEither e a = MyLeft e | MyRight a deriving Show
instance Monad (MyEither e) where
return x = MyRight x
(MyLeft x) >>= f = MyLeft x
(MyRight x) >>= f = f x
safe_divide :: Int -> Int -> MyEither ArithmeticError Int
safe_divide _ 0 = MyLeft DivideByZero
safe_divide i j | i `mod` j /= 0 = MyLeft NotDivisible
safe_divide i j = MyRight (i `div` j)
g :: Int -> Int -> Int -> MyEither ArithmeticError Int
g i j k =
do q1 <- i `safe_divide` k
q2 <- j `safe_divide` k
return (q1 + q2)
To prove to myself I understand the "do" block I want to de-sugar it and reduce it. Cribbing again from "Mike's" discussion of "do" syntax (as well as countless other examples in countless other monad tutorials and Haskell texts, I'm sure), the "do" block above turns into
(i `safe_divide` k) >>= (\q1 ->
((j `safe_divide` k) >>= (\q2 ->
(return (q1 + q1)))))
Roll it onto one line to get a sense of the way those parenthese pile up:
(i `safe_divide` k) >>= (\q1 -> ((j `safe_divide` k) >>= (\q2 -> (return (q1 + q2)))))
To double check the parenthese are right, put some values in i, j, and k, and evaluate it in a ghci prompt (load the excerpt above from a file):
*Main> 2 `safe_divide` 1 >>= (\q1 -> (4 `safe_divide` 1 >>= (\q2 -> (return (q1 + q2)))))
MyRight 6
So far so good. Next, rearrange ">>=" in function call form, and double-check with ghci:
(>>=) (i `safe_divide` k) (\q1 -> ((>>=) (j `safe_divide` k) (\q2 -> (return (q1 + q1)))))
*Main> (>>=) (2 `safe_divide` 1) (\q1 -> ((>>=) (4 `safe_divide` 1) (\q2 -> (return (q1 + q2)))))
MyRight 6
Next, I find it to be very revealing to outline the scope the evaluation contexts:
(>>=) (i `safe_divide` k) (\q1 -> ((>>=) (j `safe_divide` k) (\q2 -> (return (q1 + q1)))))
------------------- ----------------------------------------------------------------
>>= m a (a -> m b)
------------------ ----------------------------
>>= m a (a -> m b)
Here's visual proof of the impact of the fact that operators in the de-sugared "do" syntax associate to the right. Note how the scope of the second argument to the first ">>=" extends over the rest of the entire expression. I think this is one part of the impedence mismatch that "do" notation presents to programmers with imperative backgrounds. Those clauses in the "do" block may *look* like statements. They may even contain a "return" keyword. But when you de-sugar the notation and watch the extent of your parentheses, then you see they're all wrapped up inside one giant nested expression. The "do" sugar hits programmers from the land of imperative languages squarely between the eyes, the way it dresses up a giant nested expression in the clothing of a series of statements. There's no doubt it's a lot cleaner to read than a cascade of hanging lambdas. But it's still a giant expression, not a series of disconnected statements.
The other thing that grabs my attention when I do this is the discontinuity between bindings and functions. My mental model working with lambdas up to this point is that you specify an argument list and then you *use* the argument values. Why else did you elaborate them? But a quick look at the de-sugared notation above shows those bindings are really just to capture the value from the ">>=" left hand side, and they don't necessarily have anything to do with the lambda that immediately follows. In this case, lambda argument "q1" doesn't bind to anything in the next level ">>=" left hand side at all, although it could. The de-sugared "do" syntax shows the technique of "parking" those bindings for the next deeper level of expression evaluation, that's all.
Next, start reducing the de-sugared/functionalized version of the "do" block. Starting at the outermost layer, the first application of ">>=" has two arguments, the monad value (or the expression that reduces to a monad value) to the left and the function to the right. Note how, with the nesting of sub-expressions, each application of ">>=" scopes over all the remaining lines in the "do" block. The "do" notation may look like an orderly series of statements, but it ain't. Each time you apply ">>=" there's a choice: evaluate the expression to the right zero, once, or more than once.
Even the first, baby-step monad examples show the power latent in the scoping extents in the de-sugared notation. Both Maybe and Either apply a zero or once strategy, possibly just to dump the entire right hand ">>=" argument, without ever evaluating any of it. For another example, consider the list monad--another baby-step model. In this case, the ">>=" goes the other way, iterating in a kind of cross-product machine gun. Here's a trivial example:
h :: Int -> Int -> [Int]
h i j =
do l1 <- if (i > 0) then [0..i] else []
l2 <- if (j > 0) then [0..j] else []
return (l1 + l2)
De-sugared:
(if (i > 0) then [0..i] else []) >>= (\l1 -> (if (j > 0) then [0..j] else [] >>= (\l2 -> return (l1 + l2))))
Functionalized:
(>>=) (if (i > 0) then [0..i] else []) (\l1 -> (>>=) (if (j > 0) then [0..j] else []) (\l2 -> return (l1 + l2)))
Scope outlined:
(>>=) (if (i > 0) then [0..i] else []) (\l1 -> (>>=) (if (j > 0) then [0..j] else []) (\l2 -> return (l1 + l2)))
-------------------------------- -------------------------------------------------------------------------
>>= mv a (a -> mv b)
-------------------------------- --------------------------
>>= mv a a -> mv b
Reduced outer and inner scopes (for list, >>= means concat (map f mx)
concat (map (\l1 -> (>>=) (if (j > 0) then [0..j] else []) (\l2 -> return (l1 + l2))) (if (i > 0) then [0..i] else []))
------------------------------- --------------------------
mx f
concat (map (\l1 -> (concat (map (\l2 -> return (l1 + l2)) (if (j > 0) then [0..j] else [])))) (if (i > 0) then [0..i] else []))
Now you can see how the enumeration at the outer scope drives a second enumeration in the inner scope, with enumeration inputs getting carried along by bindings until they're referenced by the innermost "return" expression. What's getting "returned" (or monadized) is single item list with the sum of the two iterator values, with the encompassing "concat" calls stripping the inner list structure at each level of nested scope.
To summarize: mechanically transforming "do" syntax can help make behavior less opaque. Everything's an expression, appearances of "do" blocks to the contrary. Each successive expression in a "do" block scopes all subsequent expressions. Control flow varies monad by monad. Each line in a "do" block has implicit control over all the subsequent lines. When you can't quite grok the behavior, grab your ghci prompt, de-sugar, functionalize, scope, and start reducing.