4

私は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))

lazy-list の問題は、Scheme が最初に内部式 (lazy-list (+ from 1)) を評価し、手続きが無限再帰に陥ることです。

コンストリームが評価なしでこの内部表現を取るようにする方法はありますか?

4

4 に答える 4

3

マクロルートに行きたくない場合は、いつでも放棄して次のよう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
于 2009-06-13T22:45:00.663 に答える
3

解決策は、マクロを使用することです。私はスキームの専門家ではありません (特にマクロの専門家ではありません) が、このスニペットはインスピレーションとして役立つかもしれません:

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

于 2009-06-13T00:43:36.800 に答える
2

Scheme の遅延リストはストリームと呼ばれます。定番の紹介はこちら。

于 2009-06-13T07:22:23.643 に答える
1

あなたは本当にSRFI-41を見るべきです

特に、再帰関数によって作成されたレイジー ストリームは、明確に回避しない限り、熱心な言語でひどくメモリ リークします。そのためには、再帰関数を熱心ではなく怠惰にする必要があります。これは、遅延、強制、および遅延をエクスポートする遅延実装がSRFI-45である必要があることを意味します。ストリームを再帰的に構築する関数は、その本体を lazy でラップする必要があります。

于 2012-07-13T06:07:18.387 に答える