递归与折叠效率

Question

在众所周知的Haskell tutorial中，在关联列表中按键查找值的函数首先定义如下：

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

然而，作者随后认为这种类型的 "textbook recursion" 最好使用折叠来实现：

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

我发现这令人困惑。我说得对吗：

基于foldr的函数总是会在产生结果之前遍历整个列表，而第一个会在发现后立即停止？
因此，第一个函数将适用于无限列表，而第二个则不能？

在我看来 really 等效定义将使用 scanr 代替，并从中获取第一个不是 Nothing 的结果. (?)

Answer 1

不，当 foldr 调用函数 \(k,v) acc -> ... 时，对 foldr 的递归调用作为第二个参数提供（即 acc）。因此，请记住 Haskell 是惰性的，如果未使用 acc（即如果 if 条件为真），则不会发生递归调用并且遍历停止。
两者都适用于无限列表。

Answer 2

foldr 定义为

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

所以如果 cons 不使用它的第二个参数，则不需要它的值。由于 Haskell 是按需调用的，因此不会评估不需要的值。

所以不，两种公式都具有相同的惰性特征。

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)

因此，如果 key == k 成立，则不会触发递归调用（以找出 r 的值）。

递归与折叠效率

Recursion vs fold efficiency

recursion

haskell

fold