Recursion vs fold efficiency

Question

In the well-known Haskell tutorial, the function that finds a value-by-key in an associative list is first defined like that:

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

However, the author then argues that this type of "textbook recursion" should better be implemented using a fold:

findKey key = foldr (\(k,v) acc -> if key == k then Just v else acc) Nothing  

I found that confusing. Am I right that:

1. The foldr-based function will always traverse the whole list before producing a result, whereas the first one will immediately stop upon discovery?
2. As a consequence, the first function will work on an infinite list, whereas the second one won't?

It seems to me that the really equivalent definition would use a scanr instead and from that, take the first result that isn't Nothing. (?)

Answer 1

foldr is defined such that

foldr cons z (x:xs) = cons x (foldr cons z xs)

so if cons doesn't use its second argument, its value isn't needed. Since Haskell is call-by-need, unneeded values are not evaluated.

So no, both formulations have the same laziness characteristics.

findKey key (x:xs)
  = foldr (\(k,v) r -> if key == k then Just v else r) Nothing (x:xs)
  = (\(k,v) r -> if key == k then Just v else r) x
      (foldr (\(k,v) r -> if key == k then Just v else r) Nothing xs)
  = case x of (k,v) -> if key == k then Just v else 
      (foldr (\(k,v) r -> if key == k then Just v else r) Nothing xs)

and so if key == k holds, the recursive call (to find out the r's value) isn't triggered.