Clojure中如何实现惰性序列？

Question

Clojure中如何实现惰性序列？

clojurelisplazy-evaluationlazy-sequences

30

我喜欢Clojure语言。唯一让我困扰的问题是，我不知道惰性序列是如何实现和工作的。

我知道惰性序列仅计算被要求的序列项。那么它是如何实现这一点的呢？

什么使得惰性序列如此高效，以至于它们不会消耗太多堆栈空间？
为什么可以用惰性序列包装递归调用，并且在大量计算时不再产生stack over flow（栈溢出）？
惰性序列需要消耗哪些资源来完成其工作？
在哪些场景下，惰性序列不太高效？
在哪些场景下，惰性序列最高效？

- mudgen

6

去年八月份我开始学习Clojure语言，大约5个月前，尝试理解这篇帖子时，我无法理解问题和答案。现在，这篇帖子中讨论的内容对我来说是有意义的！ :-) 因此，我想与其他Clojure学习者分享，学习Clojure的概念可能需要时间，但不要放弃学习它。 - Jay Somedon

3个回答

16

我知道惰性序列只会评估被请求的序列项，它是如何实现的呢？先前发布的答案已经很好地解释了这部分内容。我只想补充一点，"强制"一个惰性序列是一个隐式的函数调用，没有括号！:-)，也许这种思考方式能让某些事情更清晰。同时需要注意的是，强制一个惰性序列涉及到隐藏的变异——被强制的thunk需要生成一个值，将其存储在缓存中（再次变异！）并丢弃其可执行代码，因为不再需要（再次变异！）。

它们之所以不消耗堆栈，是因为它们消耗堆。惰性序列是一个数据结构，存在于堆上，包含一小段可执行代码，当需要更多数据结构时可以调用它来生成数据。

首先，像dbyrne提到的那样，如果thunk本身需要执行具有非常深层嵌套调用结构的代码，则使用惰性序列仍然可能导致栈溢出。

但基于一定意义上的使用惰性序列可以代替尾递归，到达一定程度后，你可以说它们有助于避免栈溢出。实际上，非常重要的是，生成惰性序列的函数不应该是尾递归的；与严格序列不同，使用惰性序列时将栈空间转移到堆空间，任何尝试以尾递归方式编写它们的尝试都只会破坏事情。

关键的洞察力在于，一个惰性序列是一个对象，在首次被创建时不包含任何项；当函数返回一个惰性序列时，仅返回这个"惰性序列对象"，在任何强制操作发生之前。因此，在任何强制操作发生之前，调用返回惰性序列的栈帧已经弹出。让我们来看一个例子生成器函数：

(defn foo-producer [] ; not tail recursive...
  (lazy-seq
    (cons :foo        ; because it returns the value of the cons call...
           (foo-producer)))) ; which wraps a non-tail self-call

这能够工作是因为lazy-seq立即返回，因此(cons :foo (foo-producer))也立即返回，并且外部对foo-producer的调用使用的堆栈帧会立即弹出。内部对foo-producer的调用隐藏在序列的rest部分中，这是一个thunk；如果/当强制执行该thunk时，它将短暂地在堆栈上使用自己的帧，但然后立即返回，如上所述等等。

像dbyrne所提到的分块略微改变了这个情况，因为每个步骤会产生更多的元素，但原则仍然相同：在生成惰性序列的相应元素时，每个步骤都使用了一些堆栈，然后在进行更多强制操作之前回收该堆栈。

在哪些场景下惰性序列不高效？

在哪些场景下惰性序列最高效？

如果你需要一次性持有整个序列，那么懒序列就没有意义。当未分块时，惰性序列在每一步都进行一次堆分配，或者在分块时在每个32步进行一次；在某些情况下，避免这种分配可以带来性能提升。

然而，惰性序列可以启用流水线数据处理模式：

(->> (lazy-seq-producer)               ; possibly (->> (range)
     (a-lazy-seq-transformer-function) ;               (filter even?)
     (another-transformer-function))   ;               (map inc))

以严格的方式执行此操作将分配大量堆内存，因为您必须将中间结果保留下来以便将它们传递到下一个处理阶段。此外，您需要将整个东西保存下来，但在(range)的情况下这是不可能的——一个无限序列！而当它是可能时，通常效率很低。

- Michał Marczyk

8

原先，在Clojure中，懒惰序列是按需逐项计算的。在Clojure 1.1中添加了分块序列以提高性能。与逐项计算不同，每次计算32个元素的“块”。这减少了惰性计算所产生的开销。此外，它允许Clojure利用底层数据结构。例如，PersistentVector实现为32个元素数组的树。这意味着要访问一个元素，必须遍历树，直到找到适当的数组。使用分块序列，可以一次获取整个数组。这意味着在需要重新遍历树之前，可以检索每个32个元素。

有关在需要完全惰性时强制逐项评估的讨论已经进行了一段时间。但是，我认为它尚未添加到语言中。

“你为什么可以将递归调用包装在懒惰序列中，并且不会因大规模计算而导致堆栈溢出？”

“你有例子吗？如果您将递归绑定到lazy-seq，则肯定会导致堆栈溢出。”

- dbyrne

检查我的递归惰性序列的答案。 - Isaac

我觉得我表达得有点不清楚。我理解递归惰性序列，但是不确定为什么Mudge担心它们会导致堆栈溢出。惰性本质上可以避免堆栈溢出的发生。 - dbyrne

啊，我明白了——有道理。很抱歉。 - Isaac

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Isaac · Accepted Answer

开始吧。

•我知道惰性序列只评估被请求的序列项，那么它是如何做到这一点的？

惰性序列（以下简称LS，因为我是一个懒人）由部分组成。已经评估的序列的头部或部分（实际上每次评估32个元素，从Clojure 1.1开始，我认为在1.2中也是如此）后面跟着一个叫做“thunk”的东西，它基本上是等待调用的信息块（将其视为创建序列的函数的剩余部分，未评估）。当它被调用时，thunk会评估所要求的任意数量，并创建一个新的thunk，必要时保留上下文（已经调用了多少，以便可以从之前暂停的位置恢复）。

因此，你执行(take 10 (whole-numbers))——假设whole-numbers是一个整数的惰性序列。这意味着你强制评估thunk 10次（尽管在内部，这可能会有一些不同，具体取决于优化）。

•什么使得惰性序列如此高效，以至于它们不会消耗太多的栈空间？

在阅读上一个答案之后，这一点变得更清楚了（我希望如此）：除非你特别调用某些东西，否则什么都不会被评估。当你调用某个东西时，序列的每个元素都可以单独进行评估，然后被丢弃。

如果序列不是惰性的，通常它会持有它的头部，这会消耗堆空间。如果它是惰性的，它会被计算，然后被丢弃，因为它对于后续的计算并不需要。

•为什么你可以将递归调用包装在惰性序列中，而不再为大型计算产生堆栈溢出？

查看上一个答案并考虑：lazy-seq宏（来自文档）将

will invoke the body only the first time seq
is called, and will cache the result and return it on all subsequent
seq calls.

查看filter函数，这是一个使用递归的很酷的LS：

(defn filter
  "Returns a lazy sequence of the items in coll for which
  (pred item) returns true. pred must be free of side-effects."
  [pred coll]
  (let [step (fn [p c]
                 (when-let [s (seq c)]
                   (if (p (first s))
                     (cons (first s) (filter p (rest s)))
                     (recur p (rest s)))))]
    (lazy-seq (step pred coll))))

• 懒惰序列需要消耗哪些资源才能完成其工作？

我不太确定你在问什么。懒惰序列需要内存和CPU周期。它们只是不断地执行计算操作以获取序列元素时，没有一直占用调用栈并填充调用栈。

• 在哪些情况下使用懒惰序列效率低下？

当你使用的是小的序列，计算速度快且不会被频繁使用时，将其转化成懒惰序列是低效的，因为创建懒惰序列需要额外的几个字符。

说真的，除非你试图做出极端高效的东西，否则使用懒惰序列就是最好的选择。

• 在哪些情况下使用懒惰序列最高效？

当你处理的序列很大，但只使用其中的部分时，这时使用懒惰序列可以获得最多的好处。

实际上，对于方便性、易于理解（一旦你掌握了它们）、对代码进行推理以及速度等方面，通常使用懒惰序列优于非懒惰序列。