summary |
shortlog |
log |
commit | commitdiff |
tree
raw |
patch |
inline | side by side (from parent 1:
21c2f56)
Signed-off-by: Jim Pryor <profjim@jimpryor.net>
+Here are some additional homeworks, 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 require you to do them. But we will strongly encourage it. If you'd like to do them, and have us take account of your efforts when deciding on grades, let us know now when you propose to submit the work. (Up to the start of next term 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/>:
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
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
+ 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.
Give some thought to efficiency: there are straightforward
bibliograpic numerals don't start with zero.
Give some thought to efficiency: there are straightforward
leaf as soon as you see it?
Consider a variation in which you must replace each leaf with
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
that with a single traversal?
You can assume that the tree is leaf-labeled (no labels on the
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.
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.
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).
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).
-We'll give you hint, but it will involve some extra work.
+We'll give you a hint, but it will require some extra thought.
-The hint is a solution to this exercise taken from the source code that accompanies the Glasgow Haskell Compiler. (Underneath /Control/Monad/State/Strict.hs).
+The hint is a solution to this exercise taken from the source code that accompanies the Glasgow Haskell Compiler (underneath */Control/Monad/State/Strict.hs*).
We're not going to massage it in any way. If you want to make use of it, you'll have to figure out for yourself what's going on. This should be within your reach at this point. See our page on
We're not going to massage it in any way. If you want to make use of it, you'll have to figure out for yourself what's going on. This should be within your reach at this point. See our page on
-[[translating between OCaml Scheme and Haskell]] for guidance.
+[[translating between OCaml Scheme and Haskell]] for guidance. See our [[state monad tutorial]] for explanation of `get` and `put`.
-Also, you'll notice that this solution targets trees with labels on their inner nodes, instead of on their leaves. You should be able to get this to work for leaf-labeled trees, too.
+Also, you'll notice that this solution targets trees with labels on their inner nodes, instead of on their leaves. It shouldn't be too hard to get a similar strategy to work for leaf-labeled trees.
data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show, Eq)
data Tree a = Nil | Node a (Tree a) (Tree a) deriving (Show, Eq)
numTree t = evalState (numberTree t) []
testTree = Node "Zero" (Node "One" (Node "Two" Nil Nil) (Node "One" (Node "Zero" Nil Nil) Nil)) Nil
numTree t = evalState (numberTree t) []
testTree = Node "Zero" (Node "One" (Node "Two" Nil Nil) (Node "One" (Node "Zero" Nil Nil) Nil)) Nil
- numTree testTree => Node 0 (Node 1 (Node 2 Nil Nil) (Node 1 (Node 0 Nil Nil) Nil)) Nil
+ numTree testTree
+
+ ~~> Node 0 (Node 1 (Node 2 Nil Nil) (Node 1 (Node 0 Nil Nil) Nil)) Nil