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.

Answer 2

1. No, when the function \(k,v) acc -> ... is called by foldr, the recursive call to foldr is supplied as the second argument (i.e. acc). So, keeping in mind that Haskell is lazy, if acc isn't used (i.e. if the if condition is true), the recursive call does not happen and the traversal stops.
2. Both work fine with infinite lists.