-; 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 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 - -eq 2 2 yes no -+ ; 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 make_pair = \f s g. g f s in + let fst = true in + let snd = false in + let empty = make_pair true junk in + let isempty = \x. x fst in + let make_list = \h t. make_pair false (make_pair h t) in + let head = \l. isempty l err (l snd fst) in + let tail = \l. isempty l err (l snd snd) in + + ; a list of numbers to experiment on + let mylist = make_list 1 (make_list 2 (make_list 3 empty)) 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. isempty l 0 (succ (length (tail l)))) in + let pred = \n. iszero n 0 (length (tail (n (\p. make_list junk p) empty))) + in + let leq = \m n. iszero(n pred m) in + let eq = \m n. and (leq m n)(leq n m) in + + eq 2 2 yes no Then `length mylist` evaluates to 3. @@ -62,10 +60,10 @@ intensive). two lists have the same length. That is, - listLenEq mylist (makeList meh (makeList meh (makeList meh nil))) + listLenEq mylist (make_list junk (make_list junk (make_list junk empty))) ~~> true - listLenEq mylist (makeList meh (makeList meh nil))) ~~> false + listLenEq mylist (make_list junk (make_list junk empty))) ~~> false 4. (Still easy) Now write the same function, but don't use the length @@ -82,18 +80,20 @@ lists. #Computing with trees# -Linguists analyze natural language expressions into 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 trees as follows: instead of words, we'll use Church numerals. Then a tree will be a (version 1 type) list in which each element is -itself a tree. For simplicity, we'll adopt the convention that -a tree of length 1 must contain a number as its only element. +itself a tree. For simplicity, we'll adopt the convention that +a tree of length 1 must contain a number as its only element. + Then we have the following representations:

- (a) (b) (c) + (a) (b) (c) . /|\ /\ /\ / | \ /\ 3 1 /\ @@ -117,25 +117,24 @@ trees. 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 - -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 -+ 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 t3) 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 + 2. Write a function that counts the number of leaves. -- 2.11.0