why foldl is not short circuiting with andFn function?

Question

My understanding is that foldl and foldr executes like :

foldl f a [1..30] => (f (f (f ... (f a 1) 2) 3) ... 30)

and

foldr f a [1..30] => (f 1 (f 2 (f 3 (f ....(f 30 a)))))..)

so.. foldr (&&) False (repeat False) can shortciruit as outermost f sees (&&) False ((&&) False (....)) sees first argument as false and does not need to evaluate the second argument (which is a large thunk).

so what happens with

andFn :: Bool -> Bool -> Bool
andFn _ False = False
andFn x True  = x

and

foldl andFn True (repeat False)  -- =>

-- (andFn (andFn ...(andFn True False) ... False) False)
--  ^^ outermost andFn

But this is taking forever.

I thought that outermost andFn would know that by pattern matching on second argument, the answer is False..

What else is happening here ?

Pros

Answer 1

There is a larger difference between foldr and foldl than the order of the arguments to andFn.

foldr f z (x:xs) = f x (foldr f z xs)
foldl f z (x:xs) = foldl f (f z x) xs

Notice how foldr immediately transfers control to f: if f is lazy it can avoid the computation of foldr f z xs.

Instead, foldl transfers control to... foldl: the function f will only start being used when the base case is reached

foldl f z [] = z      -- z contains the chained f's, which NOW get evaluated

Hence foldl f z infiniteList will always diverge, no matter what f is: the whole infiniteList needs to be completely iterated over before any real computation happens. (Off topic: this is why, even when it works, foldl often has horrible performance, and foldl' is more used in practice.)

In particular, the posted example

foldl andFn True (repeat False)  -- =>
-- (andFn (andFn ...(andFn True False) ... False) False)
--  ^^ outermost andFn

is partly wrong. The "outermost andFn" would actually be the last one, i.e. the one related to the last element in repeat False. But there is no such a beast.

Clipboard