X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment10.mdwn;h=004f8dfb22ebb43233c2b15c038ad4a98a081494;hp=8f52ca20370e879efa536b7d720c5a7d21a6c6dd;hb=61612ba6746dc4646fb0d5bb1c9e1864bf927848;hpb=21c2f56ceac1e9445ee7cc8e15786e9521a40b9b diff --git a/assignment10.mdwn b/assignment10.mdwn index 8f52ca20..004f8dfb 100644 --- a/assignment10.mdwn +++ b/assignment10.mdwn @@ -1,3 +1,20 @@ +***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 : @@ -10,9 +27,10 @@ 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, @@ -22,11 +40,12 @@ 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). @@ -73,11 +92,11 @@ 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).