Here are a bunch of pre-tested operations for the untyped lambda calculus. In some cases multiple versions are offered.
+Some of these are drawn from:
+
+* [[!wikipedia Lambda calculus]]
+* [[!wikipedia Church encoding]]
+* Oleg's [Basic Lambda Calculus Terms](http://okmij.org/ftp/Computation/lambda-calc.html#basic)
+
+and all sorts of other places. Others of them are our own handiwork.
+
+
+**Spoilers!** Below you'll find implementations of map and filter for v3 lists, and several implementations of leq for Church numerals. Those were all requested in Assignment 2; so if you haven't done that yet, you should try to figure them out on your own. (You can find implementations of these all over the internet, if you look for them, so these are no great secret. In fact, we'll be delighted if you're interested enough in the problem to try to think through alternative implementations.)
+
+
; booleans
let true = \y n. y in ; aka K
let false = \y n. n in ; aka K I
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 list2 to list1 with: list1 make_list list2
- let reverse = \lst. lst (\h sofar. sofar make_list (singleton h)) empty 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
let length = Y (\self lst. isempty lst 0 (succ (self (tail lst)))) in
+ true
+
+<!--
+
; numhelper 0 f z ~~> z
; when n > 0: numhelper n f z ~~> f (pred n)
; compare Bunder/Urbanek pred
fact Theta 3 ; returns 6
-
+-->
<!--
; my original efficient comparisons
negate_int = \int. sign_case int (church_to_negint (abs int)) zero (church_to_int (abs int))
- for more, see http://okmij.org/ftp/Computation/lambda-arithm-neg.scm
+ for more, see http://okmij.org/ftp/Computation/lambda-calc.html#neg
+
-->