作者:欣荣_75229 | 来源:互联网 | 2023-05-29 11:37
我一直致力于在Haskell中理解foldl
vs foldr
vs.foldl'
我理解,共识是在第二个参数中使用foldr
何时f
是惰性的,因为它反映了列表的结构.foldl'
当我们知道需要处理整个列表并且f
其参数严格时,会更好.
我特别感兴趣的是这样的情况:
foldr (&&) False (repeat False)
回报False
.
但:
foldl (&&) False (repeat False)
从未完成.
该foldr
扩展为:
False && (False && (False && .... (False && *False*)) ... )
鉴于foldl
:
&& (... (&& (&& *False* False) False) ...) False
星星是False
传入的基础案例fold
.
是否foldr
能立即终止,因为LHS只是一个单一的False
,而foldl
单False
是在右边一路,它不"检查"直到它完成处理左边?
1> luqui..:
让我们看一下相关的定义(与Prelude中的定义不完全相同,但与此分析相当).
(&&) :: Bool -> Bool -> Bool
True && x = x
False && _ = False
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
看看每个foldr
和foldl
必须产生结果的机会.给出时,它们都会立即产生结果[]
.在这种(x:xs)
情况下,foldr
如果f
立即返回而不评估其正确的参数(这是递归调用),也有机会产生结果. foldl
没有这个,因为它最外面的调用是自己的,所以唯一的时间foldl
可以给出任何信息回来的[]
情况,这是无限的列表永远不会达到.
在这样的例子中,我发现做一些手动评估很有帮助.回想一下,Haskell的评估顺序是在外面进行的:我们尽可能少地评估最外层函数应用程序的适用模式匹配.我将在每个步骤中使用斜体来表示要评估的下一个函数.foldr
很简单:
foldr (&&) False (repeat False)
= foldr (&&) False (False : repeat False)
= False && foldr (&&) False (repeat False)
= False
并foldl
揭示问题:
foldl (&&) False (repeat False)
= foldl (&&) False (False : repeat False)
= foldl (&&) (False && False) (repeat False)
= foldl (&&) (False && False) (False : repeat False)
= foldl (&&) ((False && False) && False) (repeat False)
= foldl (&&) ((False && False) && False) (False : repeat False)
= foldl (&&) (((False && False) && False) && False) (repeat False)
等等.请注意,即使(&&)
有能力通过检查任何一方来简化,我们仍然永远不会有机会返回它,因为我们从未达到过这种[]
情况.
然而,顺序(&&)
计算它的参数也还那么重要(这对左一个第一,通过模式匹配语义确定).我们可以flip
参数的顺序,看看有什么foldr
作用:
ghci> foldr (flip (&&)) False (repeat False)
^CInterrupted
(运动)这是为什么?