Skip to the content ForoHackers
Log inJoin

foldr vs foldl: what laziness does to your stack (and your infinite lists)

Functional programmingHaskell
#1141 · lambda_llama · · Report

New year, new attempt to convert one (1) person to Haskell. Today's weapon: the difference between foldr and foldl.

foldr (&&) True (repeat False)   -- False, instantly
foldl (&&) True (repeat False)   -- never returns

foldr f z (x:xs) = f x (foldr f z xs). If f does not need its second argument (False && _ is False), the rest of the list is never touched, so even an infinite list is fine.

foldl f z (x:xs) = foldl f (f z x) xs. It walks the whole spine before it can return anything, so on an infinite list it just walks forever.

The other classic:

foldl (+) 0 [1..10000000]

Lazy foldl builds ten million nested thunks (((0+1)+2)+3)... and only evaluates them at the end. With optimisation GHC's strictness analysis often rescues you, but you should not depend on that. Use foldl' from Data.List, which forces the accumulator at each step.

Rule of thumb I teach: foldr when you build a lazy structure or can short-circuit, foldl' when you reduce to a single strict value. Plain foldl is almost never what you want.

Yes, I will mention monads in the replies if nobody else does.

#1887 · monad_tutorial_no_47 · · Report

Monads were not mentioned, so I consider this a personal victory. Good post. One more thing for people arriving from other languages: foldr is not "the one that goes from the right" in any useful sense. It is the one that replaces (:) with f and [] with z. Once you see that, map, filter and ++ are all just folds.

#1888 · off_by_two · · Report

Small puzzle in the same spirit: what does take 3 (foldr (\x acc -> x : acc) [] [1..]) print, and why does it not hang? (Answer is the same reason as your && example, but people get stuck on it.)

#1889 · lambda_llama · · Report

It prints [1,2,3]: the lambda produces x : acc and acc is an unevaluated thunk until take asks for more. Laziness does the short-circuiting for you. Well asked.

Log in or join to reply.