haskell - 为什么这个 Haskell 代码可以成功地处理无限列表？

Question

我有一些 Haskell 代码可以在无限列表上正常工作，但我不明白为什么它可以成功。 (我修改了我的原始代码 - 没有处理无限列表 - 以合并来自其他在线代码的内容，突然我发现它有效但不知道为什么)。

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldr step False list
   where
      step item acc = p item || acc

我对 foldr 的理解是它将遍历列表中的每个项目(也许这种理解是不完整的)。如果是这样，那么“step”函数的措辞应该无关紧要......代码应该无法处理无限循环。

但是，以下工作:

*Main Data.List> myAny even [1..]
True

请帮助我理解:为什么？

Answer 1

让我们对 Haskell 将如何评估您的表达式进行一些跟踪。在每一行上用 equals 替换 equals，表达式很快就会计算为 True:

myAny even [1..]
foldr step False [1..]
step 1 (foldr step False [2..])
even 1 || (foldr step False [2..])
False  || (foldr step False [2..])
foldr step False [2..]
step 2 (foldr step False [3..])
even 2 || (foldr step False [3..])
True   || (foldr step false [3..])
True

这是因为 acc作为未评估的 thunk(惰性评估)传递，但也因为 ||函数在其 中是严格的第一个 争论。

所以这终止:

True || and (repeat True)

但这不会:

and (repeat True) || True

看||的定义看看为什么会这样:

True  || _ =  True
False || x =  x