From: Jim Pryor Date: Fri, 24 Dec 2010 03:22:33 +0000 (-0500) Subject: ass10 hints X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=e8c44d33c131b04cf7b61f083a4a4f59d2484d84 ass10 hints Signed-off-by: Jim Pryor --- diff --git a/hints/assignment_10_hint_2.mdwn b/hints/assignment_10_hint_2.mdwn index e69de29b..83be68fb 100644 --- a/hints/assignment_10_hint_2.mdwn +++ b/hints/assignment_10_hint_2.mdwn @@ -0,0 +1,56 @@ +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 types 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 e -> + let e_prev = k a e + in update_env e_prev 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 e -> ...) takes a leaf element a and a continuation k, which maps leaf elements and environments e to new environments. + +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](/hints/assignment_10_hint_3) if you need them. diff --git a/hints/assignment_10_hint_3.mdwn b/hints/assignment_10_hint_3.mdwn new file mode 100644 index 00000000..6a442a09 --- /dev/null +++ b/hints/assignment_10_hint_3.mdwn @@ -0,0 +1,90 @@ +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. diff --git a/hints/assignment_10_hint_4.mdwn b/hints/assignment_10_hint_4.mdwn new file mode 100644 index 00000000..bb5a7997 --- /dev/null +++ b/hints/assignment_10_hint_4.mdwn @@ -0,0 +1,86 @@ +Here's the solution: + + + let asker : char -> int Reader_custom.m = + fun (a : char) -> fun (env : char -> int) -> env a;; + + let seed t = TR.monadize asker t;; + + let v3 = TreeCont.monadize (fun a k -> + fun e -> k a (update_env e a) + ) tree seed (fun a -> 0);; + + +What's going on here? Our distributed function takes a leaf element `a`, +a continuation `k` (which takes leaf elements and environments), and an +environment `e`, and returns the result of passing the leaf element and +an updated environment to `k`. + +As always, the seed function operates on trees of leaf elements where +the distributed function operated on leaf elements. So the seed function +takes a tree and a environment, and returns whatever you want. + +What we want is a tree-reader, that is, a function from environments to +trees. Once this gets distributed over the tree using the +`TreeCont.monadize` function, we'll have a tree-reader that operates on +the updated environment instead of the initial environment (which we +still have to supply---it's the final `fun a -> 0`). + + +How can we build such a tree-reader? The same way we formerly turned a tree +of `int`s and an int-to-b-reader function into a b-tree-reader: using the `TR.monadize` function. + + +And `v3` is just what we were looking for: + + Node (Leaf 2, Node (Leaf 1, Node (Leaf 1, Leaf 2))). + + + + +Now all of this should be implementable in the "monads.ml" library too. But as +I said earlier, the encapsulation enforced by that library may make it somewhat harder to work with. + + + module T = Tree_monad;; + module C = Continuation_monad;; + module S = State_monad(struct type store = char -> int end);; + module R = Reader_monad(struct type env = char -> int end);; + module TC = T.T(C);; + module TS = T.T(S);; + module TR = T.T(R);; + + + # let v0 = TC.(run_exn (distribute (fun a -> + C.(shift (fun k -> k a >>= fun v -> unit (1+v))) + ) tree)) (fun a -> 0);; + - : int = 5 + + + # let v1 = TC.(run_exn (distribute (fun a -> + C.(shift (fun k -> k a >>= fun ka -> + unit (fun e -> let e_prev = ka e in (update_env e_prev a)))) + ) tree)) (fun t e -> e) (fun a -> 0);; + - : char -> int = + + (* now + v1 '0';; ~~> 0 + v1 '1';; ~~> 2 + v1 '2';; ~~> 1 + *) + + # let v2 = TS.(run (distribute annotater tree)) (fun a -> 0);; + # let (tree',env) = v2 in TR.(run (distribute (fun a -> a) tree')) env;; + + (* returns tree with leafs replaced with their numbers of occurrences *) + + + # let v3 = TC.(run_exn (distribute (fun a -> + C.(shift (fun k -> k a >>= fun ka -> + unit (fun e -> ka (update_env e a)))) + ) tree)) (fun t -> + TR.(run(distribute (fun a -> R.asks (fun e -> e a)) (Some t))) + ) (fun a -> 0);; + + (* also returns tree with leafs replaced with their numbers of occurrences *) +