+***Non-required but strongly suggested work***: Here are some
+additional homework problems that will consolidate your understanding
+of what we've covered in the last weeks of the seminar. Those who are
+taking the class for credit: since we're so late to post these, and
+they add up to a substantial chunk of thinking, we won't officially
+require you to do them, since we don't want to get into a bureaucratic
+bind if you've planned your next month in a way that would not permit
+you to get the work done. But ***we strongly encourage*** you to work on
+the problem set: solving these problems will produce a qualitatively
+deeper understanding of continuations. If you plan to do some or all
+of these problems, and would like us to take them into account in our
+evaluation of your work for the course, please let us know when to
+expect to see them. (Up to the start of next term, which begins on 24
+January 2011, would be viable.)
+
+Of course, if you need help or want us to review your efforts, we'll be glad to discuss with you at any later point as well.
+
1. This problem is taken from _The Craft of Functional Programming_ by Simon Thompson, Addison-Wesley 1999 <http://www.cs.kent.ac.uk/people/staff/sjt/>:
As Ken Shan points out, this is an instance of the algorithm
- for converting name/year citations (like 'v. Montague 1970')
- to numerals corresponding to their ('v. [24]'). Except that
- bibliograpic numerals don't start with zero.
+ for converting name/year citations (like 'see Montague 1970')
+ 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,
leaf as soon as you see it?
Consider a variation in which you must replace each leaf with
- is number of occurrences in the tree. Is there any way to do
+ 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 leaf-labeled (no labels on the
- internal nodes), and that the leafs are, say, chars.
+ You can assume that the tree is binary, leaf-labeled (no
+ labels on the internal nodes), and that the leafs are, say,
+ chars.
Here is [a hint](/hints/assignment_10_hint).
Now, go back to the GS&V assignment from [[assignment7]]. Does the monad you've now crafted enable you to code your implementation of that semantics more elegantly? You can begin by using a composite store of the same sort we used in the hints: a pair of an assignment function `r` and some `h` that associates pegs with entities.
- Is the `h` really essential to your solution? Or could you do everything with a store consisting of a single mapping from variables to entities? (You'd still be working with a State monad, but without the pegs.) Explain why or why not.
+ Are the pegs and the `h` really essential to your solution? Or could you do everything with a store consisting of a single mapping from variables to entities? (You'd still be working with a State monad, but without the pegs.) Explain why or why not.
4. The next two exercises were taken from _The Little Schemer_ Chapter 8.
- Suppose `lst` is a list of Scheme symbols (`'symbols 'are 'things 'written 'like 'this`; a list of them is `'(written like this)`). And that the behavior of `(remove 'sym lst)` is to remove every occurrence of `'sym` from `lst`.
+ Suppose `lst` is a list of Scheme symbols (`'symbols 'are 'things 'written 'like 'this`; a list of them is `'(written like this)`). And suppose that the behavior of `(remove 'sym lst)` is to remove every occurrence of `'sym` from `lst`.
Now we define a function `remove-co` which has the following behavior. It accepts as arguments a symbol, a list, and a handler `k` (I wonder why we named it that). `remove-co` calls `k` with two arguments: first, a list of all the symbols in `lst` that aren't equal to `'sym`, and second, a list of all the symbols in `lst` that are equal to `'sym` (the handler might want to, for example, see what the length of the latter list is).