为什么 foldr 适用于无限列表？

Question

这个函数可能适用于无限关联表，很容易找出原因：

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

当它找到密钥时，它 returns Just v，停止递归。现在看看另一个实现：

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

compiler/interpreter如何知道当key匹配k时，它可以return呢？

 *Main> findKey' 1 $ zip [1..] [1..]

returns Just 1

当它发现 key == k 时，它 return 就会 Just v。为什么递归到此为止，允许我们用无限关联列表做这样的事情？

Answer 1

因为传递给 foldr 的函数并不总是计算 acc 参数，即它在该参数中是惰性的。

例如，

(\(k,v) acc -> if 1 == k then Just v else acc) (1,"one") (error "here be dragons!")

将 return "one" 甚至不尝试计算 error 表达式。

此外，foldr 根据定义满足：

foldr f a (x:xs) = f x (foldr f a xs)

如果x:xs是无限的，但是f不使用它的第二个参数，那么foldr可以立即return。

在您的示例中，当且仅当第一个参数不是所需的关联时，f 才计算其第二个元素。这意味着关联列表只会被评估到足以找到 key 关联。

如果您想尝试，请试试这个：

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

case 看起来多余，因为函数 return 在两个分支中都是一样的。但是，这需要评估 acc 打破无限列表上的代码。

您可能想尝试的另一件事

foldr (:) [] [0..]

这基本上按原样重建了无限列表。

foldr (\x xs -> x*10 : xs) [] [0..]

这会将所有内容乘以 10，等同于 map (*10) [0..]。

Answer 2

foldr的非空情况可以定义为foldr f init (x:xs) = f x (foldr f init xs)。在您的例子中，f 是 (\(k,v) acc -> if key == k then Just v else acc)，因此 (k,v) 代表列表中的当前元素，acc 代表 (foldr f init xs)。即acc代表递归调用。在 then 的情况下，您不使用 acc，因此递归调用不会发生，因为 Haskell 是惰性的，这意味着直到（并且除非）使用参数才会被评估。

为什么 foldr 适用于无限列表？

Why foldr works on infinity list?

recursion

haskell

fold