使用 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))

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

Comments

由于格式有限（此网站不支持多行代码在反引号中，您必须使用 UI 中的指定代码块按钮），并且代码中有些 `__`，但可能是这个： 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))`。当然，这会使行变得 eager，可能有一个避免这种方法的解决方案，但对我来说现在已经太晚了去思考它。

---

啊，当然 - 他们的方案没有失败是因为它使用了`(last coll)`。所以集合并没有在放入另一个`lazy-seq`之前就完全实现。最终，他们的解决方案在每一行层面上也是 eager 的。你的原始解决方案不是 eager 的，但它的实现不得不为此付出代价，导致栈膨胀。

---

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