X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=arithmetic.mdwn;h=fafecafdba3036c095fe1e50d26e5bf1da6395d9;hp=e948f0b48123694b7b1c1f328ff91520a374f4bd;hb=6dffa91feff41dc4736d907bf59c3a76a3c8d50f;hpb=bbc4b46b396a1a5e8db1f0ca97eda1bf806ef59d diff --git a/arithmetic.mdwn b/arithmetic.mdwn index e948f0b4..fafecafd 100644 --- a/arithmetic.mdwn +++ b/arithmetic.mdwn @@ -22,39 +22,62 @@ Here are a bunch of pre-tested operations for the untyped lambda calculus. In so let make_triple = \x y z f. f x y z in + ; Church numerals: basic operations + + let zero = \s z. z in ; aka false + let one = \s z. s z in ; aka I + let succ = \n s z. s (n s z) in + ; for any Church numeral n > zero : n (K y) z ~~> y + let iszero = \n. n (\x. false) true in + + ; version 3 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 = \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) zero in + (\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 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 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_1st in - let head = \lst. isempty lst error (lst get_2nd get_1st) in + let head = \lst. isempty lst err (lst get_2nd get_1st) in let tail_empty = empty in let tail = \lst. isempty lst tail_empty (lst get_2nd get_2nd) in + ; more math with Church numerals - ; Church numerals: easy operations - - let zero = \s z. z in ; aka false - let one = \s z. s z in ; aka I - let succ = \n s z. s (n s z) in - ; for any Church numeral n > zero : n (K y) z ~~> y - let iszero = \n. n (\x. false) true in let add = \m n. m succ n in ; or let add = \m n s z. m s (n s z) in let mul = \m n. m (\z. add n z) zero in ; or @@ -195,10 +218,10 @@ Here are a bunch of pre-tested operations for the untyped lambda calculus. In so )) in - ; Curry's fixed point combinator + ; Rosenbloom's fixed point combinator let Y = \f. (\h. f (h h)) (\h. f (h h)) in ; Turing's fixed point combinator - let Z = (\u f. f (u u f)) (\u f. f (u u f)) in + let Theta = (\u f. f (u u f)) (\u f. f (u u f)) in ; length for version 1 lists @@ -215,7 +238,7 @@ Here are a bunch of pre-tested operations for the untyped lambda calculus. In so - fact Z 3 ; returns 6 + fact Theta 3 ; returns 6 + +