assignment3.mdwn

   1 Assignment 3
   2 ------------
   3
   4 Once again, the lambda evaluator will make working through this
   5 assignment much faster and more secure.
   6
   7 *Writing recursive functions on version 1 style lists*
   8
   9 Recall that version 1 style lists are constructed like this:
  10
  11 <pre>
  12 let true = \x y. x in
  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
  18 let fst = true in
  19 let snd = false 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
  26
  27 length mylist
  28 </pre>
  29
  30 Then `length mylist` evaluates to 3.
  31
  32 What does `head (tail (tail mylist))` evaluate to?