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.