clojure - 了解 Clojure 中延迟斐波那契实现的执行

Question

我试图理解以下代码的执行:

(def fibs 
  (concat (lazy-seq [0 1]) (lazy-seq (map + fibs (rest fibs)))))

这就是我期望的执行结果

[0 1 : (map + [0 1] [1]) => 1
[0 1 1 : (map + [0 1 1] [1 1]) => 1 2
[0 1 1 1 2 : (map + [0 1 1 2] [1 1 2]) => 1 2 3
[0 1 1 1 2 1 2 3 : (map + [0 1 1 2 3] [1 1 2 3]) => 1 2 3 5
[0 1 1 1 2 1 2 3 1 2 3 5 .... 

这显然是不正确的，因为结果是错误的。我能想到的唯一能产生正确结果的执行是:

[0 1 : (map + [0 1] [1]) => 1
[0 1 1 : (map + [1 1] [1]) => 2
[0 1 1 2 : (map + [1 2] [2]) => 3
[0 1 1 2 3 : (map + [2 3] [3]) => 5
[0 1 1 2 3 5 ....

这是执行过程中 head 和 tail 状态的正确“表示”吗？如果是这样，为什么 (rest fibs) 返回单个项目？是因为像 (rest (rest (rest [1 1 2 3]))) 这样的递归调用吗？

Answer 1

Fibs 是 (0 1 ...) (因为开头有 (concat [0 1] ... ) )。 (rest fibs) 是 (1 ...)。那么 (map + fibs (rest fibs)) 是

((+ 0 1) ...) => (1 ...)

所以小纤维是(0 1 1 ...)。由于我们得到了下一个项目，我们可以计算另一个项目:

(1 (+ 1 1) ...) => (1 2 ...)

事情还在继续......

(1 2 (+ 1 2) ...)

将 fibs 视为已经存在，并且将 (map + fibs (rest fibs) 的状态视为在已存在的 fibs 列表上移动(这很好，因为它最终会计算出我们所需要的一切)。

写下两个序列也可能有所帮助:

 (0 1 1 2 3 5 ...)
+(1 1 2 3 5 ...)
=(1 2 3 5 8 ...)

(我会在此处绘制箭头来指示我们已经得到的内容以及结果的去向，但我在这里做不到那么好)。