+++ /dev/null
-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.