X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=manipulating_trees_with_monads.mdwn;h=0d9e33df3425822ec12e1b4b8aab11fa2594475c;hp=4f91bbbb64414d85c514f23f8e2640342c6e316b;hb=b62e35e77aaba7acf2441ce120931e329f61b774;hpb=6debd883b7ee5c9125743a23d05e997b9188f90e diff --git a/manipulating_trees_with_monads.mdwn b/manipulating_trees_with_monads.mdwn index 4f91bbbb..0d9e33df 100644 --- a/manipulating_trees_with_monads.mdwn +++ b/manipulating_trees_with_monads.mdwn @@ -57,7 +57,7 @@ new leaves, and maps that function over all the leaves in the tree, leaving the structure of the tree unchanged. For instance: let double i = i + i;; - tree_map t1 double;; + tree_map double t1;; - : int tree = Node (Node (Leaf 4, Leaf 6), Node (Leaf 10, Node (Leaf 14, Leaf 22))) @@ -80,7 +80,7 @@ each leaf instead, by supplying the appropriate `int -> int` operation in place of `double`: let square i = i * i;; - tree_map t1 square;; + tree_map square t1;; - : int tree = Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121))) @@ -140,7 +140,7 @@ It would be a simple matter to turn an *integer* into an `int reader`: asker 2 (fun i -> i + i);; - : int = 4 -This is a monadic box that waits for an an environment (here, the argument `modifier`) and returns what that environment maps `a` to. +`asker a` is a monadic box that waits for an an environment (here, the argument `modifier`) and returns what that environment maps `a` to. How do we do the analagous transformation when our `int`s are scattered over the leaves of a tree? How do we turn an `int tree` into a reader? A tree is not the kind of thing that we can apply a @@ -293,7 +293,7 @@ it through: Later, we will talk more about controlling the order in which nodes are visited. One more revealing example before getting down to business: replacing -`state` everywhere in `tree_monadize` with `list` gives us +`state` everywhere in `tree_monadize` with `list` lets us do: # let decider i = if i = 2 then [20; 21] else [i];; # tree_monadize decider t1;; @@ -311,11 +311,11 @@ one for each choice of `int`s for its leaves. Now for the main point. What if we wanted to convert a tree to a list of leaves? - type ('a, 'r) continuation = ('a -> 'r) -> 'r;; + type ('r,'a) continuation = ('a -> 'r) -> 'r;; let continuation_unit a = fun k -> k a;; let continuation_bind u f = fun k -> u (fun a -> f a k);; - let rec tree_monadize (f : 'a -> ('b, 'r) continuation) (t : 'a tree) : ('b tree, 'r) continuation = + let rec tree_monadize (f : 'a -> ('r,'b) continuation) (t : 'a tree) : ('r,'b tree) continuation = match t with | Leaf a -> continuation_bind (f a) (fun b -> continuation_unit (Leaf b)) | Node (l, r) -> continuation_bind (tree_monadize f l) (fun l' -> @@ -368,7 +368,7 @@ interesting functions for the first argument of `tree_monadize`: It's not immediately obvious to us how to simulate the List monadization of the tree using this technique. We could simulate the tree annotating example by setting the relevant -type to `('a, 'state -> 'result) continuation`. +type to `(store -> 'result, 'a) continuation`. Andre Filinsky has proposed that the continuation monad is able to simulate any other monad (Google for "mother of all monads").