logo标签列表

在一个无限列表上进行左折叠和右折叠

listhaskellfunctional-programminginfinitefold
73
我对Learn You A Haskell的以下段落有疑问（我认为这是一本很好的书，不是在贬低它）：
其中一个重要的区别是右折叠可以处理无限列表，而左折叠不行！简单地说，如果你从右边开始对一个无限列表进行折叠，最终会到达列表的开头。然而，如果你从左边开始对一个无限列表进行折叠，你永远也无法到达列表的结尾！
我不理解这个问题。如果你从右边开始对一个无限列表进行折叠，那么你必须从无限的起点开始，但这根本不可能发生（如果有任何一种语言可以这样做，请告诉我:p）。至少，根据Haskell的实现方式，你必须从那里开始，因为在Haskell中，foldr和foldl不需要参数来确定他们应该从列表的哪个位置开始折叠。
如果foldr和foldl需要一个参数来确定他们应该从列表的哪个位置开始折叠，我会同意上述引用，因为如果你从一个定义的索引开始向右折叠一个无限列表，它最终将终止，而无论你从哪里开始左折叠，你都会朝着无限迭代。然而，foldr和foldl没有接受这个参数，因此这个引用没有意义。在Haskell中，对于无限列表，左折叠和右折叠都不会终止。
我的理解是否正确，或者我有什么误解？
3
也许你应该查看相关栏中的这个问题：https://dev59.com/znRA5IYBdhLWcg3wxA5N。 - gatoatigrado
1
foldl 和 foldr 都 从左到右处理列表。这篇文章 可以帮助你更深入地理解 folds。 - Matthias Braun
5个回答
90

这里的关键是“惰性”。如果您用于折叠列表的函数是严格的，那么无论是左折叠还是右折叠，在给定无限列表时都不会终止。

Prelude> foldr (+) 0 [1..]
^CInterrupted.

然而，如果您尝试折叠一个不太严格的函数，您可以获得一个终止的结果。

Prelude> foldr (\x y -> x) 0 [1..]
1

你甚至可以得到一个无限的数据结构作为结果，因此尽管它在某种意义上没有终止，但仍然能够生成可以被惰性消耗的结果。

Prelude> take 10 $ foldr (:) [] [1..]
[1,2,3,4,5,6,7,8,9,10]

然而，这对于foldl是行不通的，因为你永远无法评估最外层的函数调用，无论是否延迟。

Prelude> foldl (flip (:)) [] [1..]
^CInterrupted.
Prelude> foldl (\x y -> y) 0 [1..]
^CInterrupted.

请注意，左折叠和右折叠的关键区别不在于列表遍历的顺序（始终从左到右），而是结果函数应用嵌套的方式。

  • 使用foldr时，它们在“内部”嵌套

foldr f y (x:xs) = f x (foldr f y xs)

在这里，第一次迭代将导致对f的最外层应用。因此，f有机会变为懒惰，以便第二个参数不总是被评估，或者它可以生成数据结构的某些部分而不强制其第二个参数。

  • 而对于foldl，它们是“外部嵌套”的。

    • foldl f y (x:xs) = foldl f (f y x) xs

    在这里，我们无法评估任何内容，直到我们达到f的最外层应用程序，而对于无限列表的情况，无论f是否严格，我们都永远无法到达。

    1
    这很有趣：foldr (\x y -> x) 0 [1..]。它真的是惰性求值的一个例子吗？还是编译器只是聪明地处理了它？我不知道它如何以传统意义上的方式进行求值，但最终值却非常明显。那么 GHC 到底是在惰性求值（如果是，那么它是如何做到的？:P），还是只是足够聪明地认识到答案将永远是1？ - TheIronKnuckle
    2
    @ThelronKnuckle 这是惰性求值。或者更确切地说，这是 Haskell 的非严格语义。无论编译器有多聪明，它都不允许改变这一点。 - augustss
    3
    这段内容的意思是一个 Haskell 语言中的表达式，使用了 foldr 函数对一个从 1 开始无限递增的列表进行计算。具体来说，这个表达式将每个元素都映射为其本身，然后返回第一个元素。在这个过程中，foldr 将列表中的元素一个接一个地传递给一个函数，该函数将当前元素和累积值作为参数，并返回一个新的累积值。在这种情况下，我们传递了一个只返回第一个参数的函数，因为它忽略了累积值并返回当前元素。最终的结果是 1。 - Daniel Wagner
    这个答案是我找到的对一个问题最好的解释，而我之前一直感到困惑。如果当时我看到了它，我会更快地理解。如果可以的话，我会给它加10分。 - Benjamin Hodgson
    您还可以包括来自Haskell Wiki的图像，这些图像很好地说明了 foldl 和 foldr 之间的区别。 - Petr
    显示剩余7条评论
    18

    关键词是“在某个时刻”。

    如果你在某个时刻拿到一个无限长的列表并从右边对折它，最终会抵达列表的开头。

    所以你说得对，你不可能从一个无限长的列表的“最后”元素开始。但作者的意思是：假设你可以。只需要选择一个非常远的位置（对于工程师来说，这足够接近无穷大），然后向左折叠。最终你会回到列表的开头。如果你选择了一个距离列表起始点很远的位置（称之为“足够接近”列表起始点），然后向右折叠，情况就不同了。你仍然有无限的路要走。

    因此，诀窍在于，有时你不需要去无限远。你甚至可能不需要走得很远。但你可能事先不知道需要走多远，这时无限长的列表就非常方便。

    一个简单的例子是 foldr (:) [] [1..]。让我们执行这个折叠操作。

    回想一下，foldr f z (x:xs) = f x (foldr f z xs)。在一个无限长的列表上，实际上并不在意z是什么，所以我只将其保留为z而不是[]，这会让例子显得更加清晰。

    foldr (:) z (1:[2..])         ==> (:) 1 (foldr (:) z [2..])
1 : foldr (:) z (2:[3..])     ==> 1 : (:) 2 (foldr (:) z [3..])
1 : 2 : foldr (:) z (3:[4..]) ==> 1 : 2 : (:) 3 (foldr (:) z [4..])
1 : 2 : 3 : ( lazily evaluated thunk - foldr (:) z [4..] )

    你看到了吗？尽管从理论上讲，foldr 是从右边折叠的，但在这种情况下它实际上会从左边开始输出结果列表中的单个元素。因此，如果你从这个列表中 take 3，你可以清楚地看到它将能够产生 [1,2,3]，并且不需要进一步评估折叠。

    7
    “从右侧选择某个点并向后推导”这一部分确实是关键所在，而不仅仅是一个例子--因为所谓的“某个点”只是您实际使用的最远点。因此，我们实际上可以将“无穷大”定义为“至少比我们最终需要的多一个”，我认为这是一种既符合工程师又符合数学家的定义。 - C. A. McCann
    12
    记住在 Haskell 中，由于惰性评估，您可以使用无限列表。因此，head [1..] 只是 1，并且 head $ map (+1) [1..] 是 2，即使 `[1..]` 是无限长的。如果您不理解这一点，请停下来花一些时间去尝试一下。如果您已经理解了，那么请继续阅读...
    我认为你感到困惑的部分是foldl和foldr总是从一边或另一边开始，因此不需要给出长度。 foldr 的定义非常简单。
     foldr _ z [] = z
 foldr f z (x:xs) = f x $ foldr f z xs

    为什么这段代码会在无限列表上终止，可以尝试一下

     dumbFunc :: a -> b -> String
 dumbFunc _ _ = "always returns the same string"
 testFold = foldr dumbFunc 0 [1..]

    在这里，我们将一个空字符串（因为其值并不重要）和无限自然数列表传递给foldr。这是否会终止呢？是的。

    它能够终止的原因是Haskell的求值等同于惰性术语重写。

    因此，

     testFold = foldr dumbFunc "" [1..]

    变成 (以允许模式匹配)

     testFold = foldr dumbFunc "" (1:[2..])

    这与我们对折叠的定义相同。

     testFold = dumbFunc 1 $ foldr dumbFunc "" [2..]

    现在根据 dumbFunc 的定义，我们可以得出结论。

     testFold = "always returns the same string"

    当我们有一些能够执行某些操作但有时候是懒的函数时，这就变得更加有趣了。例如:

    foldr (||) False

    any 用于检查列表中是否包含任何 True 元素。我们可以使用它来定义高阶函数 any，如果传入的函数对列表中的某个元素返回真，则返回 True。

    any :: (a -> Bool) -> [a] -> Bool
any f = (foldr (||) False) . (map f)

    惰性求值的好处在于，当它遇到第一个使得 f e == True 成立的元素 e 时就会停止。

    然而，这并不适用于 foldl。为什么呢？因为一个非常简单的 foldl 看起来像这样：

    foldl f z []     = z                  
foldl f z (x:xs) = foldl f (f z x) xs

    现在，如果我们尝试上述示例会发生什么？

    testFold' = foldl dumbFunc "" [1..]
testFold' = foldl dumbFunc "" (1:[2..])

    现在变成了这样：

    testFold' = foldl dumbFunc (dumbFunc "" 1) [2..]
    所以
    testFold' = foldl dumbFunc (dumbFunc (dumbFunc "" 1) 2) [3..]
testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) [4..]
testFold' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) 4) [5..]

    等等等等，我们永远无法到达目的地，因为Haskell总是首先评估最外层的函数（这就是懒惰求值的精髓）。

    这样做的一个很酷的结果是，你可以用foldr实现foldl，但反过来却不行。这意味着在某种深刻的意义上，foldr是所有高阶字符串函数中最基本的函数，因为它是我们用来实现几乎所有其他函数的函数。有时仍然可能想要使用foldl，因为你可以通过尾递归来实现它，并从中获得一些性能提升。

    我一边阅读你的帖子，一边评论：这个程序会在无限的“false”值列表上终止吗？foldr (||) False。我可以看出如果列表中有一个True，那么它会在无限的列表上停止，但是如果列表永远是False，那么将导致非终止，对吗？ - TheIronKnuckle
    是的，我刚刚在ghci中运行了它（应该一开始就这样做:P）。它没有终止。 - TheIronKnuckle
    很高兴我的代码是正确的。它不终止的事实是有道理的。如果你一个接一个地给我一个列表，我只能告诉你它到目前为止是否有任何真值，而不能告诉你它将来是否会有。因此，判断一个列表是否有任何真元素的最快方法是遍历并在第一个元素处停止，这就是foldr代码所做的，显然，“在第一个元素处停止”如果找不到第一个元素就不会终止... - Philip JF
    0

    在Haskell wiki上有很好的简明解释。它展示了使用不同类型的fold和累加器函数进行逐步简化的步骤。

    -3

    你的理解是正确的。我想知道作者是否试图谈论Haskell的惰性求值系统（其中您可以将无限列表传递给各种函数，但不包括fold，它只会评估需要返回答案的部分）。但我同意你的观点，作者在那段落中没有描述任何东西，而且所说的是错误的。

    4
    为什么不包括fold？试试这个：foldr (:) [] [1..]。 - n. m.
    2
    不，这段文字可能不太清晰，但它并没有错误。它在谈论惰性计算，而且所给的理由正是为什么foldr能够处理无限列表的原因。 - C. A. McCann
    真是愚蠢的事情，如果我当时继续看书，只需翻几页就能找到我想要的解释:p - TheIronKnuckle
    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接