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

当它找到键时,它返回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

编译器/解释器如何知道当密钥与k匹配时,它可以返回它？

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

回报 Just 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..].