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.

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.

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

Published by

Amit Bahree

This blog is my personal blog and while it does reflect my experiences in my professional life, this is just my thoughts. Most of the entries are technical though sometimes they can vary from the wacky to even political – however that is quite rare. Quite often, I have been asked what’s up with the “gibberish” and the funny title of the blog? Some people even going the extra step to say that, this is a virus that infected their system (ahem) well. [:D] It actually is quite simple, and if you have still not figured out then check out this link – whats in a name?

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.