减少和地图上的累加器产生堆栈溢出

Question

为什么我需要在这一段代码与mapv更换map防止堆栈溢出：

#!/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))) 

所以你并不急于与inc映射acc，但只将懒惰的序列放入另一个，这将在事后实现。

再回到其中range1e6取原始示例中，结果将是以下内容：

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

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

在mapv的情况下，不涉及懒惰，acc立即实现，因此您的示例的结果将在reduce完成后立即为[1000000 1000000]。