Why does foldright work for infinite lists?

3
votes

I was under the impression that foldright starts from the end of a list and works backwards (this is how I imagined what right-associative means). So I am confused that the following works for infinite lists.

I have a function find:

find :: (a -> Bool) -> List a -> Optional a
find p = foldRight (\c a -> if p c then Full c else a) Empty

Note that the following work:

>> find (const True) infinity
Full 0

I did do some searching and found this post: How do you know when to use fold-left and when to use fold-right?

Unfortunately, the accepted answer is not particularly helpful because the example for right-associative operations is:

A x (B x (C x D))

Which still means it needs to execute the right-most thing first.

I was wondering if anyone can clear this up for me, thanks.

3
haskellfunctional-programminglanguage-agnosticfold
Haskell is lazy, so the second parameter to A is only evaluated if necessary. – 4castle
You say, "The example is A x (B x (C x D)) which still means it needs to execute the right-most thing first.". (Here I assume by "right-most thing" you mean D, or possibly C x D.) This appears to be the fundamental mistake you've made in your reasoning. – Daniel Wagner
I suspect that you're confusing associativity (which applies to operators) with order of evaluation (which applies to their operands). In A x (B x (C x D)), you can evaluate A before B x (C x D), and if you know that A provides the answer you never need to evaluate B x (C x D). (Consider for example 0 * (123456789 * (890123456 * 789123456)), which you can immediately see is 0.) – molbdnilo

3 Answers

12
votes

Let's start with a function:

>>> let check x y = if x > 10 then x else y
>>> check 100 5
100
>>> check 0 5
5

check takes two arguments, but might not use its second argument. Since haskell is lazy, this means that the second argument may never be evaluated:

>>> check 20 (error "fire the missles!")
20

This laziness lets us skip a possibly infinite amount of work:

>>> check 30 (sum [1..])
30

Now let's step through foldr check 0 [0..] using equational reasoning:

foldr check 0 [0..]
= check 0 (foldr check 0 [1..]) -- by def'n of foldr
= foldr check 0 [1..] -- by def'n of check
= check 1 (foldr check 0 [2..]) -- by def'n of foldr
= foldr check 0 [2..] -- by def'n of check
-- ...
= foldr check 0 [10..]
= check 10 (foldr check 0 [11..]) -- by def'n of foldr
= foldr check 0 [11..] -- by def'n of check
= check 11 (foldr check 0 [12..]) -- by def'n of foldr
= 11 -- by def'n of check

Note how laziness forces us to evaluate from the top-down, seeing how (and if) the outer-most function call uses its arguments, rather than from the bottom-up (evaluating all arguments before passing them to a function), as strict languages do.

4
votes

It works because of lazy evaluation. Let’s take a really simple example.

import Data.Char (toUpper)

main :: IO ()
main = interact (foldr capitalized []) where
  capitalized :: Char -> String -> String
  capitalized x xs = (toUpper x):xs

Run this program interactively and see what happens. The input is an infinite (or at least indefinite) list of characters read from standard input.

This works because each element of the output list gets produced lazily, when it is needed. So the tail is not produced first: it’s only computed if and when it’s needed. Until then, it’s deferred, and we can use the partial results. The partial result for 'h':xs is 'H':(foldr capitalized [] xs). The partial result for 'h':'e':'l':'l':'o':',':' ':'w':'o':'r':'l':'d':'!':'\n':xs is a string we can output before we proceed to the tail xs.

Now see what happens if you try this with foldl.

This works for any data structure that generates a useful prefix. For a reduction operation that produces a single value, and no useful intermediate results, a strict left fold (Data.List.foldl') is usually the better choice.

1
votes

Your objection proves too much. If it was valid, no infinite lists at all would be possible! An infinite list is constructed using (:). Its second argument, the tail of the list, is also an infinite list, and would have to be evaluated first. This recursively doesn't get us anywhere.