Lazy Lists in Arc

No time for inflammatory ranting today. We're going to define lazy lists in Arc. (See also CL version.)

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))
(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))))

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 filter (p li)
  (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)))))

With those, we can start playing with infinite lists. For starters, the natural numbers.

(def count-from (n) (cons_ n (count-from (+ n 1))))

(= naturals (count-from 1))

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

Now, the primes:

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

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

Holy 4-line prime number sieve, Batman!

(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)
  (if (some no lists) nil
      (cons_ (apply f (map car_ lists))
             (apply map_ f (map cdr_ lists)))))

P.P.S. Bonus: Fibonacci sequence.

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