Why does foldl use so much memory on a large list in Haskell, and when should I use foldl' or foldr?

foldl is lazy in its accumulator. It walks the list and, instead of adding, builds the unevaluated expression ((((0 + 1) + 2) + 3) + ...) as a chain of thunks, one per element. Nothing forces any addition until the final result is demanded, so ten million suspended additions sit on the heap first, each costing a few machine words. Only then is the chain evaluated, and evaluating such a deeply nested expression needs a correspondingly deep stack.

The function is tail recursive, but in a lazy language that does not give you constant space; what matters is when the accumulator is evaluated.

foldl' from Data.List forces the accumulator at every step before continuing, so the running total is always a plain number and the fold runs in constant space: foldl' (+) 0 [1..10000000] gives 50000005000000 without the memory growth.

You see the problem in GHCi because it does not optimise. When compiling with -O, GHC's strictness analysis often notices that the accumulator is always needed and makes simple cases like this one strict by itself, but that is an optimisation you should not rely on. Writing foldl' states the intent.

foldr (+) 0 xs expands to 1 + (2 + (3 + ...)). Since + needs both operands before it can produce anything, the whole list has to be traversed with every pending addition waiting on the stack, which is no improvement for a sum.

foldr is the right choice when the combining function can produce part of its result without looking at the rest. foldr (\x acc -> 2 * x : acc) [] xs yields the first cons cell immediately, so take 5 of it works even on the infinite list [1..] and gives [2,4,6,8,10]. foldr (&&) True stops at the first False. A left fold can do neither; it must reach the end of the list.

One caveat about foldl': it evaluates the accumulator only to weak head normal form, meaning up to the outermost constructor. If the accumulator is a tuple, as in foldl' (\(s, n) x -> (s + x, n + 1)) (0, 0) xs for computing a mean, the pair itself is forced at each step but the two fields inside it are still growing chains of thunks.

Force the fields as well, either with bang patterns, \(!s, !n) x -> (s + x, n + 1) (the BangPatterns extension), or by using an accumulator type with strict fields such as data Acc = Acc !Double !Int.

The rule of thumb that results: use foldl' when reducing a list to a single strict value such as a sum, a count, a maximum or a Map built by insertion; use foldr when building a lazy structure or when the operation can stop early; and treat plain foldl as something you almost never want.

To see what a program is really doing, compile with -rtsopts and run it with +RTS -s. The summary prints total allocation and maximum residency, and a strict fold over ten million numbers should show a maximum residency of kilobytes rather than hundreds of megabytes.