关于folds和stack overflows的问题
Questions about folds and stack overflows
向您学习 Haskell 谈论 foldl' 作为 foldl 的替代方案，因为 foldl 容易出现堆栈溢出.
- 根据 LYAH 的说法，
foldl (+) 0 (replicate 1000000 1) 应该堆栈溢出，但在我的机器上没有。 为什么不呢？ 即使我将该数字增加到 1000 万，它也不会溢出。它占用了大量内存，直到我的 OS X 计算机变得无法使用，我不得不重新启动它。
- 在什么情况下我应该使用
foldl而不是foldl'？根据我的经验，foldl' "just works" 而 foldl 基本上会使我的计算机崩溃（见上文）。
- 我不明白为什么
foldr 没有类似的东西。为什么foldr不能堆栈溢出，为什么没有foldr'？
它不会因堆栈溢出而崩溃，因为堆栈现在默认是无限的。也就是说，默认的 GHC 运行时行为是允许堆栈无限增长——没有可以触发堆栈溢出错误的界限。
https://ghc.haskell.org/trac/ghc/ticket/8189
这里描述了它是如何工作的：
Thread stacks (including the main thread's stack) live on the heap. As
the stack grows, new stack chunks are added as required; if the stack
shrinks again, these extra stack chunks are reclaimed by the garbage
collector. The default initial stack size is deliberately small, in
order to keep the time and space overhead for thread creation to a
minimum, and to make it practical to spawn threads for even tiny
pieces of work.
Why can't foldr stack overflow and why is there no foldr'?
嗯，foldr 不是尾递归，即它不直接调用自身：
foldr f a (x:xs) = f x (foldr f a xs)
减少foldr后，控制传递给用户提供的f。因此，在将参数传递给 f 之前不需要 foldr' 来强制参数：如果需要，调用者只需传递一个严格的 f （例如利用 bang 模式或 seq).
是否溢出堆栈取决于f的作用。例如，
f x y = x
将导致仅在其第一个元素中访问列表。相反，
f x y = seq y x
可能导致堆栈溢出（或内存密集型行为）。相反，
f x y = x+1 : y
将延迟生成输出列表，类似于 map (+1) xs，没有任何令人讨厌的惊喜。
正如@dfeuer 指出的那样，存在 Data.Foldable.foldr' 对任何 Foldable 作为严格的右折叠操作。如上所述，在列表中，这几乎是多余的。在其他 Foldable 类型上，它可能是有意义的。
向您学习 Haskell 谈论 foldl' 作为 foldl 的替代方案，因为 foldl 容易出现堆栈溢出.
- 根据 LYAH 的说法，
foldl (+) 0 (replicate 1000000 1)应该堆栈溢出，但在我的机器上没有。 为什么不呢？ 即使我将该数字增加到 1000 万，它也不会溢出。它占用了大量内存，直到我的 OS X 计算机变得无法使用，我不得不重新启动它。 - 在什么情况下我应该使用
foldl而不是foldl'？根据我的经验，foldl'"just works" 而foldl基本上会使我的计算机崩溃（见上文）。 - 我不明白为什么
foldr没有类似的东西。为什么foldr不能堆栈溢出，为什么没有foldr'？
它不会因堆栈溢出而崩溃，因为堆栈现在默认是无限的。也就是说，默认的 GHC 运行时行为是允许堆栈无限增长——没有可以触发堆栈溢出错误的界限。
https://ghc.haskell.org/trac/ghc/ticket/8189
这里描述了它是如何工作的：
Thread stacks (including the main thread's stack) live on the heap. As the stack grows, new stack chunks are added as required; if the stack shrinks again, these extra stack chunks are reclaimed by the garbage collector. The default initial stack size is deliberately small, in order to keep the time and space overhead for thread creation to a minimum, and to make it practical to spawn threads for even tiny pieces of work.
Why can't foldr stack overflow and why is there no foldr'?
嗯，foldr 不是尾递归，即它不直接调用自身：
foldr f a (x:xs) = f x (foldr f a xs)
减少foldr后，控制传递给用户提供的f。因此，在将参数传递给 f 之前不需要 foldr' 来强制参数：如果需要，调用者只需传递一个严格的 f （例如利用 bang 模式或 seq).
是否溢出堆栈取决于f的作用。例如，
f x y = x
将导致仅在其第一个元素中访问列表。相反，
f x y = seq y x
可能导致堆栈溢出（或内存密集型行为）。相反，
f x y = x+1 : y
将延迟生成输出列表，类似于 map (+1) xs，没有任何令人讨厌的惊喜。
正如@dfeuer 指出的那样，存在 Data.Foldable.foldr' 对任何 Foldable 作为严格的右折叠操作。如上所述，在列表中，这几乎是多余的。在其他 Foldable 类型上，它可能是有意义的。