Why do these folds stop at the head/tail?

Question

I'm reading learnyouahaskell.com and currently investigating folds. In the book there are these examples:

maximum' :: (Ord a) => [a] -> a  
maximum' = foldr1 (\x acc -> if x > acc then x else acc)  

reverse' :: [a] -> [a]  
reverse' = foldl (\acc x -> x : acc) []  

product' :: (Num a) => [a] -> a  
product' = foldr1 (*)  

filter' :: (a -> Bool) -> [a] -> [a]  
filter' p = foldr (\x acc -> if p x then x : acc else acc) []  

head' :: [a] -> a  
head' = foldr1 (\x _ -> x)  

last' :: [a] -> a  
last' = foldl1 (\_ x -> x) 

I understand all of them except head' and tail'.

It is my understanding that the binary function should be applied to the accumulator and each element in the list in turn, and thus go through all the list. Why does this stop to the head (or tail, respectively)?

I understand _ (underscore) means "whatever" or "I don't care" but how does that stop going through all the list?

Answer 1

A foldr combines two items - the current "running total" sort of item, and the new item.

(\x _ -> x) takes the new item and discards it, retaining the original, so all of the remaining items are ignored.

Let's expand it:

foldr1 (\x _ -> x) [1..100000]
= (\x _ -> x) 1 (foldr (\x _ -> x) [2..100000])
= 1

Since the (foldr (\x _ -> x) [2..100000]) term isn't needed, it isn't evaluated (that's lazy evaluation in action, or rather inaction), so this runs fast.

---

With (\_ x -> x), the new item is taken and the old one is ignored - this keeps happening until the end of the list, so you get the last element. It doesn't avoid the other ones, it just forgets them all except the last.

A more human-readable name of (\_ x -> x) would refer to the fact that it ignores its first argument and returns its second one. Let's call it secondArg.

foldl1 (\_ x -> x) [1..4]
= let secondArg = (\_ x -> x) in foldl secondArg 1 [2..4]
= foldl (1 `secondArg` 2) [3..4] 
= foldl ((1 `secondArg` 2) `secondArg` 3) [4]
= foldl (((1 `secondArg` 2) `secondArg` 3) `secondArg` 4) []
= (((1 `secondArg` 2) `secondArg` 3) `secondArg` 4)
= 4

Answer 2

Let's have a look at the definition of foldr1 first:

foldr1 :: (a -> a -> a) -> [a]       -> a
foldr1    f                [x]       =  x
foldr1    f                (x : xs)  =  f x (foldr1 f xs)

Then, consider a call of your function head',

head' :: [a] -> a  
head' =  foldr1 (\x _ -> x)

to a list, say, [2, 3, 5]:

head' [2, 3, 5]

Now, filling in the right hand-side of head' gives

foldr1 (\x _ -> x) [2, 3, 5]

Recall that [2, 3, 5] is syntactic sugar for (2 : 3 : 5 : []). So, the second case of the definition of foldr1 applies and we yield

(\x _ -> x) 2 (foldr1 (\x _ -> x) (3 : 5 : [])

Now, reducing the applications results in 2 getting bound to x and foldr1 (\x _ -> x) (3 : 5 : []) getting bound to the ignored parameter _. What is left is the right-hand side of the lambda-abstraction with x replaced by 2:

2

Note that lazy evaluation makes that the ignored argument foldr1 (\x _ -> x) (3 : 5 : []) is left unevaluated and so—and this hopefully answers your question—the recursion stops before we have processed the remainder of the list.