manip trees tweaks
authorJim Pryor <profjim@jimpryor.net>
Thu, 2 Dec 2010 01:27:22 +0000 (20:27 -0500)
committerJim Pryor <profjim@jimpryor.net>
Thu, 2 Dec 2010 01:27:22 +0000 (20:27 -0500)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>
manipulating_trees_with_monads.mdwn

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
 
        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 ->
-                              reader_bind (tree_monadize f r) (fun y ->
-                                reader_unit (Node (x, y))));;
+           | Leaf a -> reader_bind (f a) (fun b -> reader_unit (Leaf b))
+           | Node (l, r) -> reader_bind (tree_monadize f l) (fun l' ->
+                              reader_bind (tree_monadize f r) (fun r' ->
+                                reader_unit (Node (l', r'))));;
 
 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
 
 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
 
        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:
 
 
 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
        
        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
 
 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]
 
 
 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
 
 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:
 
 `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)))
 
        - : 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 *)
 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 *)
        - : 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 *)
        - : 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
        - : int = 5
 
 We could simulate the tree state example too, but it would require