为什么不可能在foldl方面重新定义(实现)foldr

我们foldl可以实现foldr这一点.这在关于折叠的普遍性和表现力的教程中有详细解释.在论文中指出:

相反,它是不可能重新定义fold来讲foldl,由于这样的事实,foldl在其列表参数的尾部严格,但fold并非如此.

不过,我看不出这构成了对定义的不可能性证明foldr来讲foldl(注意,在原纸上fold是一个代名词foldr).我很困惑,试图理解严格性在这里发挥作用.有人可以扩展这个解释吗？

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调用可以"提前停止",而不检查整个列表.

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但是您仍然无法检查整个列表,如果您实际上只需要一个小的前缀,这可能是非常低效的.