foldl behaviour on infinite lists

4
votes

What I've understood about foldl vs. foldr on lists :

If we right fold [0,1,2,3] with a function s and a starting accumulator a, we are doing this :

f 0 (f 1 (f 2 (f 3 a)))

If we left fold [0,1,2,3] with a function s and a starting accumulator a, we are doing this :

f (f (f (f 0 a) 1) 2) 3)

Given : 

elem_r :: (Eq a) => a -> [a] -> Bool
elem_r y ys = foldr (\x acc -> if x == y then True else acc) False ys

and

elem_l :: (Eq a) => a -> [a] -> Bool
elem_l y ys = foldl (\acc x -> if x == y then True else acc) False ys

It seems clear to me that elem_r 3 [0..] will compute what it really must, and return True as soon as value 3 is reached.

f 0 (f 1 (f 2 (f 3 (...)))

Whereas elem_l 3 [0..] need to evaluate the complete nested functions application before returning a result.

f (f (f (f (f 0 3) 1) 2) 3) ...)

Now my question is :

In the specific case of elem_l 0 [0..] The searched element is the first item of the list.

In this expression : f (f (f (f (f 0 0) 1) 2) 3) ...) The innermost function (f 0 0) can immediately be evaluated to "True". Why does Haskell continue to evaluate the rest of nested functions?

2
haskellfunctional-programmingfold
if x == y then True else acc could be a bit tidier as acc || x == y, imho. - Bartek Banachewicz
Recommended reading: haskell.org/haskellwiki/Foldr_Foldl_Foldl' - jub0bs
@BartekBanachewicz you meant x == y || acc, undoubtedly. - Will Ness

2 Answers

7
votes

Even if you "immediately" reduce f 0 0 to True, that does not help. You still have all the surrounding occurrences of f to reduce ...

1
votes

Because f (f (f (f (f 0 0) 1) 2) 3) ...) is not right. The final parenthesis and the first f are mismatched, and the initial argument is all wrong. It really is

(f ... (f (f (f (f False 0) 1) 2) 3) ...)

so after foldl has finished building this expression (which is, never), we have to get through an infinite amount of nested expressions, evaluating them first, before we get to the innermost expression, which gets evaluated last (because f stops on 0). Or in this case, never.

And the other test, searching for 3, would stop earlier, on (f (f (f (f False 0) 1) 2) 3), because now f stops on 3; but still it'd have to go through the infinite amount of nested expressions first, after that infinite nested expression is built.