左和右折叠无限列表 [英] Left and Right Folding over an Infinite list

问题描述

我遇到以下学习你一个Haskell 的问题（很棒的书imo，不要废止它） ：

一个很大的区别是，正确的
fold在无限列表上工作，而左边的不是！明白地说，如果您在某个时间点获得无限列表，并且从右侧折叠
，您最终会到达列表的开头。
然而，如果您在某一点上获得无限列表，并且您尝试从左侧折叠
，那么您将永远无法达到目的！

我只是不明白这一点。如果你有一个无限的列表，并尝试从右边折叠起来，那么你将不得不从无穷远处开始，这不会发生（如果有人知道你可以做到这一点的语言，它会告诉：p ）。至少，根据Haskell的实现，你必须从Haskell的实现开始，因为在Haskell中，foldr和foldl不会接受一个参数来确定列表中哪些位置应该开始折叠。

我同意这个引用iff foldr和foldl接受了确定列表中他们应该从哪里开始折叠的参数，因为如果你接受一个无限列表并从一个已定义的索引开始折叠，那么它将会最终会终止，而无论你从哪里开始左侧折叠都无关紧要;你会朝着无限的方向折叠。然而，foldr和foldl 不会接受这个参数，因此引用没有任何意义。在Haskell中，无限列表中的左对齐和右对齐不会终止。

我的理解是正确还是缺少某些东西？

解决方案

这里的关键是懒惰。如果您用于折叠列表的函数是严格的，那么无论是左折还是右折都将终止，给出无限列表。

code>前奏> foldr（+）0 [1 ..]
^ C中断。

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

  Prelude> foldr（\xy  - > x）0 [1 ..] 
 1 
  

你甚至可以得到一个无限数据结构的结果，所以尽管它在某种意义上不会终止，但它仍然能够产生一个可以被懒惰消费的结果。

 前奏> 10 $ foldr（:) [] [1 ..] 
 [1,2,3,4,5,6,7,8,9,10] 
  

然而，这对于 foldl 不起作用，因为您永远无法评估最外层函数调用，懒惰或不。

  Prelude> foldl（flip（:)）[] [1 ..] 
 ^ C中断。 
前奏> foldl（\ xy  - > y）0 [1 ..] 
 ^ C中断。 
  

请注意，左侧和右侧折叠之间的关键区别并不在于列表的排列顺序遍历，它总是从左到右，而是如何生成的函数应用程序嵌套。

• 使用 foldr ，它们嵌套在内部。
  $ b

    foldr fy（x：xs） = fx（foldr fy xs）
    

  这里，第一次迭代将导致最外面的˚F。因此， f 有可能是懒惰的，所以第二个参数或者不总是被计算，或者它可以产生数据结构的一部分而不强制它的第二个参数。 / p>




• 使用 foldl ，它们嵌套在外部

    foldl fy（x：xs）= foldl f（fyx）xs 
    

  在这里，我们不能评估任何东西，直到我们已经到达 f 的最外层应用程序，在无限的情况下我们永远不会达到无论 f 是否严格。

I have issues with the following passage from Learn You A Haskell (Great book imo, not dissing it):

One big difference is that right folds work on infinite lists, whereas left ones don't! To put it plainly, if you take an infinite list at some point and you fold it up from the right, you'll eventually reach the beginning of the list. However, if you take an infinite list at a point and you try to fold it up from the left, you'll never reach an end!

I just don't get this. If you take an infinite list and try to fold it up from the right then you'll have to start at the point at infinity, which just isn't happening (If anyone knows of a language where you can do this do tell :p). At least, you'd have to start there according to Haskell's implementation because in Haskell foldr and foldl don't take an argument that determines where in the list they should start folding.

I would agree with the quote iff foldr and foldl took arguments that determined where in the list they should start folding, because it makes sense that if you take an infinite list and start folding right from a defined index it will eventually terminate, whereas it doesn't matter where you start with a left fold; you'll be folding towards infinity. However foldr and foldl do not take this argument, and hence the quote makes no sense. In Haskell, both a left fold and a right fold over an infinite list will not terminate.

Is my understanding correct or am I missing something?

解决方案

The key here is laziness. If the function you're using for folding the list is strict, then neither a left fold nor a right fold will terminate, given an infinite list.

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

However, if you try folding a less strict function, you can get a terminating result.

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

You can even get a result that is an infinite data structure, so while it does in a sense not terminate, it's still able to produce a result that can be consumed lazily.

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

However, this will not work with foldl, as you will never be able to evaluate the outermost function call, lazy or not.

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

Note that the key difference between a left and a right fold is not the order in which the list is traversed, which is always from left to right, but rather how the resulting function applications are nested.

• With foldr, they are nested on "the inside"

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

  Here, the first iteration will result in the outermost application of f. Thus, f has the opportunity to be lazy so that the second argument is either not always evaluated, or it can produce some part of a data structure without forcing its second argument.

• With foldl, they are nested on "the outside"

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

  Here, we can't evaluate anything until we have reached the outermost application of f, which we will never reach in the case of an infinite list, regardless of whether f is strict or not.

这篇关于左和右折叠无限列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！