How to make a lazy list in an impatient language?

Question

I wanted to make a lazy list on the Scheme. This is what I still have.

;; Constructor for Pairs (define (cons-stream ab) (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 internal expression (lazy-list (+ from 1)), as a result of which the procedure goes into infinite recursion.

Is there a way to get con-stream to accept this internal expression without any evaluation?

Answer 1

The solution is to use a macro. I am not an expert on schemas (especially not on macros), but perhaps this snippet can serve as an 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" 

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. Take a look at define-syntax .

Answer 2

If you do not want to follow the macro route, you can always simply abandon cons-stream and rewrite lazy-list as follows:

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

This is perhaps the simplest, most pragmatic solution, but it is only useful for creating lazy lists of increasing numbers. You can generalize this by passing a function that will generate sequential list items 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 very well:

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

But there is an error in the code:

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

This error occurs because calling cdr-stream calls generator again. We can solve this by caching the return value of 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

The tape list in the diagram is known as a stream. Here's a standard introduction.

Answer 4

You really have to look at the SRFI-41

In particular, lazy threads created by recursive functions will greatly pollute memory in an impatient language, unless you avoid it. To do this, you need to make recursive functions lazy, not impatient. This means that your implementation of laziness should be SRFI-45 , which exports delay, strength and laziness. Functions that create threads recursively should wrap their bodies lazy.