+`'b reader` with `'b state`, and substituting in the appropriate unit and bind:
+
+ let rec tree_monadize (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 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:
+
+ # tree_monadize (fun a -> fun s -> (a, s+1)) t1 0;;
+ - : int tree * int =
+ (Node (Node (Leaf 2, Leaf 3), Node (Leaf 5, Node (Leaf 7, Leaf 11))), 5)
+
+ .
+ ___|___
+ | |
+ . .
+ _|__ _|__ , 5
+ | | | |
+ 2 3 5 .
+ _|__
+ | |
+ 7 11
+
+Note that the value returned is a pair consisting of a tree and an
+integer, 5, which represents the count of the leaves in the tree.
+
+Why does this work? Because the operation `fun a -> fun s -> (a, s+1)`
+takes an `int` and wraps it in an `int state` monadic box that
+increments the state. When we give that same operations to our
+`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
+
+ # tree_monadize (fun i -> [ [i; square i] ]) t1;;
+ - : int list tree list =
+ [Node
+ (Node (Leaf [2; 4], Leaf [3; 9]),
+ Node (Leaf [5; 25], Node (Leaf [7; 49], Leaf [11; 121])))]
+
+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.
+
+[Why is the argument to `tree_monadize` `int -> int list list` instead
+of `int -> int list`? Well, as usual, the List monad bind operation
+will erase the outer list box, so if we want to replace the leaves
+with lists, we have to nest the replacement lists inside a disposable
+box.]
+
+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;;
+ 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 =
+ 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' ->
+ 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 `'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? 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 _ -> []`. Then given what we've
+said about `tree_monadize`, what should we expect `tree_monadize (fun
+a -> fun k -> a :: k a` to do?
+
+In a moment, we'll return to the same-fringe problem. Since the
+simple but inefficient way to solve it is to map each tree to a list
+of its leaves, this transformation is on the path to a more efficient
+solution. We'll just have to figure out how to postpone computing the
+tail of the list until its needed...
+
+The Continuation monad is amazingly flexible; we can use it to
+simulate some of the computations performed above. To see how, first
+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 t -> t);;
+ - : int tree =
+ Node (Node (Leaf 2, Leaf 3), Node (Leaf 5, Node (Leaf 7, Leaf 11)))
+
+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 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 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 t -> 0);;
+ - : int = 5
+
+[To be fixed: exactly which kind of monad each of these computations simulates.]
+
+We could simulate the tree state example too by setting the relevant
+type to `('a, 'state -> 'result) continuation`.
+In fact, Andre Filinsky has suggested that the continuation monad is
+able to simulate any other monad (Google for "mother of all monads").
+
+We would eventually want to generalize the continuation type to
+
+ type ('a, 'b, 'c) continuation = ('a -> 'b) -> 'c;;
+
+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 problem, recall, is to take two trees and decide whether they have
+the same leaves in the same order.