为什么这个Haskell代码能够成功地使用无限列表?
-
08-07-2019 - |
题
我有一些 在无限列表中正常工作的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
请帮助我理解:为什么??
解决方案
让我们在脑海中对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
其他提示
我对foldr的理解就是它 将遍历每个项目 列表(也许是那种理解 是不完整的。)
foldr
(与 foldl
不同)不必遍历列表中的每个项目。查看如何定义 foldr
是有益的。
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
当评估对 foldr
的调用时,它会强制评估对函数 f
的调用。但请注意对 foldr
的递归调用是如何嵌入到函数 f
的参数中的。如果 f
不评估其第二个参数,则不会评估该递归调用。
这里的关键点是Haskell是一种非严格的语言。 "非严格"意味着它允许非严格的函数,这反过来意味着在使用它们之前可能无法完全评估函数参数。这显然允许惰性评估,这是“延迟计算直到需要结果的技术”。
从这篇Wiki文章开始
我不知道Haskell,但我怀疑在你的情况下,它的作用是因为懒惰的评估。因为它允许您无限长地使用列表,当您访问它时,它将根据您的需要计算结果。