list - 为什么右折叠可以在 Haskell 中处理无限列表？

Question

对于无限列表，它没有“最后”元素。那么 foldr 如何使用它呢？

我有来自 Haskell 书中的代码片段:

(&&)::Bool->Bool->Bool
True && x = x
False && _ = False

and' :: [Bool]->Bool
and' xs=foldr (Main.&&) True xs

然后在 Prelude 中加载此 hs 文件并运行:

*Main> and' (repeat False)
False

它按预期工作，但我不明白:

1. (&&) 的定义在其左侧接收 bool 值， 但我们应用 True && x = x 而变量 x 位于其右侧。 是不是很奇怪？
2. 为什么当 (&&) 返回 False 时 foldr 会停止？ 根据我的理解 foldr 将从尾部到头部循环遍历列表。 是否存在任何内部“中断”机制？
3. foldr 从列表的最后一个元素开始，但无限列表没有结束。 foldr 如何开始工作？

Answer 1

您需要稍微熟悉一下语法。 在 Haskell 中，函数定义如下:

 this   =   that

基本上，这意味着:当您看到这个时，它意味着那个。事实上

True && x 

与x相同，并且

False && x 

是False，这就是为什么我们可以按照您的示例编写定义。

对于你的第二个问题: foldr 并不是“停止”的情况。当左侧操作数为 False 时，&& 运算符不会计算其右侧操作数。

对于你的第三个问题:不，foldr 不是从列表的最后一个元素开始。请看一下foldr的定义:

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

现在假设

foldr (&&) True (False:xs)

其计算结果为

False && foldr (&&) True xs

从那时起

False && _

为False，结果为False