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

1a)

The result of evaluating tick at 0 is ((), 1) -- look at the code again, it increments the input value by one.

The lambda expression accepts () because it is the right-hand side of the bind operation, meaning its type is expected to be (() -> M b). So it takes the () as its first parameter, then uses "unit" as the M b item.

1b)

I'm not quite sure what you're asking here. The bind operator is defined to pass the result and state from the first operation (which is () and 1 respectively) into the second operation, so unit ends up being passed 1 as the current state (the result, (), was swallowed by the lambda expression). The current state is kept as-is by the unit function, and the result is the result of 4 div 2, i.e. 2.

2)

Presumably you will want some function of the type:

divCounted :: Int -> Int -> M Int

Which either combines tick and unit (similar to how you have), making sure to tick once to increase the count, and use unit to give back the result.

Answer 2

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).

Answer 3

1a) The result of evaluating tick at 0 is ((), 1), so How does the lambda expression accept ()?

The key about the state monad is that bind takes care of the second component of the pair, the state. The lambda expression only needs to handle the (), the first component of the pair, the return value.

In general, the key about the monad M is that it abstracts the whole business of threading the state away. You should think of a value of type M a as a computer program that returns a value of type a while also messing with the state. The insight is that two operations, unit and >>=, are enough to write any such program; the entire business of constructing and deconstructing pairs (a,s) can be captured in those two functions.