理解在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 ....

Is this a correct "representation" of the state of head and tail during the execution? If so, why does (rest fibs) return a single item? Is it because of a recursive call like (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) ...)

把它(map + fibs (rest fibs)视为已经存在的纤维,以及在已经存在的纤维列表上移动的状态(这很好,因为它最终计算了我们在路上需要的一切).

它也可以帮助写下两个序列:

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

(我在这里画箭头表示我们已经得到了什么以及结果在哪里,但我不能在这里做得那么好).