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.
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.