From: Jim Pryor
Date: Thu, 2 Dec 2010 01:27:22 +0000 (-0500)
Subject: manip trees tweaks
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=22b8f082095efe49f44171ffa67246a58e298402
manip trees tweaks
Signed-off-by: Jim Pryor
---
diff --git a/manipulating_trees_with_monads.mdwn b/manipulating_trees_with_monads.mdwn
index 61d29640..3b43c9a5 100644
--- a/manipulating_trees_with_monads.mdwn
+++ b/manipulating_trees_with_monads.mdwn
@@ -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 ->
- 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
@@ -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