使用lazy-seq引起的堆栈溢出

Question

我通过学习来自 rich4clojure 项目的应用问题来学习 Clojure。问题147 要求创建一个函数，该函数返回给定初始行的 Pascal 三角形的规则懒序列。例如，对于 [3 1 2]，下一行是 [3 4 3 2]。这是我的解决方案

(defn pascal
      ([row] (lazy-seq (cons row (__ row :next))))
      ([row _]
       (lazy-seq
        (let [next-row (map #(apply +' %) (partition 2 1 (concat '(0) row '(0))))]
          (cons next-row (pascal next-row :next)))))))

我决定对其进行测试，并与其他解决方案进行比较。例如，一位用户写了

(defn pascal [coll]
(lazy-seq
  (cons coll
        (pascal (let [middle (map #(apply +' %) (partition 2 1 coll))]
                       (concat [(first coll)] middle [(last coll)]))))))

我通过评估以下内容来对两个解决方案进行计时

time (nth (nth (pascal [1]) 400) 50))

结果我的解决方案更快（这在某种程度上是可以预期的，因为另一位用户依赖于 O(n) 的 last）。然而，当我尝试计算第1000行的内容时，仅在 my 函数中出现堆栈溢出错误。我无法理解为什么会发生这种情况，因为我不应该增加堆栈的大小。我遗漏了什么？

Comments

由于格式问题（本网站不支持在反引号中放置多行代码，您必须在 UI 中使用指定的代码块按钮），以及代码中的某些 `__`，因此可能是因为这个：https://stuartsierra.com/2015/04/26/clojure-donts-concat

---

对此表示歉意，我已经修复了它。

---

@Eugene Pakhomov
我认为我看到了导致问题的原因，但我不明白其他解决方案有什么不同，即为什么没有堆栈溢出。

---

这不是一件简单的事情去推理（这也是`tconcat`难以安全使用的原因之一），即使不使用`tconcat`，你也可以通过用`(partition-all 2 1 (cons 0 row))`代替`partition`调用获得相同的行为（在非异常结果方面应该等效）。

不幸的是，在没有深入挖掘内置函数的实现细节就无法添加更多细节的情况下，这里的一个简单修复是，用`mapv`替换`map`，或者将那个`partition`调用替换为`(partition-all 2 1 (into [0] row))`。当然，这会使行变得渴求资源，很可能存在避免这种情况的解决方案，但我现在太晚了，无法思考。

---

啊，当然了——他们的解决方案没有失败是因为它们使用了`(last coll)`。因此，这个小集合在馈入另一个`lazy-seq`之前已经全部实现。最终，他们的解决方案在行级别上也是渴求资源的。你原始的解决方案并不是渴求资源，但它的实现却为此付出了大量栈空间的代价。

---

哦，我现在似乎明白了，但我确实需要更多考虑。无论如何，非常感谢你的帮助，我真的很感激！