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

惰性列表的问题在于，Scheme 首先计算内部表达式（惰性列表（+ from 1））导致过程进入无限递归。

有没有办法让 con-stream 在没有任何评估的情况下采用这个内部表达式？

4

4 回答 4

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 回答
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。我们可以通过缓存 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
于 2009-06-13T22:45:00.663 回答
2

Scheme 中的惰性列表称为流。这是标准的介绍。

于 2009-06-13T07:22:23.643 回答
1

你真的应该看看SRFI-41

特别是，由递归函数创建的惰性流将在急切的语言中严重泄漏内存，除非您特别避免它。为此，您还需要使递归函数变得惰性，而不是急切。这意味着你的惰性实现需要是SRFI-45，它导出延迟、强制和惰性。递归构建流的函数必须将它们的主体包裹在惰性中。

于 2012-07-13T06:07:18.387 回答