7

Learn You a Haskell talks about foldl' as an alternative to foldl because foldl is prone to stack overflows.

  • According to LYAH, foldl (+) 0 (replicate 1000000 1) should stack overflow, but it doesn't on my machine. Why not? Even if I increase that number to 10 million it doesn't overflow. It just takes up a lot of memory until my OS X computer becomes unusable and I have to reboot it.
  • In what cases should I use foldl instead of foldl'? In my experience foldl' "just works" whereas foldl can essentially crash my computer (see above).
  • I don't understand why there is nothing similar for foldr. Why can't foldr stack overflow and why is there no foldr'?
stackoverflowuser
  • 1,157
  • 9
  • 18
  • possible duplicate of [Left and Right Folding over an Infinite list](http://stackoverflow.com/questions/7396978/left-and-right-folding-over-an-infinite-list) – Frerich Raabe Feb 12 '15 at 16:08
  • Answers to your second and third questions await you at https://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl' – jub0bs Feb 12 '15 at 16:09
  • The precise point at which your computer will hit a stackoverflow or run out of memory is dependent on your operating system, what other programs you're running, and your physical hardware. A raspberry pi will run out of RAM sooner than graphics rendering computer (which may have >100GB of RAM), for example. Your OS might also use swap in a particular way to manage programs requesting more memory. – bheklilr Feb 12 '15 at 16:09
  • Quick and dirty answers assumptions: 1. Not sure, did you have any optimizations on? 2. Always use foldl'! it's a rule of thumb. 3. foldr is lazy (it can work on infinite lists btw), so IIRC it doesn't even have an accumulator to be strict in the first place (it's not tail recursive). – MasterMastic Feb 12 '15 at 16:10
  • There are also plenty of resources on the differences between left folds and right folds in Haskell, including [many questions on SO already](http://stackoverflow.com/search?q=%5Bhaskell%5D+foldr+foldl). – bheklilr Feb 12 '15 at 16:10
  • "Why can't foldr stack overflow" - it can! "why is there no foldr'?" - because foldr' would be *more* likely to overflow than foldr, not less. – Jonathan Cast Feb 13 '15 at 18:25

2 Answers2

12

It doesn't crash with stack overflow because the stack is now infinite by default. That is, the default GHC runtime behavior is to allow the stack to grow indefinitely -- there's no bound which can trigger a stack overflow error.

https://ghc.haskell.org/trac/ghc/ticket/8189

Here is a description how it works:

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.

chi
  • 111,837
  • 3
  • 133
  • 218
Yuras
  • 13,856
  • 1
  • 45
  • 58
4

Why can't foldr stack overflow and why is there no foldr'?

Well, foldr is not tail recursive, i.e. it does not directly call upon itself:

foldr f a (x:xs) = f x (foldr f a xs)

After foldr is reduced, the control passes to the user-provided f. Therefore, there's no need to have a foldr' that forces the arguments before passing them to f: if that's wanted, the caller can just pass a strict f (e.g. exploiting bang patterns or seq).

Whether it does overflow the stack depends on what f does. For instance,

f x y = x

will cause the list to be accessed only in its first element. On the contrary,

f x y = seq y x

could cause a stack overflow (or an memory-intensive behavior). Instead,

f x y = x+1 : y

will cause the output list to be produced lazily, similarly to map (+1) xs, without any nasty surprise.

As @dfeuer points out, there exists Data.Foldable.foldr' which operates on any Foldable as a strict right fold. On lists, that is pretty much redundant, as discussed above. On other Foldable types, it can instead be meaningful.

chi
  • 111,837
  • 3
  • 133
  • 218
  • 2
    It might be worth pointing out that there *is* a `foldr'`. It's just in `Data.Foldable` rather than `Data.List`, because it's pretty much completely useless for lists. – dfeuer Feb 12 '15 at 17:23
  • Put another way, the reason why `foldr'` is almost useless on lists is that they are singly linked from the beginning, and you have to recurse to the end just to find the element to start folding at. So for a long list you end up using a lot of stack or heap anyhow. – Ørjan Johansen Feb 13 '15 at 00:26