为什么Haskell代码可以在无限列表中成功运行？ [英] Why does this Haskell code work successfully with infinite lists?

问题描述

我有一些Haskell代码可以在无限列表上正常工作，但我不明白为什么它可以成功执行。 （我修改了我的原始代码 - 不处理无限列表 - 从一些其他代码在线合并了一些代码，突然间我发现它可以工作，但不知道为什么）。

  myAny ::（a  - > Bool） - > [a]  - > Bool 
 myAny p list = foldr步骤False list 
 where 
 step item acc = p item || acc 
  

我对foldr的理解是，它会遍历列表中的每个项目（也许理解不完整）。如果是这样，那么应该怎么处理step函数......代码应该无法处理无限循环。

然而，以下工作：

  *主要Data.List> myAny甚至[1 ..] 
 True 
  

请帮我理解：为什么??

解决方案

让我们在Haskell如何评估表达式的过程中进行一些跟踪。用等于等于在每一行上的等于，表达式很快计算为真：

  myAny偶数[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（懒惰评估）传递，但也是因为第一个 || 函数严格

||和（重复真实）

但是这不是：

 和（repeat True）|| True 
  

查看||的定义。看看为什么会这样：

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

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

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.

However, the following works:

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

Please help me understand: why??

解决方案

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

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

So this terminates:

True || and (repeat True)

But this does not:

and (repeat True) || True

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

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

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