Your interleave
does not produce a lazy list; it produces an ordinary list: it uses cons
with two arguments, with the second argument not wrapped in a lambda
. So the cons
forces the 2nd argument through, causing the run-away evaluation:
(define interleave
(lambda (lz1 dlz2) ; "delayed" lz2
(if (empty? lz1)
(dlz2)
(cons (head lz1)
; here:
(interleave (dlz2) (lambda () (tail lz1)))))))
(define lz-lst-accumulate
(lambda (op initial lz)
(if (empty? lz)
initial
(op (head lz)
(lambda () (lz-lst-accumulate op initial (tail lz)))))))
(all-div-from lower)
produces correct output, ( (lower . <proc1>) . <proc2> )
, but the call to (lz-lst-accumulate interleave '() (all-div-from lower))
reduces as
(interleave [lower . <proc1>]
(lambda () (lz-lst-accumulate interleave '() (<proc2>))))
and that reduces as
(cons lower
(interleave (lz-lst-accumulate interleave '() (<proc2>))
(lambda () (<proc1>))))
while it has to reduce as
(cons lower
(lambda () (interleave ....)))
to produce a lazy list.
The obvious (now) solution is to add that missing lambda
:
(define interleave
(lambda (lz1 lz2)
(if (empty? lz1)
(lz2)
(cons (head lz1)
(lambda () (interleave (lz2) (lambda() (tail lz1))))))))
Now it runs correctly:
(take (all-div-from-flattened 7) 10)
;Value 12: (7 8 14 9 21 16 28 10 35 24)
You could much simplify your code by introducing
(define integers-from-by
(lambda (n d) (cons n
(lambda () (integers-from (+ n d) d)))))
then,
;(define div-from
; (lambda (lower int)
; (lz-lst-filter (lambda(x) (> x (- lower 1)))
; (lz-lst-map (lambda(x) (* x int)) (integers-from 1)))))
(define mults-from-of ; n in [int, 2*int ..], n >= lower
(lambda (lower int)
(let ((x (* (quotient (+ lower (- int 1)) int) int)))
(integers-from-by x int))))
You could also have
(define mults-above-of ; n in [int, 2*int ..], n > lower
(lambda (lower int)
(let ((x (* (+ (quotient lower int) 1) int)))
(integers-from-by x int))))
Next,
; (define all-div-from
; (lambda(lower)
; (cons (lz-lst-map (lambda(x) (* x lower)) (div-from 1 1))
; (lambda() (all-div-from (add1 lower))))))
(define all-mults-from
(lambda (lower)
(lz-lst-map (lambda (n) (mults-from-of n n))
; or just (integers-from-by n n)
(integers-from-by lower 1))))
If you change your interleave
to combine the streams in order, and switch to mults-above-of
in the all-mults-from
definition, then (lz-lst-accumulate interleave-ordered '() (all-mults-from-above 2))
will define the lazy list of all composite numbers, in order, by means of counting up as in the sieve of Eratosthenes.
From this, it's just one more step to getting yourself your own lazy unbounded incremental sieve of Eratosthenes (search for "SiCp" on that page).
Another remark: take
should be tweaked to not force an extra element of a stream. More here.