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

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

Answer 3

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

Answer 4

You should really look at SRFI-41

In particular, lazy streams created by recursive functions will leak memory badly in an eager language, unless you specifically avoid it. To do so, you need to make recursive functions lazy also, not eager. This means that your laziness implementation needs to be SRFI-45, which exports delay, force, and lazy. Functions that build streams recursively must wrap their bodies in lazy.