Why doesn't product [0..] evaluate to 0 "instantly"?

Question

I am trying to understand laziness. Because 0 multiplied with any number is 0, shouldn't product [0..] evaluate to 0? I tried also foldl (*) 1 [0..], and to define my own product as

myProduct 0 _ = 0
myProduct _ 0 = 0
myProduct a b = a*b

Why doesn't the fold stop as soon as a 0 is found?

Answer 1

Because the multiply operator doesn't know it's getting chained, and the fold function doesn't know the multiply operator's particular behaviour for any argument. With that combination, it needs to exhaust the list to finish the fold. In fact, for this reason foldl doesn't work at all on infinite lists. foldr does, because it can expand the function from the head of the list.

foldl (*) 1 [0..] -> (((..(((1*0)*1)*2)*3....)*inf

The outermost multiplication in the foldl case can never be found, because the list is infinite. It therefore cannot follow the chain to conclude the result is zero. It can, and does, calculate the product along the list, and that product happens to stay zero, but it will not terminate. If you use scanl instead you can see these intermediate products.

foldr (*) 1 [0..] -> 0*(1*(2*(3*((...((inf*1)))...)))

The outermost multiplication in the foldr case is found immediately, because the rest of the list is in fact left as a lazy thunk. It only runs one step:

foldr (*) 1 [0..] -> 0*(foldr (*) 1 [1..])

So because your custom multiplication operator myProduct is not strict in the second argument if the first argument is zero, foldr myProduct 1 [0..] can terminate.

As a side note, the prelude product function is restricted to finite lists (and may be implemented with foldl). Even if it used foldr, it probably would not shortcut because the standard multiply operator is strict; doing otherwise would be computationally expensive in the common case where the products are neither zero nor chained.

-- sum and product compute the sum or product of a finite list of numbers.

sum, product     :: (Num a) => [a] -> a
sum              =  foldl (+) 0  
product          =  foldl (*) 1

In addition, there's a reason it does not use foldr; as we could see in the expansions and scanl function, the left folds can compute as they consume the list. The right fold, if the operator does not shortcut, needs to build an expression as large as the list itself to even begin computation. This difference is because it's the innermost expression that starts the computation in the strict case, but the outermost expression that produces the result, allowing the lazy case. Lazy vs. non-strict in the Haskell wiki might explain better than I can, and even mentions that pattern matching, which you used to describe the shortcut in myProduct, can be strict.

Answer 2

If you switch the first two lines:

myProduct _ 0 = 0
myProduct 0 _ = 0
myProduct a b = a*b

the second argument will always be evaluated before the first one and the infinite foldr won't work anymore.

Since its impossible to define a myProduct that works lazily for both arguments (not evaluating the second if the first is 0 and not evaluating the first if the second is 0) maybe we are better off with having * always evaluate both its arguments.