+ let gcd = Y (\gcd m n. iszero n m (gcd n (mod m n))) in ; or
+ let gcd = \m n. iszero m n (Y (\gcd m n. iszero n m (lt n m (gcd (sub m n) n) (gcd m (sub n m)))) m n) in
+ let lcm = \m n. or (iszero m) (iszero n) 0 (mul (div m (gcd m n)) n) in
+
+
+ ;; version 1 lists
+ let empty = make_pair true junk in
+ let make_list = \h t. make_pair false (make_pair h t) in
+ let isempty = \lst. lst get_fst in
+ let head = \lst. isempty lst err (lst get_snd get_fst) in
+ let tail_empty = empty in
+ let tail = \lst. isempty lst tail_empty (lst get_snd get_snd) in
+
+ let length = Y (\length lst. isempty lst 0 (succ (length (tail lst)))) in
+ let fold = Y (\fold lst f z. isempty lst z (f (head lst) (fold (tail lst) f z))) in
+ let map = Y (\map lst f. isempty lst empty (make_list (f (head lst)) (map (tail lst) f))) in
+ let filter = Y (\filter lst f. isempty lst empty (f (head lst) (make_list (head lst)) I (filter (tail lst) f))) in
+
+
+ ;; version 3 (right-fold) lists
+ let empty = \f z. z in
+ let make_list = \h t f z. f h (t f z) in
+ let isempty = \lst. lst (\h sofar. false) true in
+ let head = \lst. lst (\h sofar. h) junk in
+ let tail_empty = empty in
+ let tail = \lst. (\shift. lst shift (make_pair empty tail_empty) get_snd)
+ ; where shift is
+ (\h p. p (\t y. make_pair (make_list h t) t)) in
+ let length = \lst. lst (\h sofar. succ sofar) 0 in
+ let map = \f lst. lst (\h sofar. make_list (f h) sofar) empty in
+ let filter = \f lst. lst (\h sofar. f h (make_list h sofar) sofar) empty in ; or
+ let filter = \f lst. lst (\h. f h (make_list h) I) empty in
+ let singleton = \x f z. f x z in
+ ; append [a;b;c] [x;y;z] ~~> [a;b;c;x;y;z]
+ let append = \left right. left make_list right in
+ ; very inefficient but correct reverse
+ let reverse = \lst. lst (\h sofar. append sofar (singleton h)) empty in ; or
+ ; more efficient revappend, reverse
+ ; revappend [a;b;c] [x;y] ~~> [c;b;a;x;y]
+ ; make_left_list a (make_left_list b (make_left_list c empty)) ~~> \f z. f c (f b (f a z))
+ let revappend = (\make_left_lst left right. left make_left_list right) (\h t f z. t f (f h z)) in
+ ; from Oleg, of course it's the most elegant
+ let revappend = \left. left (\hd sofar. \right. sofar (make_list hd right)) I in
+ let rev = \lst. revappend lst empty in
+ ; zip [a;b;c] [x;y;z] ~~> [(a,x);(b,y);(c,z)]
+ let zip = \left right. (\base build. reverse left build base (\x y. reverse x))
+ ; where base is
+ (make_pair empty (map (\h u. u h) right))
+ ; and build is
+ (\h sofar. sofar (\x y. isempty y
+ sofar
+ (make_pair (make_list (\u. head y (u h)) x) (tail y))
+ )) in
+ let all = \f lst. lst (\h sofar. and sofar (f h)) true in
+ let any = \f lst. lst (\h sofar. or sofar (f h)) false in
+