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_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' ->
+ state_bind (tree_monadize f l) (fun 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
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
---------------------