Clojure 中使用 lazy-seq 时发生栈溢出

Question

我通过解决rich4clojure存储库中的问题来学习 Clojure。问题 147 要求创建一个函数，该函数根据给定的初始行返回遵循帕斯卡三角形规则的行序列。例如，对于 [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))

结果发现我的解决方案更快（这在某种程度上是可以预料的，因为另一个用户依赖 last，其时间为 O(n)）。然而，当我尝试计算第 1000 行时，只有在我的函数中才会出现堆栈溢出错误。我很难理解为什么会发生这种情况，因为我没有增加堆栈大小。我错过了什么？

Comments

格式化较为困难（这个网站不支持使用反引号的多行代码，您必须通过 UI 中的 Code Block 按钮使用），并且在代码中有一些 `__` 符号，但可能是这个：[链接](https://stuartsierra.com/2015/04/26/clojure-donts-concat)

---

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

---

@Eugene Pakhomov
我认为我看到了为什么这会导致问题，但我不知道其他解决方案有何不同，也就是说，为什么那里没有栈溢出。

---

这不是一个简单的问题（部分原因是因为“concat”很难安全使用）并且即使没有“concat”你也会得到同样的行为，比如用`(partition-all 2 1 (cons 0 row))`代替`partition`调用（在非异常结果方面应该是等效的）。

不幸的是，我无法添加更多细节，除非深入到内置函数的实现细节中才能弄清楚。但在这里的一个简单修复是将其`map`替换为`mapv`或将该`partition`调用替换为`(partition-all 2 1 (into [0] row))`。当然，这会使行变得即时，可能有一个避免这一点的解决方案，但对我来说现在已经太晚了去思考它了。

---

当然——他们的解决方案不会失败，因为它使用了`(last coll)`。因此，在将其馈入另一个`lazy-seq`之前，该集合已经完全实现。最终，他们的解决方案在行级别也是即时的。你原来的解决方案不是即时的，但它的实现付出了吹胀堆栈的代价。

---

哦，我现在好像明白了，但我肯定还要多想想。无论如何，非常感谢您的帮助，我真的很感激！