使用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行时，只在我的函数中遇到了栈溢出错误。我在努力理解为什么会发生这种情况，因为我不应该增加栈的大小。我错过了什么？

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))`。当然，这会使行变得急切，并且可能有一个避免这种情况的解决方案，但对我来说已经太晚了，无法考虑这个问题了。

---

啊，当然——它们的使用并未失败，因为它们使用了`(last coll)`。因此，在将其馈送到另一个`lazy-seq`之前，集合已经完全实现。最后，它们的解决方案在行级别也是急切的。你的原始解决方案不是急切的，但它非常实现起来付出了巨大的栈膨胀的代价。

---

哦，我现在看明白了，但我肯定要再考虑一下。无论如何，非常感谢您的帮助，我真的很感激！