使用 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` 调用来得到相同的行为。（从非异常结果的角度来看应该等效）。

不幸的是，我无法提供更多细节，除非深入研究内置函数的实现细节来找出全部情况。但是这里的一个简单修复是用 `mapv` 替换 `map`，或者用 `(partition-all 2 1 (into [0] row))` 替换那个 `partition` 调用。当然，这会使得行变得 eager，并且可能有一个避免这种情况的解决方案，但现在已经太晚考虑这个问题了。

---

啊，当然——它们的解决方案没有失败，因为它们使用了 `(last coll)`。所以这个集合在馈入另一个 `lazy-seq` 之前已经被完全实现了。最终，它们的解决方案也是在行级别上 eager。你的原始解决方案不是 eager，但它的实现却在栈上造成了爆栈。

---

我明白了，但我肯定还需要更多思考。无论如何，非常感谢你的帮助，我真的很感激！