; Sieve of Eratosthenes via cons-list filter.
; Produces all primes < 100. Exercises list traversal across tiers.

(define (range a b)
  (if (>= a b) (quote ())
      (cons a (range (+ a 1) b))))

(define (filter pred xs)
  (cond ((null? xs) (quote ()))
        ((pred (car xs)) (cons (car xs) (filter pred (cdr xs))))
        (else (filter pred (cdr xs)))))

(define (sieve xs)
  (if (null? xs) (quote ())
      (let ((p (car xs)))
        (cons p
              (sieve
                (filter (lambda (x) (not (= (modulo x p) 0)))
                        (cdr xs)))))))

(define (print-list xs)
  (cond ((null? xs) (newline))
        (else
          (display (car xs))
          (display " ")
          (print-list (cdr xs)))))

(display "primes < 100: ")
(print-list (sieve (range 2 100)))
(print "done")
