concat是一个棘手的函数. 字面意思是将两个collection组合(concatenate)起来. 如果只有两个coll, 那它可谓名副其实.

但这仅仅是它的表象, 本质上, 它是一个懒序列(lazy sequence)函数.

这里有一个我在实际场景中看到的例子. 假设有一个循环, 将某些中间结果连成合并的表结果:

(defn next-results
  "Placeholder for function which computes some intermediate
  collection of results."
  [n]
  (range 1 n))

(defn build-result [n]
  (loop [counter 1
         results []]
    (if (< counter n)
      (recur (inc counter)
             (concat results (next-results counter)))
      results)))

这个函数的难题在于当n很小时, 完全没有问题.

(take 21 (build-result 100))
;;=> (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6)

但是当n变得足够大时, 突然就栈溢出了:

(first (build-result 4000))
;; StackOverflowError   clojure.core/seq (core.clj:133)

stacktrace, 我们看到concat和seq一遍又一遍:

(.printStackTrace *e *out*)
;; java.lang.StackOverflowError
;;      at clojure.core$seq.invoke(core.clj:133)
;;      at clojure.core$concat$fn__3955.invoke(core.clj:685)
;;      at clojure.lang.LazySeq.sval(LazySeq.java:40)
;;      at clojure.lang.LazySeq.seq(LazySeq.java:49)
;;      at clojure.lang.RT.seq(RT.java:484)
;;      at clojure.core$seq.invoke(core.clj:133)
;;      at clojure.core$concat$fn__3955.invoke(core.clj:685)
;;      at clojure.lang.LazySeq.sval(LazySeq.java:40)
;;      at clojure.lang.LazySeq.seq(LazySeq.java:49)
;;      at clojure.lang.RT.seq(RT.java:484)
;;      at clojure.core$seq.invoke(core.clj:133)
;;      at clojure.core$concat$fn__3955.invoke(core.clj:685)
;;      at clojure.lang.LazySeq.sval(LazySeq.java:40)
;;      at clojure.lang.LazySeq.seq(LazySeq.java:49)
;;      ... hundreds more ...

因此, 我们有一个栈溢出, 但为什么呢, 我们使用recur呀...我们的代码没有消耗栈的, 对吧?

让我们仔细看看concat的定义, 主体逻辑则如下所示:

(defn concat [x y]
  (lazy-seq
    (if-let [s (seq x)]
      (cons (first s) (concat (rest s) y))
      y)))

lazy-seq是一个宏, 它将其主体包装在函数中, 然后将函数包装在LazySeq对象中.

build-result中的循环调用了先前concat返回的LazySeq上的concat, 创建了像这样的LazySeq链:

+----------+
| lazy-seq |
+--+-------+
   |
+--v---+   +----------+
|  Fn  +---> lazy-seq |
+------+   +--+-------+
              |
           +--v---+   +----------+
           |  Fn  +---> lazy-seq |
           +------+   +--+-------+
                         |
                         ....

调用seq强制LazySeq调用函数, 以实现其值. 大多数Clojure序列函数(例如first)都会自动为您调用seq. 打印懒惰的序列也会强制其被实现.

在我们的concat链的情况下, 每个LazySeq的fn都返回另一个LazySeq. seq必须通过它们递归, 直到它找到实际值. 如果此递归过深, 则会溢出堆栈.

仅构造序列不会触发错误:

(let [r (build-result 4000)]
  nil)
;;=> nil

仅当我们试图实现它时, 它才会溢出:

(let [r (build-result 4000)]
  (seq r)
  nil)
;; StackOverflowError   clojure.lang.RT.seq (RT.java:484)

这是生产代码中的严重错误, 因为它可能远离其源, 并且seq的累积堆栈帧会阻止我们看到错误来源.

不要concat

修复问题的方法是首先避免concat. 我们的循环立即构建结果集合, 而不是惰性地, 因此我们可以使用vector并调用into来累计结果:

(defn build-result-2 [n]
  (loop [counter 1
         results []]
    (if (< counter n)
      (recur (inc counter)
             (into results (next-results counter)))
      results)))

这样做的代价是立即实现整个集合:

(time (doall (take 21 (build-result-2 4000))))
;; "Elapsed time: 830.66655 msecs"
;;=> (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6)

这个特定的例子也可以写成一个适当的惰性序列, 如下所示:

(defn build-result-3 [n]
  (mapcat #(range 1 %) (range 1 n)))

从而避免了事先构建整个序列:

(time (doall (take 21 (build-result-3 4000))))
;; "Elapsed time: 0.075421 msecs"
;;=> (1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6)

在中国古老的炼金术中, 硝石, 硫磺, 木炭三者组合, 一遇见明火就会引发爆炸.

同样, 在Clojure编程中, recur(或者是reducee), Concat, Lazy-seq(可以是concat, map, filter等)三者混合, 一遇见必须一次性求值的场景(nth, seq, last, first, etc.), 就有可能发生栈溢出.

编程中可以遵循一般性原则: 不要构建惰性的惰性序列.

还有许多这种错误的变化, 例如:

(first (reduce concat (map next-results (range 1 4000))))
;; StackOverflowError   clojure.core/seq (core.clj:133)
(nth (iterate #(concat % [1 2 3]) [1 2 3]) 4000)
;; StackOverflowError   clojure.core/seq (core.clj:133)
(first (:a (apply merge-with concat
                  (map (fn [n] {:a (range 1 n)})
                       (range 1 4000)))))
;; StackOverflowError   clojure.core/seq (core.clj:133)

不只是concat, 惰性序列函数都可能造成这种情况. concat出现频率比较高而已.