1 Here are a bunch of pre-tested operations for the untyped lambda calculus. In some cases multiple versions are offered.
4 let true = \y n. y in ; aka K
5 let false = \y n. n in ; aka K I
6 let and = \p q. p q false in ; or
7 let and = \p q. p q p in ; aka S C I
8 let or = \p q. p true q in ; or
9 let or = \p q. p p q in ; aka M
10 let not = \p. p false true in ; or
11 let not = \p y n. p n y in ; aka C
12 let xor = \p q. p (not q) q in
13 let iff = \p q. not (xor p q) in ; or
14 let iff = \p q. p q (not q) in
17 let make_pair = \x y f. f x y in
18 let get_1st = \x y. x in ; aka true
19 let get_2nd = \x y. y in ; aka false
22 let make_triple = \x y z f. f x y z in
25 ; Church numerals: basic operations
27 let zero = \s z. z in ; aka false
28 let one = \s z. s z in ; aka I
29 let succ = \n s z. s (n s z) in
30 ; for any Church numeral n > zero : n (K y) z ~~> y
31 let iszero = \n. n (\x. false) true in
36 let empty = \f z. z in
37 let make_list = \h t f z. f h (t f z) in
38 let isempty = \lst. lst (\h sofar. false) true in
39 let head = \lst. lst (\h sofar. h) junk in
40 let tail = \lst. (\shift lst. lst shift (make_pair empty junk) get_2nd)
42 (\h p. p (\t y. make_pair (make_list h t) t)) in
43 let length = \lst. lst (\h sofar. succ sofar) 0 in
44 let map = \f lst. lst (\h sofar. make_list (f h) sofar) empty in
45 let filter = \f lst. lst (\h sofar. f h (make_list h sofar) sofar) empty in ; or
46 let filter = \f lst. lst (\h. f h (make_list h) I) empty in
48 ; append list2 to list1 with: list1 make_list list2
49 let singleton = \x f z. f x z in
50 let reverse = \lst. lst (\h sofar. sofar make_list (singleton h)) empty in
51 let zip = \left right. left (\h sofar. sofar (\x y. isempty y
53 (make_pair (make_list (\u v. head y (u v) h) x) (tail y))
55 (make_pair empty (map right (\h u v. u v h)))
58 let all = \f lst. lst (\h sofar. and sofar (f h)) true in
59 let any = \f lst. lst (\h sofar. or sofar (f h)) false in
64 let empty = make_pair true junk in
65 let make_list = \h t. make_pair false (make_pair h t) in
66 let isempty = \lst. lst get_1st in
67 let head = \lst. isempty lst err (lst get_2nd get_1st) in
68 let tail_empty = empty in
69 let tail = \lst. isempty lst tail_empty (lst get_2nd get_2nd) in
72 ; more math with Church numerals
74 let add = \m n. m succ n in ; or
75 let add = \m n s z. m s (n s z) in
76 let mul = \m n. m (\z. add n z) zero in ; or
77 let mul = \m n s. m (n s) in
78 let pow = \b exp. exp (mul b) one in ; or
80 ; b (b succ) ; adds b b times, ie adds b^2
81 ; b (b (b succ)) ; adds b^2 b times, ie adds b^3
82 ; exp b succ ; adds b^exp
83 let pow = \b exp s z. exp b s z in
86 ; three strategies for predecessor
87 let pred_zero = zero in
88 let pred = (\shift n. n shift (make_pair zero pred_zero) get_2nd)
90 (\p. p (\x y. make_pair (succ x) x)) in ; or
91 ; from Oleg; observe that for any Church numeral n: n I ~~> I
92 let pred = \n. iszero n zero
94 (n (\x. x I ; when x is the base term, this will be K zero
95 ; when x is a Church numeral, it will be I
100 ; from Bunder/Urbanek
101 let pred = \n s z. n (\u v. v (u s)) (K z) I in ; or
104 ; inefficient but simple comparisons
105 let leq = \m n. iszero (n pred m) in
106 let lt = \m n. not (leq n m) in
107 let eq = \m n. and (leq m n) (leq n m) in ; or
110 ; more efficient comparisons, Oleg's gt provided some simplifications
111 let leq = (\base build consume. \m n. n consume (m build base) get_1st)
113 (make_pair true junk)
115 (\p. make_pair false p)
117 (\p. p get_1st p (p get_2nd)) in
118 let lt = \m n. not (leq n m) in
119 let eq = (\base build consume. \m n. n consume (m build base) get_1st)
120 ; 2nd element of a pair will now be of the form (K sthg) or I
121 ; we supply the pair being consumed itself as an argument
122 ; getting back either sthg or the pair we just consumed
124 (make_pair true (K (make_pair false I)))
126 (\p. make_pair false (K p))
131 ; -n is a fixedpoint of \x. add (add n x) x
132 ; but unfortunately Y that_function doesn't normalize
134 let sub = \m n. n pred m in ; or
135 ; how many times we can succ n until m <= result
136 let sub = \m n. (\base build. m build base (\cur fin sofar. sofar))
138 (make_triple n false zero)
140 (\t. t (\cur fin sofar. or fin (leq m cur)
141 (make_triple cur true sofar) ; enough
142 (make_triple (succ cur) false (succ sofar)) ; continue
145 let sub = (\base build consume. \m n. n consume (m build base) get_1st)
147 (make_pair zero I) ; see second defn of eq for explanation of 2nd element
149 (\p. p (\x y. make_pair (succ x) (K p)))
154 let min = \m n. sub m (sub m n) in
155 let max = \m n. add n (sub m n) in
158 ; (m/n) is a fixedpoint of \x. add (sub (mul n x) m) x
159 ; but unfortunately Y that_function doesn't normalize
161 ; how many times we can sub n from m while n <= result
162 let div = \m n. (\base build. m build base (\cur go sofar. sofar))
164 (make_triple m true zero)
166 (\t. t (\cur go sofar. and go (leq n cur)
167 (make_triple (sub cur n) true (succ sofar)) ; continue
168 (make_triple cur false sofar) ; enough
170 ; what's left after sub n from m while n <= result
171 let mod = \m n. (\base build. m build base (\cur go. cur))
175 (\p. p (\cur go. and go (leq n cur)
176 (make_pair (sub cur n) true) ; continue
177 (make_pair cur false) ; enough
181 let divmod = (\base build mtail. \m n.
182 (\dhead. m (mtail dhead) (\sel. dhead (sel 0 0)))
183 (n build base (\x y z. z junk))
184 (\t u x y z. make_pair t u) )
186 (make_triple succ (K 0) I) ; see second defn of eq for explanation of 3rd element
188 (\t. make_triple I succ (K t))
190 (\dhead d. d (\dz mz df mf drest sel. drest dhead (sel (df dz) (mf mz))))
192 let div = \n d. divmod n d get_1st in
193 let mod = \n d. divmod n d get_2nd in
196 ; sqrt n is a fixedpoint of \x. div (div (add n (mul x x)) 2) x
197 ; but unfortunately Y that_function doesn't normalize
200 ; (log base b of m) is a fixedpoint of \x. add (sub (pow b x) m) x
201 ; but unfortunately Y that_function doesn't normalize
203 ; how many times we can mul b by b while result <= m
204 let log = \m b. (\base build. m build base (\cur go sofar. sofar))
206 (make_triple b true 0)
208 (\t. t (\cur go sofar. and go (leq cur m)
209 (make_triple (mul cur b) true (succ sofar)) ; continue
210 (make_triple cur false sofar) ; enough
214 ; Rosenbloom's fixed point combinator
215 let Y = \f. (\h. f (h h)) (\h. f (h h)) in
216 ; Turing's fixed point combinator
217 let Theta = (\u f. f (u u f)) (\u f. f (u u f)) in
220 ; length for version 1 lists
221 let length = Y (\self lst. isempty lst 0 (succ (self (tail lst)))) in
224 ; numhelper 0 f z ~~> z
225 ; when n > 0: numhelper n f z ~~> f (pred n)
226 ; compare Bunder/Urbanek pred
227 let numhelper = \n. n (\u v. v (u succ)) (K 0) (\p f z. f p) in
229 ; accepts fixed point combinator as a parameter, so you can use different ones
230 let fact = \y. y (\self n. numhelper n (\p. mul n (self p)) 1) in
234 fact Theta 3 ; returns 6
238 ; my original efficient comparisons
239 let leq = (\base build consume. \m n. n consume (m build base) get_1st (\x. false) true)
241 (make_pair zero I) ; supplying this pair as an arg to its 2nd term returns the pair
243 (\p. p (\x y. make_pair (succ x) (K p))) ; supplying the made pair as an arg to its 2nd term returns p (the previous pair)
246 let lt = \m n. not (leq n m) in
247 let eq = (\base build consume. \m n. n consume (m build base) true (\x. false) true)
249 (make_pair zero (K (make_pair one I)))
251 (\p. p (\x y. make_pair (succ x) (K p)))
253 (\p. p get_2nd p) in ; or
261 show Oleg's definition of integers:
262 church_to_int = \n sign. n
263 church_to_negint = \n sign s z. sign (n s z)
268 sign_case = \int ifpos ifzero ifneg. int (K ifneg) (K ifpos) ifzero
270 negate_int = \int. sign_case int (church_to_negint (abs int)) zero (church_to_int (abs int))
272 for more, see http://okmij.org/ftp/Computation/lambda-arithm-neg.scm