使用折叠比标准递归效率低

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

1. foldr 是使用标准递归编写的.

2. 递归调用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,所以永远不需要递归调用.