prime-sequence.scm - find primes as a infinite sequence with lazy evaluation in Scheme R5RS

prime-sequence.scm

;; prime-sequence.scm - find primes as a infinite sequence with lazy evaluation in Scheme R5RS
;; license: public domain

(define call/cc call-with-current-continuation)

;; filter of a list of which items satisfy func(item) == #t.
;; eg. (filter (lambda (x) (> x 7)) '(2 10 3 7 16 8))
;; -> (10 16 8)
(define (filter func list)
  (filter-iter func list '())
)

(define (filter-iter func list res)
  (cond
    ((eq? list '())
     res)
    ((func (car list))
     (filter-iter func (cdr list) (append res `(,(car list)))))
    (else (filter-iter func (cdr list) res)))
)

; infinite prime sequence
(define prime-seq
  (cons 2 (delay (prime-eval '(2)))))

(define (prime-eval list)
  (let*
    ((n (+ 1 (car (reverse list))))
     (test-list (filter (lambda (x)(<= x (sqrt n))) list)))
    
     (let iter ((n n) (test-list test-list))
        (let ((is_prime
               (call/cc (lambda (cc)
                          (for-each
                           (lambda (x) (if (= (modulo n x) 0) (cc #f)))
                           test-list)))))
        (if (eq? is_prime #f)
         (iter (+ n 1) (filter (lambda (x)(<= x (sqrt (+ n 1)))) list))
         (cons n (delay (prime-eval (append list `(,n))))))
          )))
)

;; get the ith (i started from 0) item of prime-seq.
;; eg. (prime-ref 20) -> 73
(define (prime-ref n)
  (prime-ref-iter n prime-seq))

(define (prime-ref-iter i prime-seq)
  (if (= i 0)
     (car prime-seq)
     (prime-ref-iter (- i 1) (force (cdr prime-seq)))
))


;; get the 0th-item to n-th item of prime-seq as a list.
;; eg: (prime-head 10)
;; -> (2 3 5 7 11 13 17 19 23 29 31)
(define (prime-head n)
  (prime-head-iter n prime-seq '()))

(define (prime-head-iter i prime-seq prev-res)
  (let ((res (append prev-res `(,(car prime-seq)))))
  (if (= i 0) 
     res
     (prime-head-iter (- i 1) (force (cdr prime-seq)) res))))

;; print the first 100+1 primes.
(for-each
 (lambda (x) (display x)(newline))
 (prime-head 100))