So let’s contrast the two examples given back-to-back in the book:
head' :: [a] -> a
head' = foldr1 (\x _ -> x)
last' :: [a] -> a
last' = foldl1 (\_ x -> x)
these two are really the exact same implementation with one using foldl1 and one using foldr1 (the lambdas look different, but that’s just because foldl1 and foldr1 take their parameters in different orders).
x parameter is the “element” taken from the list, while the
_ is the stateful accumulator that gets iteratively updated. Now this is a very unusual usage of folds, since you’re throwing away the accumulated value, and typically folds are used specifically for the accumulated value.
So if I take the
head' function, and apply it to
[1,2,3,4], it’s going to produce
f 1 (f 2 (f 3 4)), with
f = \x _ -> x. Now if Haskell were a strict language, it would start with
f 3 4 = 3, then evaluate
f 2 3 = 2, and then finally evaluate
f 1 2 = 1, your final answer. So it does “start from the right,” but at each step it just throws away everything it calculated so far. The final invocation after it reached the left of the list keeps the head and throws out the rest.
But Haskell’s not strict, it’s lazy. That means that
f 1 (f 2 (f 3 4)) looks at the definition of
f = \x _ -> x, and it knows that it doesn’t need to bother evaluating
f 2 (f 3 4) in order to give you your answer, you can just return the
1 straight away.
If we look at the
last' function, and apply it to
[1,2,3,4], you’re going to end up with
f (f (f 1 2) 3) 4. Again, if Haskell were strict, it would need to start with that
f 1 2, which would be the left side of the list, which is why it kind of works to think of it as left-to-right. I’ll leave it as an exercise to the reader why the
last' implementation works, and what the laziness of Haskell means in this case.
Does that help? Let us know if anything is still unclear!