为什么这个Haskell代码能够成功地使用无限列表？

Question

我有一些Haskell代码是不会无限名单上正常工作,但我不明白为什么它可以做得很成功.(我修改了我原来的代码 - 没有处理无限列表 - 在网上加入其他代码的东西,突然间我发现它有效,但不知道为什么).

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

我对foldr的理解是它将遍历列表中的每个项目(也许这种理解是不完整的).如果是这样,那么"步"函数的表达方式无关紧要......代码应该无法处理无限循环.

但是,以下工作:

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

请帮我理解:为什么？

Answer 1

让我们来看看Haskell如何评估你的表达.在每一行上用等于等于等于,表达式很快就会计算为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

Answer 2

我对foldr的理解是它将遍历列表中的每个项目(也许这种理解是不完整的).

foldr(不像foldl)不必遍历列表中的每个项目.看看如何foldr定义是有益的.

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

当foldr评估调用时,它会强制评估对函数的调用f.但请注意递归调用foldr是如何嵌入到函数的参数中的f.如果f不评估其第二个参数,则不评估该递归调用.