Wie mache ich eine faule Liste in einer eifrigen Sprache?

Question

Ich wollte eine faule Liste in Scheme machen. Das habe ich bisher.

;; 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)) 

Das Problem mit der Lazy-Liste ist, dass die innere Scheme Ausdruck (lazy-Liste (+ 1)) zunächst bewirkt das Verfahren in eine unendliche Rekursion gehen auswertet.

Gibt es eine Möglichkeit, dass der Contractre diesen inneren Ausdruck ohne Bewertung nimmt?

Answer 1

Die Lösung besteht darin, ein Makro zu verwenden. Ich bin kein Schema Experten (vor allem nicht auf Makros), aber vielleicht kann dieser Schnipsel als Inspiration dienen:

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

Es verwendet wird, wie folgt:

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

Vielleicht wollen Sie so etwas wie

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

Aber ich bin mir nicht sicher. Schauen Sie sich define-syntax an.

Answer 2

Eine faule Liste in Scheme ist bekannt als Stream. Here's the standard introduction.

Answer 3

Wenn Sie das Makro Route nicht gehen wollen, können Sie immer verlassen nur cons-stream und schreiben lazy-list wie folgt:

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

Dies ist wahrscheinlich die einfachste und pragmatische Lösung, aber es ist nur gut um faule Listen von steigenden Zahlen zu machen. Man könnte dies verallgemeinern, indem man in einer Funktion übergeben, die aufeinanderfolgende Elemente der Liste generieren, wenn sie aufgerufen:

(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)))) 

Das funktioniert ziemlich gut:

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

Aber es gibt einen Fehler im Code:

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

Dieser Fehler tritt auf, weil der Aufruf an cdr-stream wieder generator aufruft. Wir können dieses Problem lösen, indem Caching der Rückgabewert des 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)))) 

Jetzt funktioniert es, wie es sollte:

> (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 4

Sie wirklich bei SRFI-41

Insbesondere aussehen sollte, faul Ströme erstellt durch rekursive Funktionen wird Speicher in einer eifrigen Sprache, schlecht auslaufen, es sei denn Sie vermeiden es ausdrücklich. Um dies zu tun, müssen Sie rekursive Funktionen auch faul, nicht eifrig machen. Das bedeutet, dass Ihre Faulheitsimplementierung SRFI-45 sein muss, die Verzögerung, Kraft, und faul exportiert. Funktionen, die rekursiv Streams erstellen, müssen ihre Körper in faule umbrechen.