为什么这个 Haskell 代码可以成功地处理无限列表? [英] Why does this Haskell code work successfully with infinite lists?

问题描述

我有一些 Haskell 代码确实可以在无限列表上正常工作，但我不明白 为什么它可以成功地做到这一点.(我修改了我的原始代码——它没有处理无限列表——从其他一些在线代码中合并一些东西，突然我发现它可以工作，但不知道为什么).

I have some Haskell code that does work correctly on an infinite list, but I do not understand why it can do so successfully. (I modified my original code -- that did not handle infinite lists -- to incorporate something from some other code online, and suddenly I see that it works but don't know why).

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

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

My understanding of foldr is that it will loop through every item in the list (and perhaps that understanding is incomplete). If so, it should not matter how the "step" function is phrased ... the code should be unable to handle infinite loops.

但是，以下有效:

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

请帮助我理解:为什么??

Please help me understand: why??

推荐答案

让我们在脑海中稍微追溯一下 Haskell 将如何评估您的表达式.将每行上的等于替换为等于，表达式的计算结果很快就会为 True:

Let's do a little trace in our heads of how Haskell will evaluate your expression. Substituting equals for equals on each line, the expression pretty quickly evaluates to 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(惰性求值)传递，还因为 || 函数在其第一 争论.

This works because acc is passed as an unevaluated thunk (lazy evaluation), but also because the || function is strict in its first argument.

所以这终止:

True || and (repeat True)

但这不会:

and (repeat True) || True

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

Look at the definition of || to see why this is the case:

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

这篇关于为什么这个 Haskell 代码可以成功地处理无限列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！