为什么不能根据 foldl 重新定义（实现）foldr

Question

我们有 foldl can be implemented in terms of foldr. This is explained in detail in 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.

但是我看不出这是如何证明不可能用 foldl 来定义 foldr（请注意，在原始论文中 fold 是 foldr).我很困惑试图理解严格在这里是如何发挥作用的。有人可以详细解释一下吗？

Answer 1

在下文中，我将 fold 称为 foldr（因为这是 Haskell 标准库中的名称）。

再看一下foldl,

的定义

foldl :: (β -> α -> β) -> β -> [α] -> β
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs

请注意，基本情况要求列表参数为 [] - 在所有其他情况下，列表被评估为 WNHF 并且我们立即使用列表的尾部进行递归。这证实了 foldl 在其（最后一个）列表参数中是严格的这一事实。

现在，我们可以使用foldl编写foldr的一个版本，但它只适用于有限长度的列表。参见 this page 的动机。

foldr' :: (α -> β -> β) -> β -> [α] -> β
foldr' f v xs = foldl (\g u x -> g (f u x)) id xs v

为了看到问题，让我们试着写一个 head 的版本，它是 ¹ 使用右折叠。

import Control.Applicative ((<|>))

safeHead :: [α] -> Maybe α
safeHead = foldr (\x y -> Just x <|> y) Nothing

如果我们用基于 foldl 的 foldr' 替换 foldr，我们将无法再找到无限列表的头部 safeHead [1..]。即使 safeHead 只需要查看列表的第一个元素，底层的 foldl 也会尝试遍历整个无限列表。

¹这样的功能其实在Prelude中已经存在了，叫做listToMaybe

Answer 2

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 可以 return 不检查第二个参数的结果（但它可以检查第一个参数 x 以决定是否要查看其第二个参数），那么 foldr 调用可以 "stop early"，而不检查整个列表。

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 引用但实际上尚未计算）。

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

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 个。这是可行的，因为无限 "results of folding the result of the list" 只是存储在列表构造函数 :.

的第二个字段中

无法通过 foldl 模拟处理无限列表的能力（无论您实际上 return 是有限还是无限结果），因为您传递给 foldl 的函数无法决定要使用的递归 "how much"； foldl 在它 return 除了对 foldl 的另一个调用之外，它本身一直递归到列表的末尾。如果列表是无限的，它永远不会 return 除了对 foldl 的另一个调用之外的任何东西，无论你传递给 foldl 什么函数或者你使用什么包装器来尝试让它做foldr.

的工作

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

为什么不能根据 foldl 重新定义（实现）foldr

Why it is not possible to redefine (implement) foldr in terms of foldl

haskell

fold

proof