scheme - 无限流的累加器

Question

我正在尝试为无限流实现一个累加器。我写了下面的代码，但它进入了一个无限循环并且无法终止

(define (stream-first stream) (car stream))
(define (stream-second stream) (car ((cdr stream))))
(define (stream-third stream) (car ((cdr ((cdr stream))))))
(define (stream-next stream) ((cdr stream)))


(define (stream-foldl func accum stream)
    (cond
         [(empty? stream) accum]
         [else (stream-foldl func (func (stream-first stream) accum) (stream-next stream))] ))

我已经编写了一些测试来演示我正在尝试实现什么

(define (natural-nums)
   (define (natural-nums-iter n)
   (thunk
   (cons n (natural-nums-iter (+ n 1)))))
   ((natural-nums-iter 0)))

(define x (stream-foldl cons empty (natural-nums)))
(check-equal? (stream-first x) empty)
(check-equal? (stream-second x) (list 0))
(check-equal? (stream-third x) (list 1 0))

(define y (stream-foldl (curry + 1) 10 (naturals)))
(check-equal? (stream-first y)  10)
(check-equal?  (stream-second y) 11)
(check-equal?  (stream-third y)  13)

这是我的 stream-foldl 函数的踪迹

>(stream-foldl
  #<procedure:cons>
  '()
  '(0 . #<procedure:...9/saccum.rkt:25:0>))
()>(stream-foldl
  #<procedure:cons>
  '(0)
  '(1 . #<procedure:...9/saccum.rkt:25:0>))
(0)>(stream-foldl
  #<procedure:cons>
  '(1 0)
  '(2 . #<procedure:...9/saccum.rkt:25:0>))
(1 0)>....

我相信我没有正确设置基本情况，因此永远不会从递归调用中终止

Answer 1

Fold 应该查看流中的每个元素，然后根据这些元素生成结果。对于无限流，折叠不会终止也就不足为奇了(您如何能够查看无限流中的每个元素？)。

你可以做什么:

从无限流中产生有限流。 stream-take可以用于那个。 stream-take 的示例实现:

;; Returns a stream containing the first n elements of stream s.
(define (stream-take n s)
  (cond ((zero? n) empty-stream)
        ((empty? s) (error "Stream is shorter than n")
        (else
          (delay (stream-first s)
                 (stream-take (- n 1) (stream-rest s)))))))
          ; Note: 'delay' is the same as the 'thunk' in your code.

然后，使用折叠的实现或 stream-fold 折叠有限流.