author Chris Barker Mon, 27 Sep 2010 18:57:57 +0000 (14:57 -0400) committer Chris Barker Mon, 27 Sep 2010 18:57:57 +0000 (14:57 -0400)
 assignment3.mdwn patch | blob | history

index 9039a95..775eb79 100644 (file)
@@ -65,13 +65,13 @@ same length.  That is,
listLenEq mylist (makeList meh (makeList meh nil))) ~~> false

listLenEq mylist (makeList meh (makeList meh nil))) ~~> false

-4. (Still easy) Now write the same function, but don't use the length function (hint: use `leq` as a model).
+4. (Still easy) Now write the same function, but don't use the length function.

5. In assignment 2, we discovered that version 3-type lists (the ones that
work like Church numerals) made it much easier to define operations

5. In assignment 2, we discovered that version 3-type 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,
+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 3 lists are within our
-reach.  Give definitions for such a map and a filter.
+reach.  Give definitions for `map` and a `filter` for verson 1 type lists.

6. Linguists analyze natural language expressions into trees.
We'll need trees in future weeks, and tree structures provide good

6. Linguists analyze natural language expressions into trees.
We'll need trees in future weeks, and tree structures provide good
@@ -94,16 +94,17 @@ Then we have the following representations:
</pre>

Limitations of this scheme include the following: there is no easy way
</pre>

Limitations of this scheme include the following: there is no easy way
-to label a constituent (typically a syntactic category, S or NP or VP,
+to label a constituent with a syntactic category (S or NP or VP,
etc.), and there is no way to represent a tree in which a mother has a
single daughter.

When processing a tree, you can test for whether the tree contains
only a numeral (in which case the tree is leaf node) by testing for
whether the length of the list is less than or equal to 1.  This will
etc.), and there is no way to represent a tree in which a mother has a
single daughter.

When processing a tree, you can test for whether the tree contains
only a numeral (in which case the tree is leaf node) by testing for
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 trees.
+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.
+#Write a function that sums the number of leaves in a tree.#
Expected behavior:

<pre>
Expected behavior:

<pre>
@@ -127,35 +128,5 @@ count-leaves tb ~~> 6
count-leaves tc ~~> 6
<pre>

count-leaves tc ~~> 6
<pre>

-Write a function that counts the number of leaves.
+#Write a function that counts the number of leaves.#

-
-
-
-[The following should be correct, but won't run in my browser:
-
-<pre>
-let factorial = Y (\fac n. isZero n 1 (mult n (fac (predecessor n)))) in
-
-let reverse =
-  Y (\rev l. isNil l nil
-                   (isNil (tail l) l
-                          (makeList (head (rev (tail l)))
-                                                   (rev (tail (rev (tail l))))))))) in
-
-reverse (makeList 1 (makeList 2 (makeList 3 nil)))
-</pre>
-
-It may require more resources than my browser is willing to devote to
-JavaScript.]
-
-; trees
-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