clojure - 在累加器上进行归约和映射会产生堆栈溢出

Question

为什么我需要将这段代码中的map替换为mapv以防止堆栈溢出:

#!/bin/bash lein-exec                                                           


(println (reduce (fn [acc _]                                                    
                   ;;(mapv #(inc %) acc))                                       
                   (map #(inc %) acc))                                          
                 (repeat 2 0)                                                   
                 (range (long 1e6))))           

~

我不明白当惰性时acc是如何处理的。感谢您的见解。

Answer 1

基本上，您得到的是大量嵌套的惰性序列，当它们被戳破时，会导致堆栈溢出。

让我们看一个更小的例子:

(reduce (fn [acc _]
          (map inc acc))
        (repeat 2 0)
        (range 3))

由于 map 是惰性的，因此上面的结果将是下一个:

(map inc (map inc (map inc (0 0)))

所以你并不是急于将 acc 与 inc 映射，而只是将惰性序列一个放入另一个，稍后再实现。

回到原始示例，其中 range 采用 1e6，结果如下:

(map inc 
    (map inc 
         (<... rougly 1e6 nested lazy sequences here ...>
            (map inc (0 0))) ...)

实现这一点将消耗大约1e6个堆栈帧，这肯定会导致堆栈溢出。

如果 mapv 不涉及惰性，并且 acc 立即实现，因此示例的结果将是 [1000000 1000000] 就在 reduce 完成之后。