author Jim Pryor Fri, 24 Dec 2010 03:22:33 +0000 (22:22 -0500) committer Jim Pryor Fri, 24 Dec 2010 03:22:33 +0000 (22:22 -0500)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>
 hints/assignment_10_hint_2.mdwn patch | blob | history hints/assignment_10_hint_3.mdwn [new file with mode: 0644] patch | blob hints/assignment_10_hint_4.mdwn [new file with mode: 0644] patch | blob

index e69de29..83be68f 100644 (file)
@@ -0,0 +1,56 @@
+I'd work with a tree monadized with a `Continuation_monad`, that is, with:
+
+
+You could in theory also use the richer "monads.ml" library:
+
+
+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 (file)
index 0000000..6a442a0
--- /dev/null
@@ -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
+
+
+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;;
+
+
+
+        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;;
+
+
+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
+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 (file)
index 0000000..bb5a799
--- /dev/null
@@ -0,0 +1,86 @@
+Here's the solution:
+
+
+      fun (a : char) -> fun (env : char -> int) -> env a;;
+
+
+    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
+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
+
+
+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 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 = <fun>
+
+       (* 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 *)
+