Folds as repeated operator application

This is one of the most straightforward ways of thinking about folds on lists.

Remind yourself of the most common definition of a fold:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

I will make one change - instead of f, we will use the operator $\oplus$ (which signifies the same thing, simply infix). Therefore, we get:

foldr (⊕) v [] = v
foldr (⊕) v (x:xs) = x ⊕ (foldr f v xs)

Let’s apply this - in the most general case - to a finite list.

foldr (⊕) v [1, 2, 3, 4]

Using the definition of foldr, we get:

foldr (⊕) v [1, 2, 3, 4]
    =
1 ⊕ foldr (⊕) v [2, 3, 4]
    =
1 ⊕ (2 ⊕ foldr (⊕) v [3, 4])
    =
...
    =
1 ⊕ (2 ⊕ (3 ⊕ (4 ⊕ v)))

This is the idea of a fold as being repeated operator application. This metaphor applies mostly to lists (because we can use an infix operator), but can be tweaked for other recursive data structures.

However, this metaphor can obscure two related facts about folds.

First: Haskell is lazy. It is not necessarily true that all the parentheses will be calculated. For example:

any :: [Bool] -> Bool
any = foldr (||) False

This function returns true if any value in the list passed to it is True. Otherwise it returns false. But the operator (||) is lazy (it short-circuits):

any [False, True, False, False]
    !=
False || (True || (False || (False || False)))
-- Nope!       ^ Returns true here, the rest is not calculated

Instead we get to:

any [False, True, False, False]
    =
False || (True || foldr (||) False [False, False])
--             ^ Returns true here

Second: Folds work on infinite lists.

isFive :: [Int] -> Bool
isFive = foldr  False
  where f n b = (n == 5) || b
 
isFive [1..]
    =
1 `f` (2 `f` (3 `f` (4 `f` ... -- ??

Of course, isFive halts after 5. But say we run isFive [6..] - it will never return. Noticing that we can do folds on infinite instances of data structures is related to lazyness - but using this as a frame can obscure that.