haskell - 为什么不能根据 foldl 重新定义(实现)foldr

Question

我们有 foldl can be implemented in terms of foldr .这在 A tutorial on the universality and expressiveness of fold 中有详细解释.论文中指出:

In contrast, it is not possible to redefine fold in terms of foldl , due to the fact that foldl is strict in the tail of its list argument but fold is not.

然而，我看不出这是如何证明无法定义 foldr在 foldl 方面(请注意，在原始论文中 fold 是 foldr 的同义词)。我很困惑试图理解严格在这里的作用。有人可以扩展这个解释吗？

Answer 1

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x : xs) = f x (foldr f acc xs)

请注意，当列表不为空时，递归调用 foldr在传递给 f 的参数中. Haskell 被惰性求值，因此递归调用 foldr不一定实际计算。如 f可以在不检查第二个参数的情况下返回结果(但 可以 检查第一个参数 x 来决定是否要查看它的第二个参数)，然后是 foldr call 可以“提前停止”，而无需检查整个列表。

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x : xs) = foldl (f acc x) xs

这里(当列表不为空时) foldl立即递归，调用 f在它传递给递归调用的累加器参数中。 f没有机会决定是否检查递归调用； foldl完全控制递归持续多长时间，并且它会一直这样做直到找到列表的末尾。

所以特别是，用 foldr您可以潜在地处理一个无限列表；只要你传递给它的函数最终没有引用它的第二个参数( acc )。例如在 GHCi 中:

Prelude> foldr (\x acc -> if x > 10 then "..." else show x ++ ", " ++ acc) "STOP" [1..5]
"1, 2, 3, 4, 5, STOP"

Prelude> foldr (\x acc -> if x > 10 then "..." else show x ++ ", " ++ acc) "STOP" [1..]
"1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..."

与 foldr ，lambda 函数能够使用该 if检查列表元素的语句 x并决定是否使用折叠列表其余部分的结果(由 acc 引用但实际上尚未计算)。

或者，该函数可以返回包含递归调用的结果，但将其存储在数据构造函数的字段中。这意味着 foldr将产生一个无限嵌套的数据结构，但允许 foldr 的调用者决定它想要查看多少无限结构，因此调用者可能仍然能够返回处理它的有限结果。一个例子是:

Prelude> take 10 $ foldr (\x acc -> x + 100 : acc) [] [1..]
[101,102,103,104,105,106,107,108,109,110]

在这里我只是使用 foldr做与 map 相同的工作，将无限列表的每个元素加100，依次产生无限列表，然后 take 10只抓取其中的前 10 个。这是有效的，因为无限的“折叠列表结果的结果”只是存储在列表构造函数 : 的第二个字段中。 .
foldl无法模拟处理无限列表的能力(无论您实际上返回有限结果还是无限结果)。 , 因为你传入的函数 foldl无法决定使用“多少”递归； foldl在返回除对 foldl 的另一个调用之外的任何内容之前，它本身会一直递归到列表的末尾。 .如果列表是无限的，除了再次调用 foldl 之外，它永远不会返回任何内容。 , 不管你传给 foldl 什么函数或者您使用什么包装器来尝试使其完成 foldr 的工作.

这不仅仅是处理无限列表(如果这看起来很深奥的话)；如果你所有的列表都是有限的，那么你可以使用 foldl获得与 foldr 相同的结果但是您仍然被锁定在检查整个列表中，如果您实际上只需要它的一个小前缀，这可能会非常低效。