author Jim Pryor Thu, 2 Dec 2010 01:27:22 +0000 (20:27 -0500) committer Jim Pryor Thu, 2 Dec 2010 01:27:22 +0000 (20:27 -0500)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>

index 61d2964..3b43c9a 100644 (file)
@@ -133,10 +133,10 @@ But we can do this:

let rec tree_monadize (f : 'a -> 'b reader) (t : 'a tree) : 'b tree reader =
match t with
-           | Leaf i -> reader_bind (f i) (fun i' -> reader_unit (Leaf i'))
-           | Node (l, r) -> reader_bind (tree_monadize f l) (fun x ->
+           | Leaf a -> reader_bind (f a) (fun b -> reader_unit (Leaf b))
+           | Node (l, r) -> reader_bind (tree_monadize f l) (fun l' ->

This function says: give me a function `f` that knows how to turn
something of type `'a` into an `'b reader`---this is a function of the same type that you could bind an `'a reader` to---and I'll show you how to
@@ -203,10 +203,10 @@ modification whatsoever, except for replacing the (parametric) type

let rec tree_monadize (f : 'a -> 'b state) (t : 'a tree) : 'b tree state =
match t with
-           | Leaf i -> state_bind (f i) (fun i' -> state_unit (Leaf i'))
-           | Node (l, r) -> state_bind (tree_monadize f l) (fun x ->
-                              state_bind (tree_monadize f r) (fun y ->
-                                state_unit (Node (x, y))));;
+           | Leaf a -> state_bind (f a) (fun b -> state_unit (Leaf b))
+           | Node (l, r) -> state_bind (tree_monadize f l) (fun l' ->
+                              state_bind (tree_monadize f r) (fun r' ->
+                                state_unit (Node (l', r'))));;

Then we can count the number of leaves in the tree:

@@ -255,20 +255,20 @@ of leaves?

let rec tree_monadize (f : 'a -> ('b, 'r) continuation) (t : 'a tree) : ('b tree, 'r) continuation =
match t with
-           | Leaf i -> continuation_bind (f i) (fun i' -> continuation_unit (Leaf i'))
-           | Node (l, r) -> continuation_bind (tree_monadize f l) (fun x ->
-                              continuation_bind (tree_monadize f r) (fun y ->
-                                continuation_unit (Node (x, y))));;
+           | Leaf a -> continuation_bind (f a) (fun b -> continuation_unit (Leaf b))
+           | Node (l, r) -> continuation_bind (tree_monadize f l) (fun l' ->
+                              continuation_bind (tree_monadize f r) (fun r' ->
+                                continuation_unit (Node (l', r'))));;

We use the continuation monad described above, and insert the
-`continuation` type in the appropriate place in the `tree_monadize` code. Then if we give the `tree_monadize` function an operation that converts `int`s into continuations expecting `'b` arguments, it will give us back a way to turn `int tree`s into continuations that expect `'b tree` arguments. The effect of giving the continuation such an argument will be to distribute across the `'b tree`'s leaves effects that parallel the effects that the `'b`-expecting continuations would have on their `'b`s.
+`continuation` type in the appropriate place in the `tree_monadize` code. Then if we give the `tree_monadize` function an operation that converts `int`s into `'b`-wrapping continuation monads, it will give us back a way to turn `int tree`s into corresponding `'b tree`-wrapping continuation monads.

So for example, we compute:

# tree_monadize (fun a -> fun k -> a :: (k a)) t1 (fun t -> []);;
- : int list = [2; 3; 5; 7; 11]

-We have found a way of collapsing a tree into a list of its leaves. Can you trace how this is working?
+We have found a way of collapsing a tree into a list of its leaves. Can you trace how this is working? Think first about what the operation `fun a -> fun k -> a :: (k a)` does when you apply it to a plain `int`, and the continuation `fun _ -> []`.

The continuation monad is amazingly flexible; we can use it to
simulate some of the computations performed above.  To see how, first
@@ -276,7 +276,7 @@ note that an interestingly uninteresting thing happens if we use
`continuation_unit` as our first argument to `tree_monadize`, and then
apply the result to the identity function:

-       # tree_monadize continuation_unit t1 (fun i -> i);;
+       # tree_monadize continuation_unit t1 (fun t -> t);;
- : int tree =
Node (Node (Leaf 2, Leaf 3), Node (Leaf 5, Node (Leaf 7, Leaf 11)))

@@ -284,19 +284,19 @@ That is, nothing happens.  But we can begin to substitute more
interesting functions for the first argument of `tree_monadize`:

(* Simulating the tree reader: distributing a operation over the leaves *)
-       # tree_monadize (fun a -> fun k -> k (square a)) t1 (fun i -> i);;
+       # tree_monadize (fun a -> fun k -> k (square a)) t1 (fun t -> t);;
- : int tree =
Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))

(* Simulating the int list tree list *)
-       # tree_monadize (fun a -> fun k -> k [a; square a]) t1 (fun i -> i);;
+       # tree_monadize (fun a -> fun k -> k [a; square a]) t1 (fun t -> t);;
- : int list tree =
Node
(Node (Leaf [2; 4], Leaf [3; 9]),
Node (Leaf [5; 25], Node (Leaf [7; 49], Leaf [11; 121])))

(* Counting leaves *)
-       # tree_monadize (fun a -> fun k -> 1 + k a) t1 (fun i -> 0);;
+       # tree_monadize (fun a -> fun k -> 1 + k a) t1 (fun t -> 0);;
- : int = 5

We could simulate the tree state example too, but it would require