From 22b8f082095efe49f44171ffa67246a58e298402 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Wed, 1 Dec 2010 20:27:22 -0500 Subject: [PATCH] manip trees tweaks Signed-off-by: Jim Pryor --- manipulating_trees_with_monads.mdwn | 36 ++++++++++++++++++------------------ 1 file changed, 18 insertions(+), 18 deletions(-) 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 -- 2.11.0