左右折叠无限列表

Question

我有以下段落的问题来自Learn You A Haskell(伟大的书imo,而不是贬低它):

一个很大的区别是右侧折叠在无限列表上工作,而左侧折叠不起作用!说白了,如果你在某个点拿一个无限列表并从右边折叠起来,你最终会到达列表的开头.但是,如果你在一个点上获得一个无限的列表,并且你试图从左边折叠起来,那么你永远不会达到目的!

我只是不明白这一点.如果你拿一个无限的列表并试图从右边折叠起来那么你将不得不从无穷远点开始,这就是没有发生(如果有人知道你能做到这一点的语言,请告诉:p ).至少,你必须根据Haskell的实现开始那里,因为在Haskell中,foldr和foldl不会采用一个参数来确定列表中应该开始折叠的位置.

我同意引用iff foldr和foldl接受确定列表中应该开始折叠的位置的参数,因为有意义的是,如果你采用无限列表并从定义的索引开始向右折叠它最终将终止,而它不会无论你从哪里开始左折; 你将向无限折叠.但是,foldr和foldl 不接受这个参数,因此引用没有意义.在Haskell中,无限列表上的左侧折叠和右侧折叠都不会终止.

我的理解是正确的还是我错过了什么？

Answer 1

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

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严格.

Answer 2

关键词是"在某些时候".

如果你在某个点上取一个无限列表并从右边折叠它,你最终会到达列表的开头.

所以你是对的,你不可能从无限列表的"最后"元素开始.但作者的观点是这样的:假设你可以.只需选择一个远在那里的点(对于工程师来说,这是"足够接近"到无限远)并开始向左折叠.最终你最终会在列表的开头.左侧折叠也是如此,如果你在那里选择一个点(并将其称为"足够接近"到列表的开头),并开始向右折叠,你仍然有一个无限的方式去.

所以诀窍是,有时你不需要去无限.你甚至可能不需要去那里等待.但是你可能不知道你需要预先走多远,在这种情况下,无限列表非常方便.

简单的说明是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]并且无需再评估折叠.

Answer 3

请记住,在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 

用于查找列表是否包含任何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总是首先评估最外层的函数(简而言之就是懒惰的评估).

这方面的一个很酷的结果是可以实现foldl出来的foldr而不是相反.这意味着以某种深刻的方式foldr是所有高阶字符串函数中最基本的,因为它是我们用来实现几乎所有其他函数的函数.你foldl有时也可能想要使用它,因为你可以foldl递归地实现尾部,并从中获得一些性能提升.