scheme - Scheme 中的斐波那契数列流

Question

我目前正在尝试理解方案中流的概念。例如，我应该编写一个函数 fibonacci，它返回斐波那契数作为流表示形式。

函数的期望输出/用法如下所示:

> (define a (finbonacci))
> a
((0 0) . #<promise>)
> (tail a)
((1 1) . #<promise>)
> (tail (tail a))
((2 1) . #<promise>)

所以每个流元素代表一对n fib(n)。

流是这样预定义的:

(define the-empty-stream '())

(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream x y)
     (cons x (delay y)))))

(define head car)
(define (tail s) (force (cdr s)))
(define empty-stream? null?) 

我目前非常基本的解决方案尝试如下:

(define fibo
    (cons-stream 1
                 (cons-stream 1
                              (map + fibo (tail fibo))))))

但即使这可以计算任何东西，我也不知道如何将 n 传递到输出或后续流中。

Answer 1

您走在正确的道路上。唯一需要调整的是递归定义的精确表述。

考虑以下内容(其中 --- 表示我们正在添加):

1 1 2 3 5   8  ...   fib
1 2 3 5 8  13  ...   (stream-rest fib)
------------------   ---------------------------------
2 3 5 8 13 21  ...   (stream-rest (stream-rest fib))

注意 (stream-rest (stream-rest fib)) 是 fib 和 (stream-rest fib) 的总和。这意味着我们可以将 fib 定义为:

(define fib (stream-cons 1 (stream-cons 1 (stream-add fib (stream-rest fib)))))