haskell - 使用折叠的效率低于标准递归

Question

我现在正在阅读《Learn You a Haskell》一书，我很好奇这个特定示例的工作原理。本书首先演示了 findKey 的实现。使用传统递归:

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  

本书随后使用 foldr 进行了更短的实现。

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

使用标准递归，一旦使用提供的键命中第一个元素，函数应该立即返回。如果我理解 foldr正确实现，它每次都会遍历整个列表，即使它匹配它遇到的第一个元素。这似乎不是处理问题的一种非常有效的方法。

关于 foldr实现工作？或者 Haskell 中是否有某种魔法使这个实现不像我想象的那么低效？

Answer 1

foldr是使用标准递归编写的。

对 foldr 的递归调用隐藏在 acc 中.如果您的代码不使用 acc ，它永远不会被计算(因为 Haskell 是惰性的)。所以foldr版本是高效的，也会提前返回。

下面是一个例子来证明这一点:

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

此表达式返回 "done"立即，即使输入列表是无限长的。

如果 foldr定义为:

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

，然后评估通过

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

这是

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

变成 "done"因为第一个函数没有使用 z ，因此从不需要递归调用。