为什么折叠权适用于无限列表?

Why does foldright work for infinite lists?

提问人:adrianmcli 提问时间:2/7/2018 更新时间:2/7/2018 访问量:485

问:

我的印象是从列表的末尾开始向后工作(这就是我想象的权利关联意味着什么)。所以我很困惑以下内容适用于无限列表。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

我确实做了一些搜索并找到了这篇文章: 你怎么知道什么时候使用左折,什么时候使用右折?

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

A x (B x (C x D))

这仍然意味着它需要首先执行最正确的事情。

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

Haskell 函数式编程 语言不可知 折叠

评论

4赞 4castle 2/7/2018
Haskell 是懒惰的,因此仅在必要时才计算第二个参数。A
4赞 Daniel Wagner 2/7/2018
你说,“这个例子仍然意味着它需要首先执行最正确的事情。(在这里,我假设您所说的“最正确的事情”是指,或者可能。这似乎是你在推理中犯的根本错误。A x (B x (C x D))DC x D
4赞 molbdnilo 2/7/2018
我怀疑您混淆了关联性(适用于运算符)和评估顺序(适用于其操作数)。在 中,你可以先评估,如果你知道它提供了你永远不需要评估的答案。(例如,考虑一下,您可以立即看到它是 。A x (B x (C x D))AB x (C x D)AB x (C x D)0 * (123456789 * (890123456 * 789123456))0

答:

1赞 Gurkenglas 2/7/2018 #1

你的反对意见证明太多了。如果它是有效的,那么根本不可能有无限的列表!无限列表是使用 构造的。它的第二个参数,即列表的尾部,也是一个无限列表,必须首先进行评估。递归地,这不会让我们走到任何地方。(:)

12赞 rampion 2/7/2018 #2

让我们从一个函数开始:

>>> 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

请注意,懒惰如何迫使我们从上到下进行评估,看看最外层的函数调用如何使用其参数,而不是像严格语言那样自下而上(在将所有参数传递给函数之前评估所有参数)。

评论

0赞 adrianmcli 2/9/2018
左折呢?如果它是左联想的,但它“从外向内工作”,这难道不意味着左折从右开始,它永远不能与无限列表一起工作吗?
2赞 rampion 2/9/2018
AdrianMC - 你已经完全明白了
4赞 Davislor 2/7/2018 #3

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

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':xsxs

现在看看如果你尝试这样做会发生什么。foldl

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