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

Question

对于无限列表，其中没有 "last" 个元素。那么 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

按预期工作，但我不明白：

(&&) 的定义在它的左边接收布尔值，但是我们应用 True && x = x 而变量 x 位于其右侧。是不是很奇怪？
为什么 foldr 在 (&&) returns False 时停止？在我的理解中 foldr 将从尾部到头部循环遍历列表。有没有内部的"break"机制？
foldr 从列表的最后一个元素开始，但无限列表没有结束。 foldr 是如何开始工作的？

Answer 1

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

 this   =   that

并且，基本上，它的意思是：当您看到 this 时，它意味着 that。事实上

True && x

与x相同，

False && x

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

关于你的第二个问题：foldr"stops"不是这样的。当左操作数为 False.

时，&& 运算符不计算其右操作数

对于您的第 3 个问题：不，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

Answer 2

让我们重复您的定义并添加更多：

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

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

repeat :: a -> [a]
repeat a = a : repeat a

foldr :: (a -> r -> r) -> r -> [a] -> r
foldr _ z [] = z
foldr f z (a:as) = f a (foldr f z as)

现在，我们可以通过手动评估来证明这一点，注意做到这一点"lazily"（首先是最外层的应用程序，并且只评估足以解析最外层的数据构造函数）：

and (repeat False)
  = foldr (&&) True (repeat False)           -- definition of `and`
  = foldr (&&) True (False : repeat False)   -- definition of `repeat`
  = False && foldr (&&) True (repeat False)  -- `foldr`, second equation
  = False                                    -- `&&`, second equation

关键是 && 定义的第二个等式丢弃了它的第二个参数：

False && _ = False

这意味着，在运行时术语中，我们永远不会在遇到 False.

的步骤强制执行 foldr 的递归调用

另一种看待它的方法是考虑 foldr 的第二个等式，以及当我们进行惰性计算时它意味着什么：

foldr f z (a:as) = f a (foldr f z as)

由于对 foldr 的递归调用作为 f 的参数发生，这意味着在运行时，函数 f 决定其第二个参数的值是否必要或不，因此在折叠的每一步选择是否递归列表。这个"decision"过程是从左到右进行的。

In my understanding foldr will loop through the list from tail till head. Is there any internal "break" mechanism?

严格来说，在纯函数式语言中没有计算顺序的内在概念。可以按照与其数据依赖性一致的任何顺序评估表达式。

你在这里所说的是一个常见的误解，即从 foldr 不纯、急切的语言中学习的人会转移到 Haskell。在急切的语言中，这是一条有用的经验法则，但在 Haskell 中，使用纯粹惰性求值，该规则只会让您感到困惑。通常相反的经验法则在编程时很有用 Haskell：foldr 将从左到右访问列表元素，并且在每一步其 f 参数函数决定是否需要列表的其余部分。

极端的例子是使用foldr:

实现一个获取列表头部的函数

-- | Return `Just` the first element of the list, or `Nothing` if the
-- list is empty.
safeHead :: [a] -> Maybe a
safeHead = foldr (\a _ -> Just a) Nothing

例如：

safeHead [1..]
  = foldr (\a _ -> Just a) Nothing [1..]
  = foldr (\a _ -> Just a) Nothing (1:[2..])
  = (\a _ -> Just a) 1 (foldr (\a _ -> Just a) Nothing [2..])
  = Just 1

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

Why right folding can process infinite list in Haskell?

haskell

list

infinite

fold