1 I'd work with a tree monadized with a `Continuation_monad`, that is, with:
5 You could in theory also use the richer "monads.ml" library:
11 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.
14 It makes debugging easier if we work with a tree whose starting leaf
15 elements are differently typed than the tree we aim to finish with. So:
17     let tree = Node(Leaf '1', Node(Leaf '2', Node(Leaf '3', Leaf '1')));;
19 Now, we already know how to count the leaves using a Continuation monad
20 in tree shape:
22     let v0 = TreeCont.monadize (fun a k -> 1 + k a) tree (fun t -> 0);;
24 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`.
26 Our first step is to extend `v0` so that we count how many leaves there are
27 of each value, rather than how many leaves in total:
29     let update_env e x = fun y -> (if x = y then 1 else 0) + e y;;
31     let v1 = TreeCont.monadize (fun a k e0 ->
32             let ecur = k a e0
33         in update_env ecur a
34     ) tree (fun t e -> e) (fun a -> 0);;
36         (* now
37        v1 '0' ~~> 0
38        v1 '1' ~~> 2
39        v1 '2' ~~> 1
40          *)
42 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 `e0` to new environments `ecur`. It gives back a function from `e0` to an updated version of `ecur`.
44 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.
46 Here our seed function just ignores the tree and returns the env unchanged.
48 What that gives us is a function from environments to environments. We give it
49 an initial environment `fun a -> 0` to get started. We get back an
50 environment `v1` that maps each leaf element to how many times that leaf
51 element appeared in the tree we started with.
53 OK? You might want to stop reading here, and see how much further you
54 can get on your own.
56 But there are [more hints](/hints/assignment_10_hint_3) if you need them.