| I was first introduced to Lisp in the form of Scheme, with the textbook The Structure and Interpretation of Computer Programs, by Abelson and Sussman. The full text is online: http://mitpress.mit.edu/sicp/ There's a lot of good stuff in there, but I wish to highlight the 'accumulate function, or at least my version of it. Here it is: (define (accumulate combiner term xs init next done);Scheme
(define (slave xs total)
(if (done xs)
total
(slave (next xs) (combiner (term xs) total))))
(slave xs init))
(def accumulate (combiner term xs init next done);Arc
((afn (xs total)
(if (done xs)
total
(self (next xs) (combiner (term xs) total))))
xs init))
I find 'accumulate very useful for writing functions that, well, accumulate. First, it frequently makes the definition shorter and nicer, and second, it is itself written tail-recursively, so it's easy to write efficient things with it. I'm going to demonstrate by rewriting several of the functions from arc.arc with 'accumulate. (def rev (xs)
(accumulate cons car xs nil cdr no))
(def map1 (f xs)
(rev (accumulate cons f:car xs nil cdr no)))
(def tuples (n xs);I put n first
(rev (accumulate cons [firstn n _] xs nil [nthcdr n _] no)))
(def pos (test seq (o start 0))
(let f (testify test)
(if (alist seq)
(accumulate + [idfn 1] (nthcdr start seq) start cdr f:car)
(recstring [if (f (seq _)) _] seq start))))
(def sum (f xs)
(accumulate + f:car xs 0 cdr no))
(def range (start end)
(rev (accumulate cons idfn start nil inc [> _ end])))
And now here are some other things I like to do with 'accumulate. (def sigma (f a b);I actually call this 'sum, but Arc uses that name
(accumulate + f a 0 inc [> _ b]))
(def product (f a b)
(accumulate * f a 1 inc [> _ b]))
(def factorial (n)
(product idfn 1 n))
(def genlist (f a b (o d 1));aka mapa-b
(rev (accumulate cons f a nil [+ _ d] [> _ b])))
(def range (a b (o d 1));someone's 'range that counts by d
(genlist idfn a b d))
(def definite-integral (f a b (o dx (/ (- b a) 100.0)))
(* dx (accumulate + f a 0 [+ _ dx] [>= _ b])))
(def num->digs (n (o base 10));(num->digs 4 2) --> (1 0 0)
(accumulate cons [mod _ base] n nil [trunc (/ _ base)] [is _ 0]))
(def digs->num (digs (o base 10))
(accumulate (fn (d n) (+ d (* n base))) car digs 0 cdr no))
Enjoy. |
