haskell - 递归与折叠效率

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

然而，作者随后认为这种“教科书式递归”最好使用折叠来实现:

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

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

foldr -based 函数在产生结果之前总是会遍历整个列表，而第一个会在发现后立即停止？

因此，第一个函数将在无限列表上工作，而第二个则不会？

在我看来，真正等效的定义将使用 scanr取而代之的是，取第一个不是 Nothing 的结果. (?)

Answer 1

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 的值)不会被触发。