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 if you need them.