tweak arithmetic

Signed-off-by: Jim Pryor <profjim@jimpryor.net>

diff --git a/arithmetic.mdwn b/arithmetic.mdwn
index 62e72bf..fafecaf 100644 (file)
--- a/arithmetic.mdwn
+++ b/arithmetic.mdwn
@@ -46,8 +46,13 @@ Here are a bunch of pre-tested operations for the untyped lambda calculus. In so
        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
        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
        ; 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