为什么需要 cons 来防止无限递归

Question

定义无限序列时，我注意到 cons 是避免无限递归所必需的。但是，我不明白的是为什么。这是有问题的代码：

(defn even-numbers
  ([] (even-numbers 0))
  ([n] (cons n (lazy-seq (even-numbers (+ 2 n))))))

(take 10 (even-numbers))
;; (0 2 4 6 8 10 12 14 16 18)

效果很好；但由于我喜欢质疑事物，我开始想知道为什么需要 cons（除了包含 0）。毕竟，lazy-seq 函数创建了一个 lazy-seq。这意味着，在调用（或分块）之前不应计算其余值。所以，我试了一下。

(defn even-numbers-v2
  ([] (even-numbers-v2 0))
  ([n] (lazy-seq (even-numbers-v2 (+ 2 n)))))

(take 10 (even-numbers-v2))
;; Infinite loooooooooop

所以，现在我知道 cons 是必要的，但我想知道为什么 cons 是必要的，以导致对所谓的惰性序列进行惰性评估

Answer 1

Lazy seqs 是一种延迟计算实际 seq 元素的方法，但最终确实需要计算这些元素。这实际上不必涉及 cons——例如，clojure.core/concat 在处理分块操作数时使用 "chunked conses"，并且可以将任何具体的 seq 类型包装在 lazy-seq 中——但是如果要进行任何 seq 处理，则在 lazy-seq 的许多层之后需要某种非惰性 return。否则连第一个元素都没有。

将您自己置于一个被传递了惰性 seq 的函数的位置。实际上，调用者告诉它 "here's this thing that's for all intents and purposes a seq, but I don't feel like computing the actual elements until later"。现在我们的函数需要一些实际的元素来操作，所以它会戳戳 seq 以尝试让它产生一些元素……然后呢？

如果剥离一些 lazy-seq 层最终产生一个 Cons 单元格、一个列表、一个向量上的序列或任何其他具有实际元素的具体序列类事物，那么很好，函数可以从中读取一个元素并取得进展。

但是如果剥离这些层的唯一结果是更多的层被显露出来，并且它一直 lazy-seqs 一直向下，那么......没有找到任何元素。并且由于原则上无法确定是否通过剥离足够多的层最终可以生成某些元素（参见 the halting problem），因此使用此类不可实现的惰性序列的函数通常别无选择，只能永远循环下去。

换个角度，让我们考虑一下您的 even-numbers-v2 函数。它接受一个参数和 return 一个 lazy-seq 对象包装对自身的进一步调用。现在，它接收的原始参数 (n) 用于计算递归调用的参数 ((+ 2 n))，但不会放置在任何数据结构中或以其他方式传送给调用者，因此没有理由它会作为结果序列的一个元素出现。调用者所看到的只是该函数产生了一个惰性 seq 对象，它别无选择，只能解包以搜索序列的实际元素；当然，这种情况会重复出现（在这种情况下，严格来说不是永远，只是因为 + 在处理 long 时最终会抱怨算术溢出）。

为什么需要 cons 来防止无限递归

Why is cons necessary to prevent infinite recursion

clojure

lazy-evaluation