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.
We could proceed in two ways: we could either convert the leafs into "askers" now, and then use `TR.monadize` to conver the tree of askers into a tree-asker (that is, a function from an environment to a tree). Or we could just pass the leaves through unchanged for the moment, and leave the job of converting them to askers to the `TR.monadize` pass. We'll take the second strategy. (This turns out to fit better with what we go on to do later.) Hence, this first pass, using `TS.monadize`, only has to update the store.
let annotater : char -> char State_custom.m =
fun a s -> (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 and a
`char -> int` environment. We can use `TR.monadize` to convert that tree 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 asker : char -> int Reader_custom.m =
fun (a : char) -> fun (env : char -> int) -> env a;;
let (t, env) = v2
in TR.monadize asker t 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.