+I'd work with a tree monadized with a `Continuation_monad`, that is, with:
+
+ #use "path/to/tree_monadize.ml";;
+
+You could in theory also use the richer "monads.ml" library:
+
+ #use "path/to/monads.ml";;
+ module TC = Tree_monad.T(Continuation_monad);;
+ let tree_monadize = TC.distribute;;
+
+But I found it easier to work out the solution using the simpler "tree\_monadize.ml" library. The "monadize.ml" library enforces encapsulation in a way that's nice and sanitized, but makes experimentation more cumbersome.
+
+
+It makes debugging easier if we work with a tree whose starting leaf
+elements are differently types than the tree we aim to finish with. So:
+
+ let tree = Node(Leaf '1', Node(Leaf '2', Node(Leaf '3', Leaf '1')));;
+
+Now, we already know how to count the leaves using a continuation monad
+in tree shape:
+
+ let v0 = TreeCont.monadize (fun a k -> 1 + k a) tree (fun t -> 0);;
+
+There are two interesting functions here: we'll call them the "distributed" function `fun a k -> 1 + k a` and the "seed" function `fun t -> 0`.
+
+Our first step is to extend `v0` so that we count how many leaves there are
+of each value, rather than how many leaves in total:
+
+ let update_env e x = fun y -> (if x = y then 1 else 0) + e y;;
+
+ let v1 = TreeCont.monadize (fun a k e ->
+ let e_prev = k a e
+ in update_env e_prev a
+ ) tree (fun t e -> e) (fun a -> 0);;
+
+ (* now
+ v1 '0' ~~> 0
+ v1 '1' ~~> 2
+ v1 '2' ~~> 1
+ *)
+
+How does this work? Our distributed function (fun a k e -> ...) takes a leaf element a and a continuation k, which maps leaf elements and environments e to new environments.
+
+Our seed function here is the initial continuation. Instead of taking a leaf element and an env, it takes a tree of such elements and an env. In general, wherever the distributed function takes `'a`s, the seed function takes `'a tree`s.
+
+Here our seed function just ignores the tree and returns the env unchanged.
+
+What that gives us is a function from environments to environments. We give it
+an initial environment `fun a -> 0` to get started. We get back an
+environment `v1` that maps each leaf element to how many times that leaf
+element appeared in the tree we started with.
+
+OK? You might want to stop reading here, and see how much further you
+can get on your own.
+
+But there are [more hints](/hints/assignment_10_hint_3) if you need them.
--- /dev/null
+OK, here's the next step.
+
+We'll switch gears and work without the Continuation monad for a while
+(though eventually we'll come back there).
+
+We already know how to annotate the leaves of a tree as we visit
+them:
+
+ (* annotate leaves as they're visited *)
+
+ let annotater : int -> (int * int) State_monad.m =
+ fun (a : int) -> fun s -> ((a,s+1), s+1);;
+
+ let initial_store = 0 in
+ TreeState.monadize annotater t1 initial_store;;
+
+
+Let's try something similar, only this time we'll re-define our State
+monad so as to have a more complex store. We want our store to be not a
+simple `int`, but instead a `char -> int` environment.
+
+ module State_custom = struct
+ type store = char -> int
+ type 'a m = store -> ('a * store)
+ let unit a : 'a m = fun s -> (a,s)
+ let bind (u: 'a m) (f: 'a -> 'b m) : 'b m =
+ fun s -> let (a,s') = u s in f a s'
+ end;;
+ module TS = Tree_monadizer(State_custom);;
+
+
+While we're at it, let's re-define our Reader monad too:
+
+ module Reader_custom = struct
+ type env = char -> int
+ type 'a m = env -> 'a
+ let unit a : 'a m = fun e -> a
+ let bind (u: 'a m) (f: 'a -> 'b m) : 'b m =
+ fun e -> f (u e) e
+ end;;
+ module TR = Tree_monadizer(Reader_custom);;
+
+
+Now instead of annotating leaves with the current store, we'll convert
+the leaves into "askers" that will wait for an environment and return what that
+environment says about the original leaf. At the same time, we'll update the store so that it knows how many leafs of each value have been seen:
+
+
+ let annotater : char -> ((char -> int) -> int) State_custom.m =
+ fun a s -> ((fun e -> e a), update_env s a);;
+
+ let v2 = TS.monadize annotater tree (fun a -> 0);;
+
+
+The seed function here is an environment that by default maps every leaf
+element to 0. In the end, `v2` consists of a pair of a tree of askers, and a
+`char -> int` environment. We can use `TR.monadize` to convert that tree of
+askers into a tree-asker, that is, a function from an environment to a tree. And we then feed it the very environment that was `v2`'s final store:
+
+ let (tree',env) = v2
+ in TR.monadize (fun a -> a) tree' env;;
+
+
+This gives us a tree of `int`s, where each `int` replaces the original `char`
+with the number of times the `char` appeared in the original tree.
+
+
+
+We've got our answer, but the way we did it boils down to asking for two traversals. Can we do better?
+
+
+That's debatable. It won't be possible to avoid two traversals taking place,
+somewhere. But we can try to avoid *asking* for two traversals. We can aim for
+code that only asks for a single traversal---whatever else is needed gets
+forced by the plumbing.
+
+Will doing so make our program clearer? No, probably not. But it should be
+a useful step towards a better understanding of continuations.
+
+
+How shall we do it? Instead of a State monad paired with
+Reader monad, let's use a Continuation monad paired with Reader monad.
+The Continuation monad will take over the State monad's job of modifying the
+environment we're working with.
+
+
+OK? You might want to stop reading here, and see how much further you
+can get on your own.
+
+But there's [a solution and explanation](/hints/assignment_10_hint_4) posted if you need them.
--- /dev/null
+Here's the solution:
+
+
+ let asker : char -> int Reader_custom.m =
+ fun (a : char) -> fun (env : char -> int) -> env a;;
+
+ let seed t = TR.monadize asker t;;
+
+ let v3 = TreeCont.monadize (fun a k ->
+ fun e -> k a (update_env e a)
+ ) tree seed (fun a -> 0);;
+
+
+What's going on here? Our distributed function takes a leaf element `a`,
+a continuation `k` (which takes leaf elements and environments), and an
+environment `e`, and returns the result of passing the leaf element and
+an updated environment to `k`.
+
+As always, the seed function operates on trees of leaf elements where
+the distributed function operated on leaf elements. So the seed function
+takes a tree and a environment, and returns whatever you want.
+
+What we want is a tree-reader, that is, a function from environments to
+trees. Once this gets distributed over the tree using the
+`TreeCont.monadize` function, we'll have a tree-reader that operates on
+the updated environment instead of the initial environment (which we
+still have to supply---it's the final `fun a -> 0`).
+
+
+How can we build such a tree-reader? The same way we formerly turned a tree
+of `int`s and an int-to-b-reader function into a b-tree-reader: using the `TR.monadize` function.
+
+
+And `v3` is just what we were looking for:
+
+ Node (Leaf 2, Node (Leaf 1, Node (Leaf 1, Leaf 2))).
+
+
+
+
+Now all of this should be implementable in the "monads.ml" library too. But as
+I said earlier, the encapsulation enforced by that library may make it somewhat harder to work with.
+
+
+ module T = Tree_monad;;
+ module C = Continuation_monad;;
+ module S = State_monad(struct type store = char -> int end);;
+ module R = Reader_monad(struct type env = char -> int end);;
+ module TC = T.T(C);;
+ module TS = T.T(S);;
+ module TR = T.T(R);;
+
+
+ # let v0 = TC.(run_exn (distribute (fun a ->
+ C.(shift (fun k -> k a >>= fun v -> unit (1+v)))
+ ) tree)) (fun a -> 0);;
+ - : int = 5
+
+
+ # let v1 = TC.(run_exn (distribute (fun a ->
+ C.(shift (fun k -> k a >>= fun ka ->
+ unit (fun e -> let e_prev = ka e in (update_env e_prev a))))
+ ) tree)) (fun t e -> e) (fun a -> 0);;
+ - : char -> int = <fun>
+
+ (* now
+ v1 '0';; ~~> 0
+ v1 '1';; ~~> 2
+ v1 '2';; ~~> 1
+ *)
+
+ # let v2 = TS.(run (distribute annotater tree)) (fun a -> 0);;
+ # let (tree',env) = v2 in TR.(run (distribute (fun a -> a) tree')) env;;
+
+ (* returns tree with leafs replaced with their numbers of occurrences *)
+
+
+ # let v3 = TC.(run_exn (distribute (fun a ->
+ C.(shift (fun k -> k a >>= fun ka ->
+ unit (fun e -> ka (update_env e a))))
+ ) tree)) (fun t ->
+ TR.(run(distribute (fun a -> R.asks (fun e -> e a)) (Some t)))
+ ) (fun a -> 0);;
+
+ (* also returns tree with leafs replaced with their numbers of occurrences *)
+