+ ; now you can search for primes, do encryption :-)
+ 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 = \f. Y (\map lst. isempty lst empty (make_list (f (head lst)) (map (tail lst)))) in
+ let filter = \f. Y (\filter lst. isempty lst empty (f (head lst) (make_list (head lst)) I (filter (tail lst)))) 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) err 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
+
+
+ ;; left-fold lists
+ let make_list = \h t f z. t f (f h z) in
+ let head = \lst. lst (\h sofar. (K (sofar (K h))) ) (\k. k err) I in
+ let tail = \lst. (\shift. lst shift (\a b. a tail_empty) I I)
+ (\h p. p (\j a b. b empty) (\t a b. b (\f z. f h (t f z))) ) in
+
+
+ ;; version 5 (CPS right-fold) lists
+ ; [] is \f z c a. c z
+ ; [1] is \f z c a. f 1 z c a
+ ; [1;2] is \f z c a. f 2 z (\z. f 1 z c a) a
+ ; [1;2;3] is \f z c a. f 3 z (\z. f 2 z (\z. f 1 z c a) a) a
+ let empty = \f2 z continue_handler abort_handler. continue_handler z in
+ let isempty = \lst larger_computation. lst
+ ; here's our f2
+ (\hd sofar continue_handler abort_handler. abort_handler false)
+ ; here's our z
+ true
+ ; here's the continue_handler for the leftmost application of f2
+ larger_computation
+ ; here's the abort_handler
+ larger_computation in
+ let make_list = \h t. \f2 z continue_handler abort_handler.
+ t f2 z (\sofar. f2 h sofar continue_handler abort_handler) abort_handler in
+ let head = \lst larger_computation. lst
+ ; here's our f2
+ (\hd sofar continue_handler abort_handler. continue_handler hd)
+ ; here's our z
+ err
+ ; here are our continue_handler and abort_handler
+ larger_computation unused in
+ let tail_empty = empty in
+ let tail = \lst larger_computation. lst
+ ; here's our f2
+ (\h sofar continue_handler abort_handler. continue_handler (sofar (\t y. make_pair (make_list h t) t)))
+ ; here's our z
+ (make_pair empty tail_empty)
+ ; here are our continue_handler and abort_handler
+ (\sofar. sofar (\x y. larger_computation y)) unused in
+
+ ;; CPS left-fold lists
+ ; [] is \f z c a. c z
+ ; [1] is \f z c a. f 1 z (\z. c z) a
+ ; [1;2] is \f z c a. f 1 z (\z. f 2 z (\z. c z) a) a
+ ; [1;2;3] is \f z c a. f 1 z (\z. f 2 z (\z. f 3 z (\z. c z) a) a) a
+ let make_right_list = make_list in
+ let make_list = \h t. \f2 z continue_handler abort_handler.
+ f2 h z (\z. t f2 z continue_handler abort_handler) abort_handler in
+ let head = \lst larger_computation. lst
+ ; here's our f2
+ (\hd sofar continue_handler abort_handler. abort_handler hd)
+ ; here's our z
+ err
+ ; here are our continue_handler and abort_handler
+ larger_computation larger_computation in
+ let tail = \lst larger_computation. lst
+ ; here's our f2
+ (\h sofar continue_handler abort_handler. continue_handler (sofar (\j a b. b empty) (\t a b. b (make_right_list h t)) ) )
+ ; here's our z
+ (\a b. a tail_empty)
+ ; here are our continue_handler and abort_handler
+ (\sofar. sofar larger_computation larger_computation) unused in
+