X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=arithmetic.mdwn;h=bc15ae8de777a3ad40fe126cbe7500f02edd4890;hp=e948f0b48123694b7b1c1f328ff91520a374f4bd;hb=cbb48495bd8cd6cdcbebd1bcd8c3051148c8b0a6;hpb=bbc4b46b396a1a5e8db1f0ca97eda1bf806ef59d

diff --git a/arithmetic.mdwn b/arithmetic.mdwn
index e948f0b4..bc15ae8d 100644
--- a/arithmetic.mdwn
+++ b/arithmetic.mdwn
@@ -22,6 +22,15 @@ 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
@@ -30,11 +39,12 @@ Here are a bunch of pre-tested operations for the untyped lambda calculus. In so
 	let head = \lst. lst (\h sofar. h) junk  in
 	let tail = \lst. (\shift lst. lst shift (make_pair empty junk) 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 reverse = \lst. lst (\h t. t make_list (\f n. f h n)) empty  in
 	
 
 	; version 1 lists
@@ -42,19 +52,13 @@ Here are a bunch of pre-tested operations for the untyped lambda calculus. In so
 	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 +199,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 +219,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
 
 
 <!--
@@ -236,3 +240,23 @@ Here are a bunch of pre-tested operations for the untyped lambda calculus. In so
 			; and consume is
 			(\p. p get_2nd p)  in ; or
 -->
+
+<!--
+	gcd
+	pow_mod
+
+
+	show Oleg's definition of integers:
+		church_to_int = \n sign. n
+		church_to_negint = \n sign s z. sign (n s z)
+
+		; int_to_church
+		abs = \int. int I
+
+		sign_case = \int ifpos ifzero ifneg. int (K ifneg) (K ifpos) ifzero
+
+		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
+
+-->