X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;ds=sidebyside;f=assignment3.mdwn;h=e240b732b1405e176d696bbab3c5974a1d125f35;hb=6c5c9ad0e2612ab4dabdfd70f0496817ff0cb41a;hp=1ce112ea8d1e6ba21e1886b174614d4e9c156c0e;hpb=daf4849794acb02a9d5393f2da7574b3e1d28cf1;p=lambda.git diff --git a/assignment3.mdwn b/assignment3.mdwn index 1ce112ea..e240b732 100644 --- a/assignment3.mdwn +++ b/assignment3.mdwn @@ -1,47 +1,59 @@ Assignment 3 ------------ -Once again, the lambda evaluator will make working through this -assignment much faster and more secure. +Erratum corrected 11PM Sun 3 Oct: the following line -*Writing recursive functions on version 1 style lists* + let tb = (make_list t12 (make_list t3 empty)) in -Recall that version 1 style lists are constructed like this: +originally read -
-; booleans -let true = \x y. x in -let false = \x y. y in -let and = \l r. l (r true false) false in - -; version 1 lists -let makePair = \f s g. g f s in -let fst = true in -let snd = false in -let nil = makePair true meh in -let isNil = \x. x fst in -let makeList = \h t. makePair false (makePair h t) in -let head = \l. isNil l err (l snd fst) in -let tail = \l. isNil l err (l snd snd) in - -; a list of numbers to experiment on -let mylist = makeList 1 (makeList 2 (makeList 3 nil)) in - -; a fixed-point combinator for defining recursive functions -let Y = \f. (\h. f (h h)) (\h. f (h h)) in - -; church numerals -let isZero = \n. n (\x. false) true in -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 predecessor = \n. length (tail (n (\p. makeList meh p) nil)) in -let leq = ; (leq m n) will be true iff m is less than or equal to n - Y (\leq m n. isZero m true (isZero n false (leq (predecessor m)(predecessor n)))) in -let eq = \m n. and (leq m n)(leq n m) in - -eq 3 3 -+ let tb = (make_list t12 t3) in + +This has been corrected below, and in the preloaded evaluator for +working on assignment 3, available here: [[assignment 3 evaluator]]. + +
- (a) (b) (c) + (a) (b) (c) . /|\ /\ /\ - / | \ /\ 3 1/\ + / | \ /\ 3 1 /\ 1 2 3 1 2 2 3 [[1];[2];[3]] [[[1];[2]];[3]] [[1];[[2];[3]]]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 -be your base case for your recursive functions that operate on trees. - -Write a function that sums the number of leaves in a tree. -Expected behavior: +be your base case for your recursive functions that operate on these +trees. -
- -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 -- -Write a function that counts the number of leaves. ++ -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+
- Write a function that sums the values at the leaves in a tree. +Expected behavior: + let t1 = (make_list 1 empty) in + let t2 = (make_list 2 empty) in + let t3 = (make_list 3 empty) in + let t12 = (make_list t1 (make_list t2 empty)) in + let t23 = (make_list t2 (make_list t3 empty)) in + let ta = (make_list t1 t23) in + let tb = (make_list t12 (make_list t3 empty)) in + let tc = (make_list t1 (make_list t23 empty)) 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 -[The following should be correct, but won't run in my browser: -
-let factorial = Y (\fac n. isZero n 1 (mult n (fac (predecessor n)))) in +- Write a function that counts the number of leaves. -let reverse = - Y (\rev l. isNil l nil - (isNil (tail l) l - (makeList (head (rev (tail l))) - (rev (makeList (head l) - (rev (tail (rev (tail l))))))))) in - -reverse (makeList 1 (makeList 2 (makeList 3 nil))) -