为什么 foldright 适用于无限列表?

Why does foldright work for infinite lists?

我的印象是 foldright 从列表的末尾开始并向后工作(这就是我想象的右关联的含义)。所以我很困惑以下适用于无限列表。

我有一个函数find:

find :: (a -> Bool) -> List a -> Optional a
find p = foldRight (\c a -> if p c then Full c else a) Empty

注意以下工作:

>> find (const True) infinity
Full 0

我确实做了一些搜索并找到了这个 post:How do you know when to use fold-left and when to use fold-right?

不幸的是,接受的答案并不是特别有用,因为右关联操作的示例是:

A x (B x (C x D))

这仍然意味着它需要先执行最右边的事情。

我想知道是否有人可以为我解决这个问题,谢谢。

你的反对太过分了。如果它是有效的,则根本不可能有无限列表!使用 (:) 构造无限列表。它的第二个参数,列表的尾部,也是一个无限列表,必须首先计算。这递归地不会让我们到任何地方。

让我们从一个函数开始:

>>> let check x y = if x > 10 then x else y
>>> check 100 5
100
>>> check 0 5
5

check 接受两个参数,但可能不会使用它的第二个参数。由于 haskell 是惰性的,这意味着可能永远不会计算第二个参数:

>>> check 20 (error "fire the missles!")
20

这种懒惰让我们跳过了可能 无限 的工作量:

>>> check 30 (sum [1..])
30

现在让我们使用等式推理逐步完成 foldr check 0 [0..]

foldr check 0 [0..]
= check 0 (foldr check 0 [1..]) -- by def'n of foldr
= foldr check 0 [1..] -- by def'n of check
= check 1 (foldr check 0 [2..]) -- by def'n of foldr
= foldr check 0 [2..] -- by def'n of check
-- ...
= foldr check 0 [10..]
= check 10 (foldr check 0 [11..]) -- by def'n of foldr
= foldr check 0 [11..] -- by def'n of check
= check 11 (foldr check 0 [12..]) -- by def'n of foldr
= 11 -- by def'n of check

请注意懒惰如何迫使我们自上而下地评估,看看最外层的函数调用如何(以及是否)使用其参数,而不是自下而上(在将所有参数传递给功能),就像严格的语言一样。

它之所以有效,是因为懒惰求值。让我们举一个非常简单的例子。

import Data.Char (toUpper)

main :: IO ()
main = interact (foldr capitalized []) where
  capitalized :: Char -> String -> String
  capitalized x xs = (toUpper x):xs

运行 这个程序交互,看看会发生什么。输入是从标准输入读取的无限(或至少不确定)字符列表。

这是有效的,因为输出列表的每个元素都是在需要时延迟生成的。所以尾巴是 而不是 首先产生的:它只在需要的时候计算。在那之前,它被推迟了,我们可以使用部分结果。 'h':xs 的部分结果是 'H':(foldr capitalized [] xs)'h':'e':'l':'l':'o':',':' ':'w':'o':'r':'l':'d':'!':'\n':xs 的部分结果是我们可以在继续尾部 xs.

之前输出的字符串

现在看看如果用 foldl 试试会发生什么。

这适用于生成有用前缀的任何数据结构。对于产生单个值且没有有用的中间结果的缩减操作,严格的左折叠 (Data.List.foldl') 通常是更好的选择。