Eager言語でレイジーリストを作成するにはどうすればよいですか？

Question

私はSchemeで怠惰なリストを作りたかったのです。これは私がこれまで持っていたものです。

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

遅延リストに伴う問題は、スキーム最初無限再帰に入る手続きを引き起こす（1）からの遅延リスト（+）内の式を評価することです。

con-streamを評価なしでこの内部表現にする方法はありますか？

Answer 1

解決策は、マクロを使用することです。私は、（マクロでは特にありません）は、スキームの専門家だが、多分このスニペットは、インスピレーションとして機能することができます

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

次のようにそれを使用しています：

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

だから、多分あなたは

ような何かをしたいです

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

しかし、わかりません。 define-syntaxをご覧ください。

Answer 2

スキームの遅延リストはストリームとして知られています。 Here's the standard introduction.

Answer 3

マクロルートを移動したくない場合は、常にちょうどcons-streamを放棄でき、次のようにlazy-listを書き換え：

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

これはおそらく最も簡単な、最も実用的なソリューションですが、それだけで良いことです増分する数字の怠惰なリストを作るためのものです。

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

しかし、バグがコードにあります：

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

これはかなりうまく機能：

あなたは呼び出されたときに、リストの連続する要素を生成する関数に渡すことで、これを一般化することができ

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

cdr-streamへの呼び出しがgeneratorを再度呼び出すため、このエラーが発生します。私たちは、ラムダの戻り値をキャッシュすることにより、この問題を解決することができます：それが必要として

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

今では動作します：

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

あなたは本当に特にSRFI-41

を見なければならない、怠惰なストリームが作成され再帰的な関数では、のような熱心な言語でメモリがひどくリークします。具体的には、を避けてください。これを行うには、再帰関数を熱心でなく怠惰にする必要があります。これは、遅れ、力、およびを遅延させて遅延化する、遅れの実装がSRFI-45である必要があることを意味します。ストリームを再帰的に構築する関数は、それらのボディを遅延させてラップする必要があります。