Wadler, Monads for Functional Programming, Section 2.8

Question

Edit II: A, okay: I did not understand how a and b are related in the definition of eval! Now I do it. If anyone is interested, this is a chart that tracks a and b. I am quite a big fan of diagrams. The drawing arrows really improved my Haskell, I swear.

Call chart eval (PDF)

Sometimes I feel very tight.

---

In Wadler’s section “ Monads for Functional Programming” , he introduces the state into a simple evaluation function. The original (non-monodic) function monitors the 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 tu) x = let (a, y) = eval' tx in let (b, z) = eval' uy in (a `div` b, z + 1) 

The definitions of unit and binding for a monadic evaluator are similar simply:

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

Here (→ =) takes the monadic value m :: M a, the function k :: a → M b and displays the monadic value M b. The value of m depends on the value selected for x in the lambda expression.

Wadler then introduces the tick function:

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

Again, straight. However, it is not easy how to combine these functions together to create an evaluation function that returns the number of division operators to execute. In particular, I do not understand:

(1) How the tick is carried out. For example, the following valid function call:

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

However, I cannot correctly evaluate it manually (indicating that I misunderstand something). In particular: (a) The result of evaluating a tick at 0 is ((), 0), since the lambda expression takes ()? (b) If a is the first element of the pair returned by calling tick at 0, how is the unit evaluated?

(2) How to combine tick and block to track the number of split statements to execute. While an ambiguous appraiser is not problematic, using bind confuses me.

Edit: Thanks, everyone. I think my misunderstanding was the role of the lambda expression, '() → unit (div 4 2)'. If I understand correctly,

 (tick >>= (\() -> unit (div mn)) x 

expands to

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

When 'a' is applied to '() → unit (div mn) y', no "bottom line" is obtained. The same effect can be achieved by associating any variable with the lambda operator and substituting a value for it. In this case, the universality of the binding lies in the fact that any value of M a can be transferred to it. As noted, the value of M a is a calculation, for example, "eval". Consequently:

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

If I understand correctly, 'eval t' is replaced with m and the rest of the expression, the function

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

is replaced by k. The result of the evaluation "eval t" is related to (a, y), and the result of the estimate k is related to (b, z). I have ways to go, but that makes it a little easier. Thanks.

Answer 1

You can evaluate the expression manually as follows:

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

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

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

If you now apply the function, replacing 0 with x , you will get:

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

Now apply a checkmark to 0:

 let (a, y) = ((), 0 + 1) in let (b, z) = (\() -> unit (div 4 2)) ay 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 obtain

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

If you apply a 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 2

1a)

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

The lambda expression accepts () because it is the right part of the binding operation, that is, its type is expected to be (() → M b). Therefore, it takes () as the first parameter, then uses "unit" as the element of M b.

1b)

I'm not quite sure what you are asking here. The binding operator is defined to transfer the result and state from the first operation (which is () and 1, respectively) to the second operation, so the device ends with passing 1 as the current state (result, (), the lambda expression was swallowed). The current state is saved as a unit function, and the result is the result of 4 div 2, i.e. 2.

2)

Presumably you will need a function like:

 divCounted :: Int -> Int -> M Int 

Anything that combines a tick and a unit (similar to how you have it), be sure to check once to increase the score, and use a unit to return the result.

Answer 3

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

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

In general, the key to monad M is that it abstracts the entire business by state flow. You should think of a value of type M a as a computer program that returns a value of type a , and also mess with the state. The understanding is that to execute any such program, two operations unit and >>= ; all the activity of building and deconstructing pairs (a,s) can be fixed in these two functions.