foldl' better than foldl

In Haskell the foldl’ function defined in the module Data.List is better than foldl because that does not use a thunk . A thunked expression requires an internal stack. As an expression can grow infinitely large, the runtime imposes a limit on the size of this stack. As the simple example below shows that given a large enough input the stack will overflow.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Prelude> foldr (+) 0 \[1..100\]  
5050  
Prelude> foldl (+) 0 \[1..100\]  
5050  
Prelude> foldl (+) 0 \[1..1000\]  
500500  
Prelude> foldl (+) 0 \[1..10000\]  
50005000  
Prelude> foldl (+) 0 \[1..100000\]  
5000050000  
Prelude> foldl (+) 0 \[1..1000000\]  
\*\*\* Exception: stack overflow

On the other hand, foldl’ while similar to foldl does not build up on thunks and in real world programs is probably more useful.

1
2
3
4
5
6
7
Prelude> :module +Data.List  
Prelude Data.List> foldl' (+) 0 \[1..1000000\]  
500000500000  
Prelude Data.List> foldl' (+) 0 \[1..1000000\]  
500000500000  
Prelude Data.List> foldl' (+) 0 \[1..10000000\]  
50000005000000