无限列表上的左右折叠

我对 向你学习 Haskell中的以下段落有疑问(这是一本很棒的书，不是贬低它) :

一个很大的区别是，这是正确的 折叠在无限的列表上起作用，而左边的列表不起作用 简单地说，如果你在某个时刻取一个无限的列表，然后把它折叠起来 从右边开始，你最终会到达列表的开头。 但是，如果你在一个点上有一个无限的列表，你试图折叠 从左往上，你永远也到不了终点！

我就是不明白。如果你把一个无限的列表从右边折叠起来，那么你必须从无穷远点开始，这是不可能的(如果有人知道一种语言你可以做到这一点，请告诉: p)。至少，你必须根据 Haskell 的实现从那里开始，因为在哈斯克尔，foldr 和 foldl 没有参数来决定它们应该从哪里开始折叠。

我同意引用 iff foldr 和 foldl 的参数决定了它们应该从列表中的哪个位置开始折叠，因为如果你从一个定义好的索引开始折叠一个无限的列表，那么 威尔最终会结束，而从左折叠的位置开始并不重要，你会折叠到无穷远处。但是 foldr 和 foldl不要使用这个参数，因此引号没有意义。在哈斯克尔，无限长列表 abc2上的左折叠和右折叠。

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

8133 次浏览
小开

你的理解是正确的。我想知道作者是否试图谈论 Haskell 的惰性求值系统(在这个系统中，您可以将无限列表传递给不包括 fold 的各种函数，并且它只求值不管返回答案需要多少)。但是我同意你的看法，作者没有很好地描述那一段中的任何内容，而且那些内容是错误的。

小开
最佳答案

这里的关键是懒惰。如果用于折叠列表的函数是严格的，那么给定无限列表时，左折叠和右折叠都不会终止。

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是否严格。

小开

记住，在哈斯克尔，你可以使用无限列表，因为它是惰性计算。所以，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 a“”(因为值并不重要)和自然数的无限列表。这会终止吗？是的。

它终止的原因是 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元素。我们可以使用它来定义高阶函数 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 总是首先计算最外面的函数(简而言之就是惰性计算)。

这样做的一个很酷的结果是，您可以在 foldr之外实现 foldl，但反之则不行。这意味着在某种意义上，foldr是所有高阶字符串函数中最基本的，因为它是我们用来实现几乎所有其他字符串函数的函数。有时您仍然可能希望使用 foldl，因为 可以递归地实现 foldl尾部，并从中获得一些性能收益。

小开

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

如果你把一个无限的列表 在某个时候从右边折叠起来，你最终会到达列表的开头。

所以你是对的，你不可能从一个无限列表的“最后”元素开始。但是作者的观点是: 假设你可以。只要选择一个远处的点(对于工程师来说，这是“足够接近”到无穷远) ，然后开始向左折叠。最终你会出现在名单的开头。左折叠并不是这样，如果你选择一个点离开那里(并称之为“足够接近”列表的开始) ，并开始向右折叠，你仍然有无限的路要走。

所以诀窍就是，有时候你不需要去无穷远处。你甚至不需要离开那里。但是您可能不知道需要预先走多远，在这种情况下，无限列表非常方便。

简单的例子是 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]，并且不需要进一步计算折叠。

小开

Haskell 维基有很好的简明解释，它显示了不同类型的褶皱和蓄能器功能的逐步减少。


提交答案