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)))
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)))
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
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;;
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' ->
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").