73

我对Learn You A Haskell中的以下段落有疑问（很棒的书 imo，而不是 dissing）：

一个很大的区别是右折叠适用于无限列表，而左折叠则不行！说白了，如果你在某个点取一个无限列表，然后从右边折叠它，你最终会到达列表的开头。但是，如果您在某个点上取出一个无限列表并尝试从左侧折叠它，您将永远不会到达终点！

我就是不明白。如果您获取一个无限列表并尝试从右侧折叠它，那么您将不得不从无穷大的点开始，这不会发生（如果有人知道您可以这样做的语言，请告诉：p ）。至少，您必须根据 Haskell 的实现从那里开始，因为在 Haskell 中， foldr 和 foldl 不采用决定它们应该在列表中的哪个位置开始折叠的参数。

我同意报价 iff foldr 和 foldl 采用的参数决定了它们应该在列表中的哪个位置开始折叠，因为如果您采用无限列表并从定义的索引开始折叠，它最终会终止，而它不会不管你从哪里开始左弃牌；你将向无穷大折叠。然而 foldr 和 foldl不接受这个论点，因此引用没有意义。在 Haskell 中，无限列表上的左折叠和右折叠都不会终止。

我的理解是正确的还是我遗漏了什么？

4

5 回答 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

于 2011-09-13T05:17:21.790 回答
18

关键短语是“在某个时候”。

如果您在某个时刻取出一个无限列表并将其从右侧折叠起来，您最终将到达列表的开头。

所以你是对的，你不可能从无限列表的“最后一个”元素开始。但作者的观点是：假设你可以。只需选择一个离那里很远的点（对于工程师来说，这“足够接近”到无穷大）并开始向左折叠。最终你会排在列表的开头。左折叠的情况并非如此，如果你选择一个点 waaaay 那里（并称它“足够接近”列表的开头），并开始向右折叠，你仍然有无限的路要走。

所以诀窍是，有时你不需要去无穷大。你可能甚至不需要去那里。但是你可能不知道你需要提前走多远，在这种情况下无限列表非常方便。

简单的说明是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]并且不需要进一步评估折叠。

于 2011-09-13T19:08:16.307 回答
12

请记住，在 Haskell 中，由于惰性求值，您可以使用无限列表。所以，head [1..]只是 1，并且head $ map (+1) [1..]是 2，即使 `[1..] 是无限长的。如果你不明白，停下来玩一会儿。如果你明白了，请继续阅读......

我认为您的部分困惑是foldlandfoldr总是从一侧或另一侧开始，因此您不需要给出长度。

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

用于查找列表是否包含任何True元素。我们可以使用它来定义高阶函数n，当且仅当传入的函数对于列表的某些元素为真时才any返回True

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

惰性求值的好处是，它会在遇到第一个元素时停止，e这样f e == True

另一方面，这不是真的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 总是首先评估最外层的函数（简而言之就是惰性评估）。

这样做的一个很酷的结果是您可以实现foldlout offoldr但反之则不行。这意味着以某种深刻的方式foldr是所有高阶字符串函数中最基本的，因为它是我们用来实现几乎所有其他函数的函数。有时您可能仍想使用 a foldl，因为您可以递归地实现foldltail，并从中获得一些性能提升。

于 2011-09-13T06:00:32.583 回答
0

Haskell wiki上有很好的简单解释。它显示了使用不同类型的折叠和累加器功能逐步减少。

于 2015-04-10T06:47:40.087 回答
-3

你的理解是正确的。我想知道作者是否试图谈论 Haskell 的惰性评估系统（在该系统中，您可以将无限列表传递给不包括折叠的各种函数，并且它只会评估返回答案所需的多少）。但我同意你的观点，即作者没有很好地描述该段落中的任何内容，而且它所说的内容是错误的。

于 2011-09-13T05:12:08.187 回答