+***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,
solution that traverses the tree exactly once, replacing each
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
- that with a single traversal?
+ You can assume that the tree is binary, leaf-labeled (no
+ labels on the internal nodes), and that the leafs are, say,
+ chars.
- You can assume that the tree is leaf-labeled (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? (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 leaf-labeled, 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:
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.
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).
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 non-instances?
+ <!--
+ (define remove-co
+ (lambda (a lst k)
+ (cond
+ ((null? lst)
+ (k '() '()))
+ ((eq? (car lst) a)
+ (remove-co a (cdr lst) (lambda (left right) (k left (cons (car lst) right)))))
+ (else
+ (remove-co a (cdr lst) (lambda (left right) (k (cons (car lst) left) right)))))))
+ -->
+
5. Now we define a function `insert-co` 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 "to-the-left" insertions that were made, and the number of "to-the-right" 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.
(else
(insert-co new before after (cdr lst) (lambda (new-lst lefts rights) ________))))))
+ <!--
+ (define insert-co
+ (lambda (new before after lst k)
+ (cond
+ ((null? lst)
+ (k '() 0 0))
+ ((eq? (car lst) before)
+ (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons new (cons before new-lst)) (succ lefts) rights))))
+ ((eq? (car lst) after)
+ (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons after (cons new new-lst)) lefts (succ rights)))))
+ (else
+ (insert-co new before after (cdr lst) (lambda (new-lst lefts rights) (k (cons (car lst) new-lst) 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