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]]):
let succ = \n s z. s (n s z) in
let mult = \m n s. m (n s) in
let length = Y (\length l. isNil l 0 (succ (length (tail l)))) in
-let pred = \n. isZero n 0 (length (tail (n (\p. makeList meh p) nil))) in
+let pred = \n. isZero n 0 (length (tail (n (\p. makeList meh p) nil)))
+in
let leq = \m n. isZero(n pred m) in
let eq = \m n. and (leq m n)(leq n m) in
interpreter; web pages are not supposed to be that computationally
intensive).
-3. (Easy) Write a function `listLenEq` that returns true just in case two lists have the
+3. (Easy) Write a function `listLenEq` that returns true just in case
+two lists have the
same length. That is,
- listLenEq mylist (makeList meh (makeList meh (makeList meh nil))) ~~> true
+ listLenEq mylist (makeList meh (makeList meh (makeList meh nil)))
+ ~~> true
listLenEq mylist (makeList meh (makeList meh nil))) ~~> false
-4. (Still easy) Now write the same function, but don't use the length function.
+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
+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,
-reasonable map and filter functions for version 3 lists are within our
-reach. Give definitions for `map` and a `filter` for verson 1 type lists.
+like `map` and `filter`. But now that we have recursion in our
+toolbox,
+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
(a) (b) (c)
.
/|\ /\ /\
- / | \ /\ 3 1/\
+ / | \ /\ 3 1 /\
1 2 3 1 2 2 3
[[1];[2];[3]] [[[1];[2]];[3]] [[1];[[2];[3]]]
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.#
-Expected behavior:
+1. Write a function that sums the number of leaves in a tree.
-<pre>
+Expected behavior:
-let t1 = (make-list 1 nil) in
-let t2 = (make-list 2 nil) in
-let t3 = (make-list 3 nil) in
-let t12 = (make-list t1 (make-list t2 nil)) in
-let t23 = (make-list t2 (make-list t3 nil)) in
-let ta = (make-list t1 t23) in
-let tb = (make-list t12 t3) in
-let tc = (make-list t1 (make-list t23 nil)) in
-
-count-leaves t1 ~~> 1
-count-leaves t2 ~~> 2
-count-leaves t3 ~~> 3
-count-leaves t12 ~~> 3
-count-leaves t23 ~~> 5
-count-leaves ta ~~> 6
-count-leaves tb ~~> 6
-count-leaves tc ~~> 6
<pre>
+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
+
+sum-leaves t1 ~~> 1
+sum-leaves t2 ~~> 2
+sum-leaves t3 ~~> 3
+sum-leaves t12 ~~> 3
+sum-leaves t23 ~~> 5
+sum-leaves ta ~~> 6
+sum-leaves tb ~~> 6
+sum-leaves tc ~~> 6
+</pre>
-#Write a function that counts the number of leaves.#
+2. Write a function that counts the number of leaves.