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

结果显示我的更快（这是可以预料的，因为另一个用户依赖 on last，这是 O(n) 的）然而，当我去计算第1000行时，只有我的函数会抛出栈溢出错误。我努力想弄清楚为什么会发生这种情况，因为我不应该增加栈的大小。我遗漏了什么？

Comments

由于这种格式（这个网站不支持在反引号内多行代码，您必须使用UI中的指定代码块按钮）以及代码中的某些`__`，所以可能是这个：https://stuartsierra.com/2015/04/26/clojure-donts-concat

---

对此表示歉意，我已经修复了这个问题。

---

@Eugene Pakhomov
我认为我已经看到了导致问题的地方，但我看不出其他解决方案有什么不同，也就是为什么那里没有栈溢出。

---

这是一个不容易分析的问题（部分原因是因为`concat`难以安全使用），即使没有`concat`，仅仅把那个`partition`调用替换为`(partition-all 2 1 (cons 0 row))`也会出现相同的行为（在非异常结果方面应该是等效的）。

不幸的是，不深入了解内置函数的实现细节就无法添加更多详细信息。但在这里的一个简单的解决方案是将`map`替换为`mapv`，或者将那个`partition`调用替换为`(partition-all 2 1 (into [0] row))`。当然，这将使行变为贪婪的，但很可能存在一种避开这种情况的解决方案，但现在已经太晚了，我想不出什么办法。

---

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

---

哦，我现在好像明白了，但是我肯定还得再思考一下。不过，非常感谢你的帮助，我真的很感激！