haskeem-0.6.10: hamming.scm

; -- Efficiently compute Hamming numbers

; This version of stream-merge keeps only one copy of duplicate
; values. For Hamming numbers, that's exactly what we want, but
; for more general stream merging, it might not be.

(define (stream-merge strm1 strm2 cmp)
  (let ((cval (cmp (car strm1) (car strm2))))
    (cond ((< cval 0) (cons (car strm1)
			    (delay (stream-merge (force (cdr strm1))
						 strm2 cmp))))
	  ((= cval 0) (cons (car strm1)
			    (delay (stream-merge (force (cdr strm1))
						 (force (cdr strm2)) cmp))))
	  ((> cval 0) (cons (car strm2)
			    (delay (stream-merge strm1
						 (force (cdr strm2)) cmp)))))))

(define hams
  (letrec ((next
	    (lambda (n)
	      (cons n (delay (stream-merge
			      (stream-map (lambda (n) (* 5 n)) hams)
			      (stream-merge
			       (stream-map (lambda (n) (* 2 n)) hams)
			       (stream-map (lambda (n) (* 3 n)) hams)
			       -)
			      -))))))
    (next 1)))

(display (stream-head hams 200))
(write-string #\linefeed)