recursion - 如何理解clojure的lazy-seq

Question

我正在尝试了解 clojure 的 lazy-seq运算符，以及一般惰性求值的概念。我知道这个概念背后的基本思想:表达式的计算被延迟到需要值时。

一般来说，这可以通过两种方式实现:

在编译时使用宏或特殊形式；

在运行时使用 lambda 函数

使用惰性求值技术，可以构建无限的数据结构，这些数据结构被评估为已使用。这些无限序列使用 lambda、闭包和递归。在clojure中，这些无限的数据结构是使用lazy-seq生成的。和 cons形式。

我想了解如何lazy-seq它的魔法吗。我知道它实际上是一个宏。考虑以下示例。

(defn rep [n]
  (lazy-seq (cons n (rep n))))

在这里，rep函数返回类型为 LazySeq 的惰性求值序列，现在可以使用序列 API 转换和使用(从而评估)。该 API 提供功能 take , map , filter和 reduce .

在扩展形式中，我们可以看到如何利用 lambda 来存储单元的配方，而无需立即对其进行评估。

(defn rep [n]
  (new clojure.lang.LazySeq (fn* [] (cons n (rep n))))) 

但是序列 API 是如何与 LazySeq 一起实际工作的？ ?

在下面的表达式中实际发生了什么？

(reduce + (take 3 (map inc (rep 5))))

中间操作如何map应用于序列，

怎么样take限制序列和

终端如何操作reduce评估序列？

此外，这些函数如何与 Vector 一起使用？或 LazySeq ?

此外，是否可以生成嵌套的无限数据结构？:包含列表的列表，包含列表，包含列表......无限宽和深，评估为使用序列 API 消耗？

最后一个问题，这之间有什么实际区别吗

(defn rep [n]
  (lazy-seq (cons n (rep n))))

和这个？

(defn rep [n]
  (cons n (lazy-seq (rep n))))

Answer 1

这是很多问题!

seq API 如何与 LazySeq 一起实际工作？

如果您查看 LazySeq 的类源代码，您会注意到它实现了 ISeq 接口(interface)，提供了 first 、 more 和 next 等方法。
map 、 take 和 filter 之类的函数是使用 lazy-seq (它们产生惰性序列)以及 first 和 rest (反过来使用 more )构建的，这就是它们如何使用惰性序列作为输入集合的方式 - 通过使用 first 和 more LazySeq 实现类(class)。

在下面的表达式中实际发生了什么？
(reduce + (take 3 (map inc (rep 5))))
关键是看 LazySeq.first 是如何工作的。它将调用包装的函数来获取并记住结果。在您的情况下，它将是以下代码:
(cons n (rep n))
因此，它将是一个 cons 单元，以 n 作为其值，另一个 LazySeq 实例(对 rep 递归调用的结果)作为其 rest 部分。它将成为这个 LazySeq 对象的实现值，first 将返回缓存的 cons 单元格的值。

当您对其调用 more 时，它​​将以相同的方式确保特定 LazySeq 对象的值被实现(或重用的内存值)并对其调用 more(在这种情况下，在包含另一个 more 对象的 cons 单元上调用 LazySeq)。

一旦您使用 LazySeq 获得 more 对象的另一个实例，当您对其调用 first 时，故事就会重复。
map 和 take 将创建另一个 lazy-seq，它将调用作为参数传递的集合的 first 和 more(只是另一个懒惰的 seq)，所以这将是类似的故事。区别仅在于传递给 cons 的值是如何生成的(例如，将 f 调用到在 first 中映射的 LazySeq 值上调用的 map 获得的值，而不是像 n 函数中的 rep 这样的原始值)。

使用 reduce 会简单一些，因为它将使用 loop 和 first 和 more 来迭代输入的惰性序列并应用减少函数来产生最终结果。

由于 map 和 take 的实际实现看起来像我鼓励您检查它们的源代码 - 它很容易理解。

seq API 如何处理不同的集合类型(例如惰性 seq 和持久向量)？

如上所述， map 、 take 等函数在 first 和 rest 方面工作(提醒——rest 是在 more 之上实现的)。因此，我们需要解释 first 和 rest/more 如何与不同的集合类型一起工作:它们检查集合是否实现了 ISeq(然后它直接实现了这些功能)，或者它们尝试创建集合的 seq View 并对其实现first 和 more 。

是否可以生成嵌套的无限数据结构？

这绝对有可能，但我不确定您想要获得的确切数据形状。你的意思是得到一个懒惰的 seq，它会生成另一个序列作为它的值(而不是像 n 中的 rep 这样的单个值)但将它作为一个平面序列返回？

(defn nested-cons [n]
  (lazy-seq (cons (repeat n n) (nested-cons (inc n)))))

(take 3 (nested-cons 1))

;; => ((1) (2 2) (3 3 3))

那宁愿返回 (1 2 2 3 3 3) ？

对于这种情况，您可以使用 concat 而不是 cons ，它会创建两个或更多序列的惰性序列:

(defn nested-concat [n]
  (lazy-seq (concat (repeat n n) (nested-concat (inc n)))))

(take 6 (nested-concat 1))

;; => (1 2 2 3 3 3)

这有什么实际区别吗

(defn rep [n]
  (lazy-seq (cons n (rep n))))

和这个？

(defn rep [n]
  (cons n (lazy-seq (rep n))))

在这种特殊情况下并非如此。但是在 cons 单元格不包装原始值而是计算它的函数调用结果的情况下，后一种形式并不是完全惰性的。例如:

(defn calculate-sth [n]
  (println "Calculating" n)
  n)

(defn rep1 [n]
  (lazy-seq (cons (calculate-sth n) (rep1 (inc n)))))

(defn rep2 [n]
  (cons (calculate-sth n) (lazy-seq (rep2 (inc n)))))

(take 0 (rep1 1))
;; => ()

(take 0 (rep2 1))
;; Prints: Calculating 1
;; => ()

因此后一种形式将评估其第一个元素，即使您可能不需要它。