我现在正在阅读《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 中是否有某种魔法使这个实现不像我想象的那么低效?
最佳答案
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
,因此从不需要递归调用。
关于haskell - 使用折叠的效率低于标准递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38413219/