How do I make a Lazy List in an Eager Language?

Question

I wanted to make a lazy list in Scheme. This is what I have so far.

;; Constructor for Pairs
(define (cons-stream a b)
  (cons a (λ() b)))

;; Selectors
(define (car-stream a-stream)
  (car a-stream))

(define (cdr-stream a-stream)
  ((cdr a-stream)))

;; Lazy List using the pairs
(define (lazy-list from)
  (cons-stream from (lazy-list (+ from 1))))

;; Take function
(define (take a-lazy-list number)
  (define (take-helper i )
    (if(= i number)
       empty
       (cons (car a-lazy-list) (take-helper (+ i 1)))))
  (take-helper 0))

The problem with the lazy-list is that Scheme evaluates the inner expression (lazy-list (+ from 1)) first causing the procedure to go into an infinite recursion.

Is there a way to make the con-stream take this inner expression without any evaluation?

Answer 1

The solution is to use a macro. I'm no scheme expert (especially not on macros), but maybe this snippet can serve as inspiration:

(define-syntax pointer-to
   (syntax-rules ()
    ((pointer-to var)
     (make-pointer
      (lambda () var) ; the "pointer dereference" operation
      (lambda (value) (set! var value)))))) ; "pointer write"

It's used as follows:

(define x 1)
(define px (pointer-to x))
(pointer-set! px 2) ; this (in some sense) becomes `(set! x 2)'

So maybe you want something like

(define-syntax lazy-cons
 (syntax-rules ()
  ((lazy-cons head lazytail)
   (cons head (lambda () lazytail)))))

But I'm not sure. Have a look at define-syntax.

Answer 2

A lazy list in Scheme is known as a stream. Here's the standard introduction.

Answer 3

If you don't want to go the macro route, you could always just abandon cons-stream and rewrite lazy-list as follows:

(define (lazy-list from)
  (cons from (λ() (lazy-list (+ from 1)))))

This is probably the easiest, most pragmatic solution, but it's only good for making lazy lists of incrementing numbers. You could generalize this by passing in a function that will generate successive elements of the list when called:

(define (lazy-list-gen generator)
  (cons (generator)
        (λ() (lazy-list-gen generator))))

(define (lazy-list from)
  (lazy-list-gen
   (λ()
     (let ((ret from))
       (set! from (+ from 1))
       ret))))

This works pretty well:

> (define x (lazy-list 1))
> (car-stream x)
1
> (car-stream (cdr-stream x))
2

But there's a bug in the code:

... continuing from above ...
> (car-stream (cdr-stream x))
3

This error happens because the call to cdr-stream calls generator again. We can solve this by caching the return value of the lambda:

(define (lazy-list-gen generator)
  (cons (generator)
        (let ((gen-cache #f))
          (λ()
            (cond ((not gen-cache)
                   (set! gen-cache (lazy-list-gen generator))))
            gen-cache))))

Now it works as it should:

> (define x (lazy-list 1))
> (car-stream x)
1
> (car-stream (cdr-stream x))
2
> (car-stream (cdr-stream x))
2
> (car-stream (cdr-stream (cdr-stream x)))
3
> (car-stream (cdr-stream x))
2