Learn Haskell — foldl vs foldr Link to heading

Today, let’s talk about fold patterns. In Haskell, there are two fold functions defined in Prelude

:t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

:t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

In case of a List, foldl starts with the left-most element whereas foldr starts with the right-most element. So what is the implication of this and how do we decided which one to use?

To better understand, let’s do a quick example. Let’s use foldl and foldr to implement length which returns the length of a given list of any type a.

lengthWithFoldl :: [a] -> Integer
lengthWithFoldl = foldl (\b _ -> b+1) 0

lengthWithFoldr :: [a] -> Integer
lengthWithFoldr = foldr (\_ b -> b+1) 0

Simple enough. Now, let’s try evaluating these two lines

lengthWithFoldl [0..100000000]
lengthWithFoldr [0..100000000]

Surprise? The two functions will crash with stack overflow!

ghci> lengthWithFoldl [0..100000000]
*** Exception: stack overflow
ghci> lengthWithFoldr [0..100000000]
*** Exception: stack overflow

So, what is going on? For the foldl case, here is the expression we are creating

((((((0 + 1) + 1) + 1) + 1) + 1) + 1) + ...

In Haskell, expressions are by default evaluated lazily, so (0+1) is not evaluated until the entire expression is prepared, at which point, stack overflows. On the other hand, with foldr case, we have

1 + (1 + (1 + (1 + ... + (1 + 0)))))

Here, the recursion must reach the final element first, at which point, stack overflows.

Solution Link to heading

So what do we do? There is a function seq which force-evaluates its first-parameter.

seq :: a -> b -> b

Using this, we can define a new foldl

foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl' _ z [] = z
foldl' f z (x:xs) = seq z' (foldl' f z' xs) where z' = f z x

lengthWithFoldl' :: [a] -> Integer
lengthWithFoldl' = foldl' (\b _ -> b+1) 0

Let’s now evaluate the same expression using the new function

ghci> lengthWithFoldl' [0..100000000]
100000001

Awesome! We can now evaluate the expression without stack overflow. In fact, this strict version of foldl is so common, Haskell provides this — though not in Prelude

ghci> import Data.List
ghci> :t foldl'
foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b

Functional programming offers a compelling approach to software development, with its emphasis on pure functions and immutable data. However, it’s not without its limitations. A proficient developer should have a broad understanding of various programming paradigms — including imperative, object-oriented, and functional — and possess the discernment to select the most suitable one for the task at hand.

Reference Link to heading

https://wiki.haskell.org/Foldr_Foldl_Foldl'