4 Once again, the lambda evaluator will make working through this
5 assignment much faster and more secure.
7 *Writing recursive functions on version 1 style lists*
9 Recall that version 1 style lists are constructed like this:
13 let false = \x y. y in
14 let makePair = \f s g. g f s in
15 let nil = makePair true meh in
16 let makeList = \h t. makePair false (makePair h t) in
17 let mylist = makeList 1 (makeList 2 (makeList 3 nil)) in
20 let isNil = \x. x fst in
21 let head = \l. isNil l err (l snd fst) in
22 let tail = \l. isNil l err (l snd snd) in
23 let succ = \n s z. s (n s z) in
24 let Y = \f. (\h. f (h h)) (\h. f (h h)) in
25 let length = Y (\length l. isNil l 0 (succ (length (tail l)))) in
30 Then `length mylist` evaluates to 3.
32 What does `head (tail (tail mylist))` evaluate to?