どのように私は熱心な言語で怠惰なリストを作るのですか？

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-ストリームは任意の評価をせずに、この内部表現を取るようにする方法はありますか？

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

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

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

これはおそらく最も簡単な、最も実用的なソリューションですが、それはインクリメント番号の怠惰なリストを作成するための唯一の良いことです。あなたは呼び出されたときに、リストの連続する要素を生成する関数に渡すことで、これを一般化可能性があります：

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

これはかなりうまく動作します：

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

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

... 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 3

スキームで怠惰なリストは、ののストリームとして知られています。 ここで標準導入があります。

Answer 4

あなたは本当に SRFI-41 の

をご覧ください のあなたは、具体的にそれを避けるしない限り、

具体的には、再帰関数によって作成された怠惰なストリームは熱心な言語、の中でひどくメモリリークが発生します。そのためには、あなたは熱心ではない、また、再帰関数が怠惰にする必要があります。これはあなたの怠惰の実装が SRFI-45 に、輸出する必要があることを意味し遅延、力、との怠惰。ストリームを構築する関数を再帰的に怠惰で自分の体をラップする必要があります。