XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment10.mdwn;h=ba4df372f42db83b4479c27249f32e8882a50ec0;hp=1a17b13ce692194de688c82a9dcc8327caac4363;hb=eb2ba5bdeb1e0153af2a7de0b88b871b65d38c82;hpb=0d7b3e7a98bc48ad86a61f418f637197742d6421
diff git a/assignment10.mdwn b/assignment10.mdwn
index 1a17b13c..ba4df372 100644
 a/assignment10.mdwn
+++ b/assignment10.mdwn
@@ 28,8 +28,9 @@ Of course, if you need help or want us to review your efforts, we'll be glad to
As Ken Shan points out, this is an instance of the algorithm
for converting name/year citations (like 'see Montague 1970')
 to numerals corresponding to their ('see [24]'). Except that
 bibliograpic numerals don't start with zero.
+ to numerals corresponding to their position in the
+ bibliography ('see [24]'). Except that bibliographic numerals
+ don't start with zero.
Give some thought to efficiency: there are straightforward
solutions that involve traversing the tree once (in order to,
@@ 38,14 +39,16 @@ Of course, if you need help or want us to review your efforts, we'll be glad to
solution that traverses the tree exactly once, replacing each
leaf as soon as you see it?
+ You can assume that the tree is binary, leaflabeled (no
+ labels on the internal nodes), and that the leafs are, say,
+ chars.
+
+ Here is [a hint](/hints/assignment_10_hint_1).
+
Consider a variation in which you must replace each leaf with
its number of occurrences in the tree. Is there any way to do
 that with a single traversal?

 You can assume that the tree is leaflabeled (no labels on the
 internal nodes), and that the leafs are, say, chars.
+ that with a single traversal? (Here is [a hint](/hints/assignment_10_hint_2).)
 Here is [a hint](/hints/assignment_10_hint).
2. Armed with your solution to problem 1, try this: you have as input a leaflabeled, binary tree whose labels are strings. You also have as input an interpretation function from strings to meanings. Let the meanings of your strings be primitive elements, for instance:
@@ 71,7 +74,7 @@ Of course, if you need help or want us to review your efforts, we'll be glad to
fun s > M.bind (u s) (fun (a, s') > f a s');;
let elevate (m : 'a M) : 'a stateT(M) =
 fun s > Wrapped.bind w (fun a > Wrapped.unit (a, s));;
+ fun s > M.bind w (fun a > M.unit (a, s));;
That won't compile in OCaml because we use the `M`s in a way that's intuitive but unrecognized by OCaml. What OCaml will recognize is more complex. Don't worry; you won't need to code a general implementation of StateT.
@@ 112,6 +115,18 @@ Of course, if you need help or want us to review your efforts, we'll be glad to
What would be a helper function you could supply as a `k` that would report `#t` iff the original `lst` contained more instances of some symbol than noninstances?
+
+
5. Now we define a function `insertco` which has the following behavior. It accepts as arguments three symbols, a list, and a handler. The first symbol is inserted before (to the left of) any occurrences in the list of the second symbol, and after (to the right of) any occurrences of the third symbol. The handler is then called with three arguments: the new list (with the insertions made), the number of "totheleft" insertions that were made, and the number of "totheright" insertions that were made.
Here is a partial implementation. You should fill in the blanks. If you get stuck, you can consult the walkthough in _The Little Schemer_, or talk to us.
@@ 128,6 +143,20 @@ Of course, if you need help or want us to review your efforts, we'll be glad to
(else
(insertco new before after (cdr lst) (lambda (newlst lefts rights) ________))))))
+
+
6. Go back to the "abSd" problem we presented in [[From List Zippers to Continuations]]. Consider the "tc" solution which uses
explicitly passed continuations. Try to reimplement this using reset