Wadler, "Monads for Functional Programming," Section 2.8

Question

Edit II: Ah, okay: I wasn't understanding how a and b were being bound in the definition of eval! Now I do. If anyone's interested, this is a diagram tracking a and b. I'm a pretty big fan of diagrams. Drawing arrows really improved my Haskell, I swear.

A Diagram of an eval call (PDF)

Sometimes I feel really dense.

---

In section 2.8 of Wadler's "Monads for Functional Programming," he introduces state into a simple evaluation function. The original (non-monadic) function tracks state using a series of let expressions, and is easy to follow:

data Term = Con Int | Div Term Term
 deriving (Eq, Show)

type M a = State -> (a, State)
type State = Int

eval' :: Term -> M Int
eval' (Con a) x   = (a, x)
eval' (Div t u) x = let (a, y) = eval' t x in
                    let (b, z) = eval' u y in
                    (a `div` b, z + 1)

The definitions of unit and bind for the monadic evaluator are similarly straightforward:

unit :: a -> M a
unit a = \x -> (a, x)

(>>=) :: M a -> (a -> M b) -> M b
m >>= k = \x -> let (a, y) = m x in
                let (b, z) = k a y in
                 (b, z)

Here, (>>=) accepts a monadic value m :: M a, a function k :: a -> M b, and outputs a monadic value M b. The value of m is dependent on the value substituted for x in the lambda expression.

Wadler then introduces the function tick:

tick :: M ()
tick = \x -> ((), x + 1)

Again, straightforward. What isn't straightforward, however, is how to chain these functions together to produce an evaluation function that returns the number of division operators performed. Specifically, I don't understand:

(1) How tick is implemented. For instance, the following is a valid function call:

(tick >>= \() -> unit (div 4 2)) 0
 ~> (2, 1)

However, I can't evaluate it correctly by hand (indicating that I misunderstand something). In particular: (a) The result of evaluating tick at 0 is ((), 0), so How does the lambda expression accept ()? (b) If a is the first element of the pair returned by calling tick at 0, how does unit get evaluated?

(2) How to combine tick and unit to track the number of division operators performed. While the non-monadic evaluator is not problematic, the use of bind is confusing me here.

Edit: Thanks, everybody. I think my misunderstanding was the role of the lambda expression, '() -> unit (div 4 2)'. If I understanding it correctly,

(tick >>= (\() -> unit (div m n)) x

expands to

(\x -> let (a, y) = tick x in
       let (b, z) = (\() -> unit (div m n) a y) in
       (b, z)) x

When 'a' is applied to '() -> unit (div m n) a y', no 'practical result' is yielded. The same effect could be achieved by binding any variable with a lambda operator, and substituting a value for it. The versatility of bind, in this case, is that any value M a can be passed to it. As noted, a value M a represents a computation, for instance, 'eval.' Hence:

eval (Con a) = unit a

eval (Div t u) = eval t >>= (\a ->
                  eval u >>= (\b ->
                   tick >>= (\c -> unit (a `div` b))))

If I understand correctly, 'eval t' is substituted for m and the remainder of the expression, the function

'(\a -> eval u >>= (\b -> tick >>= (\c -> unit (a `div` b))))'

is substituted for k. The result of evaluating 'eval t' is bound to (a, y), and the result of evaluating k is bound to (b, z). I have a ways to go, but this clears it up somewhat. Thanks.

Answer 1

You can evaluate the expression by hand like this:

(tick >>= \() -> unit (div 4 2)) 0

If you insert tick and \() -> unit (div 4 2) into the definition of >>=, this becomes:

(\x -> let (a, y) = tick x in
       let (b, z) = (\() -> unit (div 4 2)) a y in
       (b, z)) 0

If you now apply the function by substituting 0 for x, you get:

let (a, y) = tick 0 in
let (b, z) = (\() -> unit (div 4 2)) a y in
(b, z)

Now let's apply tick to 0:

let (a, y) = ((), 0 + 1) in
let (b, z) = (\() -> unit (div 4 2)) a y in
(b, z)

So a becomes () and y becomes 0+1 which is 1. So we have

let (b, z) = (\() -> unit (div 4 2)) () 1 in
(b, z)

If we apply the function to () we get

let (b,z) = unit (div 4 2) 1 in
(b,z)

If we apply unit, we get

 let (b,z) = (div 4 2, 1) in
 (b,z)

div 4 2 is 2, so the result is (2,1).