ANSWER:
- let neq? = \n m. neg (num_eq? n m) in
- let mem? = \n xs. neg (empty? (drop_while (neq? n) xs)) in
- let without = \n xs. append (take_while (neq? n) xs) (tail (drop_while (neq? n) xs)) in
+ let not_equal? = \n m. neg (num_equal? n m) in
+ let mem? = \n xs. neg (empty? (drop_while (not_equal? n) xs)) in
+ let without = \n xs. append (take_while (not_equal? n) xs) (tail (drop_while (not_equal? n) xs)) in
let set_cons = \x xs. (mem? x xs) xs (cons x xs) in
let set_equal? = Y (\set_equal?. \xs ys. (empty? xs)
(empty? ys)
Your assignment is to write a Lambda Calculus function that expects a tree, encoded in the way just described, as an argument, and returns the sum of its leaves as a result. So for all of the trees listed above, it should return `1 + 2 + 3`, namely `6`. You can use any Lambda Calculus implementation of lists you like.
- ANSWER: TODO
+ ANSWER:
+ The tricky thing about defining these functions is that it's easy to unwittingly violate the conventions about how we're encoding trees. Thus `Leaf1 ≡ [1]` is a tree, and `[Leaf1, Leaf1, Leaf1]` is also a tree, but `[Leaf1]` is not a tree. (It's a singleton whose content is not a number, but rather a leaf, a list containing a number.) Thus when we are recursively processing `[Leaf1, Leaf1, Leaf1]`, we have to be careful not to just blindly call our function with the tail of our input, since when we get to the end the tail `[Leaf1]` is not itself a tree, on the conventions we've adopted. And our function is likely to rely on those conventions in such a way that it chokes when they are violated.
+
+ That understood, here is a recursive implementation of `sum_leaves`:
+
+ let singleton? = \xs. num_equal? one (length xs) in
+ let singleton = \x. cons x empty in
+ let doubleton = \x y. cons x (singleton y) in
+ let second = \xs. head (tail xs) in
+
+ let sum_leaves = Y (\sum_leaves. \t.
+ (singleton? t)
+ (head t)
+ ; else if t is a tree, it contains two or more subtrees
+ (add
+ (sum_leaves (head t))
+ ; don't recurse if (tail t) is a singleton
+ ((singleton? (tail t))
+ (sum_leaves (second t))
+ ; else it's ok to recurse
+ (sum_leaves (tail t))))) in
+ ...
-8. The **fringe** of a leaf-labeled tree is the list of values at its leaves, ordered from left-to-right. For example, the fringe of all three trees displayed above is the same list, `[1, 2, 3]`. We are going to return to the question of how to tell whether trees have the same fringe several times this course. We'll discover more interesting and more efficient ways to do it as our conceptual toolboxes get fuller. For now, we're going to explore the straightforward strategy. Write a function that expects a tree as an argument, and returns the list which is its fringe. Next write a function that expects two trees as arguments, converts each of them into their fringes, and then determines whether the two lists so produced are equal. (Convert your `list_equal?` function from last week's homework into the Lambda Calculus for this last step.)
- ANSWER: TODO
+8. The **fringe** of a leaf-labeled tree is the list of values at its leaves, ordered from left-to-right. For example, the fringe of all three trees displayed above is the same list, `[1, 2, 3]`. We are going to return to the question of how to tell whether trees have the same fringe several times this course. We'll discover more interesting and more efficient ways to do it as our conceptual toolboxes get fuller. For now, we're going to explore the straightforward strategy. Write a function that expects a tree as an argument, and returns the list which is its fringe. Next write a function that expects two trees as arguments, converts each of them into their fringes, and then determines whether the two lists so produced are equal. (Convert your `list_equal?` function from last week's homework into the Lambda Calculus for this last step.)
+ ANSWER using right-fold lists:
+
+ ; are xs strictly longer than ys?
+ let longer? = \xs ys. neg (leq? (length xs) (length ys)) in
+
+ ; uncons xs f ~~> f (head xs) (tail xs)
+ let uncons = \xs f. f (head xs) (tail xs) in
+
+ let check = \x p. p (\bool ys. uncons ys (\y ys. pair (and (num_equal? x y) bool) ys)) in
+ let finish = \bool ys. (empty? ys) bool false in
+ let list_equal? = \xs ys. (longer? xs ys) false (xs check (pair true (rev ys)) finish) in
+
+ let get_fringe = Y (\get_fringe. \t.
+ ; this uses a similar pattern to previous problem
+ (singleton? t)
+ t
+ ; else if t is a tree, it contains two or more subtrees
+ (append
+ (get_fringe (head t))
+ ; don't recurse if (tail t) is a singleton
+ ((singleton? (tail t))
+ (get_fringe (second t))
+ ; else it's ok to recurse
+ (get_fringe (tail t))))) in
+
+ Here is some test data:
+
+ let leaf1 = singleton 1 in
+ let leaf2 = singleton 2 in
+ let leaf3 = singleton 3 in
+ let t12 = doubleton leaf1 leaf2 in
+ let t23 = doubleton leaf2 leaf3 in
+ let alpha = cons leaf1 t23 in
+ let beta = doubleton t12 leaf3 in
+ let gamma = doubleton leaf1 t23 in
+ list_equal? (get_fringe gamma) (get_fringe alpha)
+
+ And here are some cleverer implementations of some of the functions used above:
+
+ let box = \a. \v. v a in
+ let singleton? = \xs. xs (\x b. box (b (K true))) (K false) not in
+
+ ; this function works by first converting [x1,x2,x3] into (true,(true,(true,(K false))))
+ ; then each element of ys unpacks that stack by applying its fst to its snd and itself
+ ; so long as we've not gotten to the end, this will have the result of selecting the snd each time
+ ; when we get to the end of the stack, ((K false) fst) ((K false) snd) (K false) ~~> K false
+ ; after ys are done iterating, we apply the result to fst, which will give us either true or ((K false) fst) ~~> false
+ let longer? = \xs ys. ys (\y p. (p fst) (p snd) p) (xs (\x. pair true) (K false)) fst in
+
+ let shift = \x t. t (\a b c. triple (cons x a) a (pair x))) in
+ let uncons = \xs. xs shift (triple empty empty (K err_head)) (\a b c. c b) in
+ ...
## Arithmetic infinity? ##