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

很难说（这个网站不支持在反引号中的多行代码，您必须使用用户界面中指定的代码块按钮）代码中有一些 `__`，但这可能是这个： https://stuartsierra.com/2015/04/26/clojure-donts-concat

---

很抱歉，我已经修复了它。

---

@Eugene Pakhomov
我认为我已经看到导致问题的原因了，但我不明白其他解决方案有何不同，也就是说，为什么会没有堆栈溢出...

---

这是一个非平凡的推理问题（部分原因在于为什么 `concat` 难以安全使用），即使不使用 `concat`，你也可以通过将那个 `partition` 调用替换为 `(partition-all 2 1 (cons 0 row))` 来获得相同的行为（在非异常结果方面应该是等效的）。

不幸的是，没有更详细的信息，除非深入研究内置函数的实现细节，才能找出所有问题。但这里的一个简单修复是使用 `mapv` 替换 `map`，或用 `(partition-all 2 1 (into [0] row))` 替换那个 `partition` 调用。当然，这使行变得懒散，可能有避免这种情况的解决方案，但今天太晚了，我无法思考这个问题。

---

啊，当然 - 由于它使用 `(last coll)`，因此解决方案不会失败。因此，在将其提供给另一个 `lazy-seq` 之前，集合已经完全实现。最终，他们的解决方案在行级别也是懒散的。你的原始解决方案不是懒散的，但其实现确实会由于堆栈爆炸而付出代价。

---

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