The idea of adding lazy lists to Lisp dates back to TR44:

CONS should not Evaluate its Arguments (Daniel P. Friedman, 1976). Guy Steele discusses TR44 and other cool ideas in this talk.

In order to delay evaluation, the lazy cons will suspend its arguments in closures. These closures will be executed on first access, and the results stored.

(mac wrap (a) `(fn () ,a))Presto, we're done! Those are all the primitive we need. Now we'll just define some typical list utilities to using our new car_, cdr_, and cons_.

(def force (f) (wrap (f)))

(mac cons_ (a b) `(cons (wrap ,a) (wrap ,b)))

(def car_ (li) ((zap force (car li))))

(def cdr_ (li) ((zap force (cdr li))))

(def filter (p li)With those, we can start playing with infinite lists. For starters, the natural numbers.

(if (no li) li

(p (car_ li)) (cons_ (car_ li) (filter p (cdr_ li)))

(filter p (cdr_ li))))

(def map_ (f li)

(if (no li) li

(cons_ (f (car_ li)) (map_ f (cdr_ li)))))

(def take (n li)

(if (<= n 0) nil

(cons (car_ li) (take (- n 1) (cdr_ li)))))

(def count-from (n) (cons_ n (count-from (+ n 1))))Now, the primes:

(= naturals (count-from 1))

(take 5 (filter odd naturals)) ; => (1 3 5 7 9)

(take 5 (map_ [* _ 3] naturals)) ; => (3 6 9 12 15)

(def sieve (li)Holy 4-line prime number sieve, Batman!

(let p (car_ li)

(cons_ p (sieve (filter [> (mod _ p) 0] (cdr_ li))))))

(= primes (sieve (count-from 2)))

(take 10 primes) ; => (2 3 5 7 11 13 17 19 23 29)Here is the equivalent in Haskell (see also HaskellWiki.)

primes = sieve [2..] where

sieve (p:xs) = p : sieve (filter (\x -> x `mod` p > 0) xs)

P.S. A multi-arg version of map_. I did the single argument version above because it is easier to follow.

(def map_ (f . lists)P.P.S. Bonus: Fibonacci sequence.

(if (some no lists) nil

(cons_ (apply f (map car_ lists))

(apply map_ f (map cdr_ lists)))))

(= fibs (cons_ 1 (cons_ 1 (map_ + fibs (cdr_ fibs)))))

## 2 comments:

> Holy 4-line prime number sieve,

> Batman!

Except that it is not a sieve. Isn't Eratosthenes's sieve, at least : the real Eratosthenes sieve complexity is around O(n log n), while your code use O(n^2).

It's

aprime number sieve. I didn't mean to imply it was the sieve of Eratosthenes.I went ahead and coded up the real one though, see today's post.

Post a Comment