haskell - 为什么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

当它找到 key 时，它返回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

编译器/解释器如何知道当key匹配k时，它可以返回它？

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

返回只有1

当它找到 key == k 时，它返回 Just v。为什么递归会停在那里，允许我们用无限关联列表做这样的事情？

Answer 1

因为传递给 foldr 的函数并不总是评估 acc 参数，即它在那个参数中是惰性的。

例如，

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

将返回 "one" 甚至不尝试评估 error 表达式。

此外，foldr 根据定义满足:

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

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

在您的示例中，当且仅当第一个参数不是想要的关联时，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 看起来是多余的，因为该函数在两个分支中返回相同的内容。 然而，这需要评估 acc 打破无限列表中的代码。

你可能想尝试的另一件事

foldr (:) [] [0..]

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

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

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