First, we'll be needing a lot of trees for the remainder of the
course. Here again is a type constructor for leaf-labeled, binary trees:
- type 'a tree = Leaf of 'a | Node of ('a tree * 'a tree)
+ type 'a tree = Leaf of 'a | Node of ('a tree * 'a tree);;
[How would you adjust the type constructor to allow for labels on the
internal nodes?]
let square i = i * i;;
tree_map square t1;;
- - : int tree =ppp
+ - : int tree =
Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
Note that what `tree_map` does is take some unchanging contextual
tree that is ready to accept any `int -> int` function and produce the
updated tree.
-\tree (. (. (f 2) (f 3)) (. (f 5) (. (f 7) (f 11))))
-
\f .
_____|____
| |
`tree_monadize` function, it then wraps an `int tree` in a box, one
that does the same state-incrementing for each of its leaves.
+We can use the state monad to replace leaves with a number
+corresponding to that leave's ordinal position. When we do so, we
+reveal the order in which the monadic tree forces evaluation:
+
+ # tree_monadize (fun a -> fun s -> (s+1, s+1)) t1 0;;
+ - : int tree * int =
+ (Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf 5))), 5)
+
+The key thing to notice is that instead of copying `a` into the
+monadic box, we throw away the `a` and put a copy of the state in
+instead.
+
+Reversing the order requires reversing the order of the state_bind
+operations. It's not obvious that this will type correctly, so think
+it through:
+
+ let rec tree_monadize_rev (f : 'a -> 'b state) (t : 'a tree) : 'b tree state =
+ match t with
+ | Leaf a -> state_bind (f a) (fun b -> state_unit (Leaf b))
+ | Node (l, r) -> state_bind (tree_monadize f r) (fun r' -> (* R first *)
+ state_bind (tree_monadize f l) (fun l'-> (* Then L *)
+ state_unit (Node (l', r'))));;
+
+ # tree_monadize_rev (fun a -> fun s -> (s+1, s+1)) t1 0;;
+ - : int tree * int =
+ (Node (Node (Leaf 5, Leaf 4), Node (Leaf 3, Node (Leaf 2, Leaf 1))), 5)
+
+We will need below to depend on controlling the order in which nodes
+are visited when we use the continuation monad to solve the
+same-fringe problem.
+
One more revealing example before getting down to business: replacing
`state` everywhere in `tree_monadize` with `list` gives us
Unlike the previous cases, instead of turning a tree into a function
from some input to a result, this transformer replaces each `int` with
-a list of `int`'s. We might also have done this with a Reader monad, though then our environments would need to be of type `int -> int list`. Experiment with what happens if you supply the `tree_monadize` based on the List monad an operation like `fun -> [ i; [2*i; 3*i] ]`. Use small trees for your experiment.
+a list of `int`'s. We might also have done this with a Reader monad, though then our environments would need to be of type `int -> int list`. Experiment with what happens if you supply the `tree_monadize` based on the List monad an operation like `fun i -> [2*i; 3*i]`. Use small trees for your experiment.
[Why is the argument to `tree_monadize` `int -> int list list` instead
of `int -> int list`? Well, as usual, the List monad bind operation
If you want to see how to parameterize the definition of the `tree_monadize` function, so that you don't have to keep rewriting it for each new monad, see [this code](/code/tree_monadize.ml).
+Using continuations to solve the same fringe problem
+----------------------------------------------------
+
+We've seen two solutions to the same fringe problem so far.
+The simplest is to map each tree to a list of its leaves, then compare
+the lists. But if the fringes differ in an early position, we've
+wasted our time visiting the rest of the tree.
+
+The second solution was to use tree zippers and mutable state to
+simulate coroutines. We would unzip the first tree until we found the
+next leaf, then store the zipper structure in the mutable variable
+while we turned our attention to the other tree. Because we stop as
+soon as we find the first mismatched leaf, this solution does not have
+the flaw just mentioned of the solution that maps both trees to a list
+of leaves before beginning comparison.
+
+Since zippers are just continuations reified, we expect that the
+solution in terms of zippers can be reworked using continuations, and
+this is indeed the case. To make this work in the most convenient
+way, we need to use the fully general type for continuations just mentioned.
+
+tree_monadize (fun a k -> a, k a) t1 (fun t -> 0);;
+
+
The Binary Tree monad
---------------------
resulting from `bind u f` is a tree with the same strucure as `u`,
except that each leaf `a` has been replaced with `f a`:
-\tree (. (f a1) (. (. (. (f a2) (f a3)) (f a4)) (f a5)))
-
. .
__|__ __|__
| | | |
we'll give an example that will show how an inductive proof would
proceed. Let `f a = Node (Leaf a, Leaf a)`. Then
-\tree (. (. (. (. (a1) (a2)))))
-\tree (. (. (. (. (a1) (a1)) (. (a1) (a1)))))
-
.
____|____
. . | |