为什么reduce在Clojure中给出了StackOverflowError？

Question

我正在尝试连接一系列Seqs.

我可以做到apply concat.

user=> (count (apply concat (repeat 3000 (repeat 3000 true))))
9000000

但是,根据我有限的知识,我会假设使用apply力量来实现懒惰的Seq,这对于非常大的输入来说似乎并不合适.如果可以的话,我宁愿懒洋洋地这样做.

所以我认为使用reduce就可以完成这项工作.

user=> (count (reduce concat (repeat 3000 (repeat 3000 true))))

但这导致了

StackOverflowError   clojure.lang.RT.seq (RT.java:484)

我很惊讶,因为我会认为语义reduce意味着它是尾调用的递归.

两个问题:

• 这apply是最好的方法吗？
• 是reduce一般不适合大投入？

Answer 1

使用apply.当函数参数是惰性时,也是如此apply.

让我们检查一下对底层子序列的计数副作用:

(def counter (atom 0))

(def ss (repeatedly 3000 
          (fn [] (repeatedly 3000 
            (fn [] (do (swap! counter inc) true))))))


(def foo (apply concat ss))

so.core=> @counter
0

so.core=> (dorun (take 1 foo))
nil

so.core=> @counter
1

so.core=> (dorun (take 3001 foo))
nil

so.core=> @counter
3001

reduceconcat由于thunk组成而导致大量s溢出

延迟序列,例如由concatthunk 产生的序列,延迟函数调用.当你concat的结果是concat你已经在另一个thunk中嵌套thunk.在你的函数中,嵌套深度为3000,因此一旦请求第一个项目并且展开3000个嵌套的thunk,堆栈就会溢出.

so.core=>  (def bar (reduce concat (repeat 3000 (repeat 3000 true))))
#'so.core/bar

so.core=> (first bar)
StackOverflowError   clojure.lang.LazySeq.seq (LazySeq.java:49)

懒惰序列的实现通常会在seq编辑时展开嵌套的thunks trampoline样式并且不会打击堆栈:

so.core=> (loop [lz [1], n 0] 
            (if (< n 3000) (recur (lazy-seq lz) (inc n)) lz))
(1)

但是,如果你seq在实现它的同时在未实现部分的惰性序列中调用...

so.core=> (loop [lz [1], n 0] 
            (if (< n 3000) (recur (lazy-seq (seq lz)) (inc n)) lz))
StackOverflowError   so.core/eval1405/fn--1406 (form-init584039696026177116.clj:1)

so.core=> (pst 3000)

StackOverflowError
        so.core/eval1619/fn--1620 (form-init584039696026177116.clj:2)
        clojure.lang.LazySeq.sval (LazySeq.java:40)
        clojure.lang.LazySeq.seq (LazySeq.java:49)
        clojure.lang.RT.seq (RT.java:484)
        clojure.core/seq (core.clj:133)
        so.core/eval1619/fn--1620 (form-init584039696026177116.clj:2)
        clojure.lang.LazySeq.sval (LazySeq.java:40)
        clojure.lang.LazySeq.seq (LazySeq.java:49)
        clojure.lang.RT.seq (RT.java:484)
        clojure.core/seq (core.clj:133)
        ... (repeatedly)

然后你最终建立seq堆栈帧.实施concat就是这样.检查StackOverflowError的堆栈跟踪,您concat会看到类似的.