懒惰序列的思考

Question

以Clojure Wiki中的Fibonacci系列为例,Clojure代码为:

(def fib-seq
 (lazy-cat [0 1] (map + (rest fib-seq) fib-seq)))

如果你从[0 1]开始考虑这个问题,它是如何工作的？如果对思考过程有任何建议,那就很好了.

Answer 1

如您所述,[0 1]建立基本情况:序列中的前两个值为零,然后是一个.之后,每个值都是前一个值和该值之前的值的总和.因此,我们甚至无法计算序列中的第三个值,而不会在它之前至少有两个值.这就是为什么我们需要两个值来开始.

现在看一下map表格.它表示从两个不同的序列中获取头项,将它们与+函数组合(添加多个值以产生一个和),并将结果作为序列中的下一个值公开.该map形式将两个序列(可能是相等长度)压缩成一个相同长度的序列.

馈送到的两个序列map是相同基本序列的不同视图,移位一个元素.第一个序列是"除基本序列的第一个值之外的所有值".第二个序列是基本序列本身,当然,它包括第一个值.但基本序列应该是什么？

上面的定义说每个新元素是前一个元素(Z - 1)和前一个元素(Z - 2)的前一个元素的总和.这意味着扩展值序列需要以相同的顺序访问先前计算的值.我们肯定需要一个双元素移位寄存器,但我们也可以请求访问我们以前的结果.这就是fib-seq这里所谓的序列的递归引用.符号fib-seq指的是一个序列,它是一个零,一个,然后是它自己的Z - 2和Z - 1值之和的串联.

采用所调用的序列fib-seq,绘制第一个项会产生[0 1]向量的第一个元素- 零.绘制第二个项目会产生向量的第二个元素 - 一个.在绘制第三个项目时,我们咨询map生成序列并将其用作剩余值.map这里生成的序列以"其余部分"的第一项和第一项的总和开始[0 1],第一项[0 1]是零,第一项是零.这笔钱是一个.

绘制第四个项目map再次进行咨询,现在必须计算基本序列的"剩余部分"的第二项的总和,该基础序列是由基数序列生成的map,以及基本序列的第二项,即向量中的一项.[0 1].这笔钱是两个.

绘制第五项参考map,将基本序列的"剩余部分"的第三项 - 再次,由零和一的总和得到的那一项 - 以及我们刚刚发现的两个基本序列的第三项相加.

您可以看到它是如何构建的,以匹配系列的预期定义.更难看的是绘制每个项目是否重新计算所有前面的值两次 - 对于每个检查的序列一次map.事实证明这里没有这样的重复.

为了确认这一点,增加这样的定义fib-seq来仪器使用功能+:

(def fib-seq
  (lazy-cat [0 1] 
            (map 
              (fn [a b]
                (println (format "Adding %d and %d." a b))
                (+ a b))
            (rest fib-seq) fib-seq)))

现在要求前十项:

> (doall (take 10 fib-seq))
Adding 1 and 0.
Adding 1 and 1.
Adding 2 and 1.
Adding 3 and 2.
Adding 5 and 3.
Adding 8 and 5.
Adding 13 and 8.
Adding 21 and 13.
(0 1 1 2 3 5 8 13 21 34)

请注意,有八个调用+来生成前十个值.

在编写前面的讨论之后,我花了一些时间研究Clojure中懒惰序列的实现 - 特别是LazySeq.java文件- 并认为这是分享一些观察结果的好地方.

首先,请注意Clojure中的许多延迟序列处理函数最终会使用lazy-seq其他一些集合.lazy-seq创建Java类型的实例LazySeq,它为小型状态机建模.它有几个允许它以不同状态启动的构造函数,但最有趣的情况是仅以对nullary函数的引用开始的情况.以这种方式构造,LazySeq既没有评估函数也没有找到委托序列(ISeq在Java中输入).第一次询问LazySeq第一个元素 - via first- 或任何后继者 - 通过next或rest- 它评估函数,向下挖掘生成的对象以剥离其他LazySeq实例的任何包装层,最后通过java提供最内层对象function RT#seq(),导致一个ISeq实例.

在这一点上,LazySeq有一个ISeq到代表的委托电话first,next和rest.通常,"head" ISeq将是类型Cons,它在其"第一"(或"car")槽中存储恒定值,而ISeq在其"rest"(或"cdr")槽中存储另一个值.即ISeq在它的"休息"槽可以依次是LazySeq,在这种情况下访问它会再次需要该相同的功能的评价,剥离掉任何懒惰包装上的返回值,并通过该值通过RT#seq(),以产生另一个ISeq向其委托.

的LazySeq情况下保持连接在一起,但是具有强制一个(通过first,next或rest)使其通过一些非延迟直委派ISeq其后.通常,强制计算一个函数,该函数产生一个Cons绑定到第一个值并且它的尾部绑定到另一个值LazySeq; 它是一个生成器函数链,每个函数生成一个值(Cons"s"第一个"槽"),链接到另一个机会以产生更多值(LazySeq在Cons's"rest"槽中).

在上面的Fibonacci序列示例中,map将这些内容绑定到每个嵌套引用,fib-seq并通过重复调用将它们分开rest.每个这样的调用最多只会将LazySeq一个未评估的函数转换为LazySeq指向类似的函数Cons.转换后,任何后续访问都将快速解析为Conses - 存储实际值的位置.当map压缩的一个分支将fib-seq一个元素引导到另一个元素后面时,这些值已经被解析并且可用于恒定时间访问,而不需要进一步评估所需的生成器功能.

以下是一些图表,可帮助您查看代码的这种解释:

        +---------+
        | LazySeq |
fib-seq |  fn -------> (fn ...)
        |  sv     |
        |  s      |
        +---------+


        +---------+
        | LazySeq |
fib-seq |  fn -------> (fn ...) -+
        |  sv <------------------+
        |  s      |
        +---------+


        +---------+
        | LazySeq |
fib-seq |  fn     |
        |  sv -------> RT#seq() -+
        |  s  <------------------+
        +---------+


        +---------+   +------+
        | LazySeq |   | ISeq |
fib-seq |  fn     |   |      |
        |  sv     |   |      |
        |  s  ------->|      |
        +---------+   +------+


        +---------+   +--------+        +------+
        | LazySeq |   | Cons   |        | ISeq |
fib-seq |  fn     |   |  first ---> 1   |      |
        |  sv     |   |  more  -------->|      |
        |  s  ------->|        |        |      |
        +---------+   +--------+        +------+


        +---------+   +--------+        +---------+
        | LazySeq |   | Cons   |        | LazySeq |
fib-seq |  fn     |   |  first ---> 1   |  fn -------> (fn ...)
        |  sv     |   |  more  -------->|  sv     |
        |  s  ------->|        |        |  s      |
        +---------+   +--------+        +---------+

随着map进展,它从跳跃LazySeq到LazySeq(并因此Cons到达Cons),并且最右边仅在第一次调用first时next,或rest在给定时扩展LazySeq.

Answer 2

我的Clojure有点生疏,但这似乎是着名的Haskell单行的字面翻译:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

[我将使用伪Haskell,因为它更简洁一点.]

你需要做的第一件事就是让懒惰沉入其中.当你看到这样的定义时:

zeroes = 0 : zeroes

作为一个严格的程序员,你直接的直觉反应是"ZOMG无限循环!必须修复bug!" 但它不是一个无限循环.这是一个懒惰的无限循环.如果你做一些愚蠢的事情

print zeroes

然后,是的,有将是一个无限循环.但只要你只使用有限数量的元素,你就永远不会注意到递归实际上并没有终止.这真的很难得到.我还是没有.

懒惰就像货币制度:它基于这样的假设:绝大多数人从不使用他们的绝大部分资金.所以,当你把1000美元存入银行时,他们就不会把它保存在保险柜里.他们借给别人.实际上,他们利用这笔钱,这意味着他们向其他人借了5000美元.他们只在任何时候需要足够的钱,让他们能够迅速重新洗牌,以便它的存在,当你看着它,给你的外表,他们实际上让你的钱.

只要他们能够设法在你走到自动取款机时总是给钱,实际上你的绝大部分资金都不存在并不重要:他们只需要少量的资金来支付你的资金.你退学的时间.

懒惰的效果是一样的:每当你看到它,价值就在那里.如果你看一下第一个,第十个,第五个,第四个元素zeroes,它就会存在.但是,这只是在那里,如果和当你看它,不是之前.

这就是为什么这种无关紧要的递归定义的原因zeroes:只要你不试图查看无限列表的最后一个元素(或每个元素),你就是安全的.

下一步是zipWith.(Clojure的map仅仅是一个在其他编程语言是什么,通常有三种不同的功能概括:map,zip并zipWith在这个例子中,它被用作zipWith.)

zip功能族以这种方式命名的原因是因为它实际上像拉链一样工作,这也是如何最好地可视化它.假设我们有一些体育赛事,每个参赛者都有两次尝试,两次尝试的分数相加,以得出最终结果.如果我们有两个序列,run1并且run2每次运行得分,我们可以像这样计算最终结果:

res = zipWith (+) run1 run2

假设我们的两个列表是(3 1 6 8 6)和(4 6 7 1 3),我们并排排列这两个列表,比如拉链的两半,然后我们使用给定的函数(+在本例中)将它们压缩在一起以产生一个新的序列:

3   1   6   8   6
+   +   +   +   +
4   6   7   1   3
=   =   =   =   =
7   7  13   9   9

参赛者#3获胜.

那么,我们的fib样子是什么样的？

好吧,它从a开始0,然后我们追加a 1,然后我们追加无限列表的总和,并将无限列表移动一个元素.最简单的方法就是:

• 第一个元素是零:

  0
  

• 第二个元素是一个:

  0   1
  

• 第三个元素是第一个元素加上其余元素的第一个元素(即第二个元素).我们将这两个列表放在一起,就像拉链一样再次将其可视化.

  0   1
  +
  1
  =
  1
  

• 现在,我们刚才计算的元素不只是输出的的zipWith功能,它同时也输入,因为它被附加到这两个列表(这实际上是相同的列表,只需移动一位):

  0   1   1
  +   +
  1   1
  =   =
  1   2
  

• 等等:

  0   1   1   2
  +   +   +
  1   1   2
  =   =   =
  1   2   3
  
  
  0   1   1   2   3   ^
  +   +   +   +       |
  1   1   2   3   ^   |
  =   =   =   =   |   |
  1   2   3   5---+---+
  

或者,如果你以不同的方式绘制它并将结果列表和第二个输入列表(实际上它们是相同的)合并为一个:

0   1   1   2   3   ^
+   +   +   +   +   |
1 = 1 = 2 = 3 = 5---+

无论如何,这就是我想象它的方式.