XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment3.mdwn;h=e91eeee58765ddf36d5f331b42de2d8e6ee84c5e;hp=f669cb1e6488906d7d2baf66d27927d91abf1ab0;hb=ce6877027e00cdb159651cddba03addb5208e875;hpb=c0674bbb2f8587d3fd625277628140a99b52a9d6
diff git a/assignment3.mdwn b/assignment3.mdwn
index f669cb1e..e91eeee5 100644
 a/assignment3.mdwn
+++ b/assignment3.mdwn
@@ 4,7 +4,7 @@ Assignment 3
Once again, the lambda evaluator will make working through this
assignment much faster and more secure.
*Writing recursive functions on version 1 style lists*
+#Writing recursive functions on version 1 style lists#
Recall that version 1 style lists are constructed like this (see
[[lists and numbers]]):
@@ 70,10 +70,12 @@ same length. That is,
5. In assignment 2, we discovered that version 3type lists (the ones that
work like Church numerals) made it much easier to define operations
like `map` and `filter`. But now that we have recursion in our toolbox,
reasonable map and filter functions for version 3 lists are within our
+reasonable map and filter functions for version 1 lists are within our
reach. Give definitions for `map` and a `filter` for verson 1 type lists.
6. Linguists analyze natural language expressions into trees.
+#Computing with trees#
+
+Linguists analyze natural language expressions into trees.
We'll need trees in future weeks, and tree structures provide good
opportunities for learning how to write recursive functions.
Making use of the resources we have at the moment, we can approximate
@@ 87,7 +89,7 @@ Then we have the following representations:
(a) (b) (c)
.
/\ /\ /\
 /  \ /\ 3 1/\
+ /  \ /\ 3 1 /\
1 2 3 1 2 2 3
[[1];[2];[3]] [[[1];[2]];[3]] [[1];[[2];[3]]]
@@ 104,28 +106,29 @@ whether the length of the list is less than or equal to 1. This will
be your base case for your recursive functions that operate on these
trees.
#Write a function that sums the number of leaves in a tree.#
+1. Write a function that sums the number of leaves in a tree.
+
Expected behavior:
let t1 = (makelist 1 nil) in
let t2 = (makelist 2 nil) in
let t3 = (makelist 3 nil) in
let t12 = (makelist t1 (makelist t2 nil)) in
let t23 = (makelist t2 (makelist t3 nil)) in
let ta = (makelist t1 t23) in
let tb = (makelist t12 t3) in
let tc = (makelist t1 (makelist t23 nil)) in

countleaves t1 ~~> 1
countleaves t2 ~~> 2
countleaves t3 ~~> 3
countleaves t12 ~~> 3
countleaves t23 ~~> 5
countleaves ta ~~> 6
countleaves tb ~~> 6
countleaves tc ~~> 6
+let t1 = (makeList 1 nil) in
+let t2 = (makeList 2 nil) in
+let t3 = (makeList 3 nil) in
+let t12 = (makeList t1 (makeList t2 nil)) in
+let t23 = (makeList t2 (makeList t3 nil)) in
+let ta = (makeList t1 t23) in
+let tb = (makeList t12 t3) in
+let tc = (makeList t1 (makeList t23 nil)) in
+
+sumleaves t1 ~~> 1
+sumleaves t2 ~~> 2
+sumleaves t3 ~~> 3
+sumleaves t12 ~~> 3
+sumleaves t23 ~~> 5
+sumleaves ta ~~> 6
+sumleaves tb ~~> 6
+sumleaves tc ~~> 6
#Write a function that counts the number of leaves.#
+2. Write a function that counts the number of leaves.