-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 typed 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 ->
- fun e0 ->
- let ecur = k a e0
- in update_env ecur 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 -> ...` takes a leaf element `a` and a continuation `k`, which maps leaf elements and environments `e0` to new environments `ecur`. It gives back a function from `e0` to an updated version of `ecur`.
-
-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.