Is using fold less efficient than standard recursion

Question

I'm going through the Learn You a Haskell book right now and I'm curious about how this particular example works. The book first demonstrates an implementation of findKey using traditional recursion:

findKey :: (Eq k) => k -> [(k,v)] -> Maybe v  
findKey key [] = Nothing  
findKey key ((k,v):xs) = if key == k  
                            then Just v  
                            else findKey key xs  

The book then follows up with a shorter implementation using foldr

findKey :: (Eq k) => k -> [(k,v)] -> Maybe v  
findKey key = foldr (\(k,v) acc -> if key == k then Just v else acc) Nothing  

With the standard recursion, the function should immediately return once it hits the first element with the provided key. If I understand the foldr implementation correctly, it will iterate over the entire list every time, even if it matched the first element it came across. That doesn't seem like a very efficient way to handle the problem.

Is there something I'm not getting about how the foldr implementation works? Or is there some kind of magic within Haskell that makes this implementation not quite as inefficient as I think it is?

Answer 1

1. foldr is written using standard recursion.

2. The recursive call to foldr is hidden inside of acc. If your code doesn't use acc, it will never be computed (because Haskell is lazy). So the foldr version is efficient and will also return early.

Here's an example demonstrating this:

Prelude> foldr (\x z -> "done") "acc" [0 ..]
"done"

This expression returns "done" immediately, even though the input list is infinitely long.

---

If foldr is defined as:

foldr f z (x : xs) = f x (foldr f z xs)
foldr _ z [] = z

, then evaluation goes via

f x (foldr f z xs)
    where
    f = \x z -> "done"
    x = 0
    z = "acc"
    xs = ...  -- unevaluated, but is [1 ..]

which is

(\x z -> "done") 0 (foldr (\x z -> "done") "acc" [1 ..])

which turns into "done" because the first function doesn't use z, so the recursive call is never needed.