X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=lambda_library.mdwn;h=0c00c4508e5f7d62c4b79086aec13cfc30769229;hp=5623b9fa219b4cf9ef0fca41b8fe098768b803df;hb=9e49e4a8db892623d6f3dd202aad27a8547ad826;hpb=4cea4f69242f3a229292186c8fa652942f31f8b8 diff --git a/lambda_library.mdwn b/lambda_library.mdwn index 5623b9fa..0c00c450 100644 --- a/lambda_library.mdwn +++ b/lambda_library.mdwn @@ -63,8 +63,12 @@ and all sorts of other places. Others of them are our own handiwork. ; 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)) + ; 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 + ; most elegant + ; revappend [a;b;c] [x;y] ~~> [c;b;a;x;y] + let revappend = \lst. lst (\hd sofar. \lst. sofar (make_list hd lst)) I in + let rev = \lst. revappend lst empty 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 @@ -236,6 +240,12 @@ and all sorts of other places. Others of them are our own handiwork. let Theta = (\u f. f (u u f)) (\u f. f (u u f)) in + ; now you can search for primes, do encryption :-) + let gcd = Y (\gcd m n. iszero n m (gcd n (mod m n))) in ; or + let gcd = \m n. iszero m n (Y (\gcd m n. iszero n m (lt n m (gcd (sub m n) n) (gcd m (sub n m)))) m n) in + let lcm = \m n. or (iszero m) (iszero n) 0 (mul (div m (gcd m n)) n) in + + ; length for version 1 lists let length = Y (\self lst. isempty lst 0 (succ (self (tail lst)))) in @@ -314,10 +324,14 @@ let list_equal = ; (might_for_all_i_know_still_be_equal?, tail_of_reversed_right) ; when left is empty, the lists are equal if right is empty (make_pair - (not (isempty right)) + true ; for all we know so far, they might still be equal (reverse right) ) ; when fold is finished, check sofar-pair (\might_be_equal right_tail. and might_be_equal (isempty right_tail)) + +; most elegant +let list_equal = \lst. lst (\hd sofar. \lst. and (and (not (isempty lst)) (eq hd (head lst))) (sofar (tail lst))) isempty + -->