index bc15ae8..fafecaf 100644 (file)
@@ -37,15 +37,34 @@ Here are a bunch of pre-tested operations for the untyped lambda calculus. In so
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 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 = \lst. (\shift lst. lst shift (make_pair empty junk) get_2nd)
+       let tail_empty = empty  in
+       let tail = \lst. (\shift. lst shift (make_pair empty tail_empty) get_2nd)
; 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
; 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 reverse = \lst. lst (\h t. t make_list (\f n. f h n)) 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 reverse builds a left-fold instead
+       ; (make_left_list a (make_left_list b (make_left_list c empty)) ~~> \f z. f c (f b (f a z))
+       let reverse = (\make_left_list lst. lst make_left_list empty) (\h t f z. t f (f h z))  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
+

; version 1 lists

; version 1 lists