열렬한 언어로 게으른 목록을 어떻게 만드나요?

Question

나는 계획에서 게으른 목록을 만들고 싶었다. 이것이 내가 지금까지 가지고있는 것입니다.

;; 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))을 평가하여 먼저 절차가 무한 재귀로 들어가게한다는 것입니다.

Contream이 평가 없이이 내부 표현을 취하게하는 방법이 있습니까?

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 다시. 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))))

이제는 다음과 같이 작동합니다.

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

계획의 게으른 목록은 a로 알려져 있습니다 개울. 표준 소개는 다음과 같습니다.

Answer 4

당신은 정말로보아야합니다 SRFI-41

특히, 재귀 함수에 의해 생성 된 게으른 스트림은 열렬한 언어로 메모리가 나쁘게 누출됩니다. ~하지 않는 한 당신은 구체적으로 그것을 피합니다. 그렇게하려면 재귀적인 기능도 게으르고 열망하지 않도록해야합니다. 이것은 당신의 게으름 구현이 필요하다는 것을 의미합니다 SRFI-45, 지연, 힘, 그리고 게으른. 스트림을 구축하는 기능은 재귀 적으로 몸을 게으른 상태로 감해야합니다.