我知道这个问题很旧了,但我想加入一个不同的角度,我认为这对其他人也有帮助。
从一个小例子开始,关键的洞察力在于注意到foldr
和foldl
作用于短列表时可以分别重写为
foldr f z [a, b, c]
== a `f` (b `f` (c `f` z))
== (a `f`) . (b `f`) . (c `f`) $ z
== (f a) . (f b) . (f c) $ z
并且
foldl f z [a, b, c]
== ((z `f` a) `f` b) `f` c
== (`f` c) . (`f` b) . (`f` a) $ z
== ((flip f) c) . ((flip f) b) . ((flip f) a) $ z
请注意,主要区别在于f
被翻转,组合顺序相反。
我们通常认为折叠是以某种方式“处理列表”; 我提倡的变化是,我们将它们视为由列表参数化的函数组合构建。
让我们从一个明显的离题开始。
简单组合
如果我们有一个函数列表a -> a
,我们可以将它们全部组合在一起,并获得一个新的函数a -> a
。 在foldr
方面,实现非常简单:
compose :: [a -> a] -> (a -> a)
compose = foldr (.) id
如果我们想要以相反的顺序组合它们,当然可以链接compose . reverse
,但是另一种方法是通过翻转(.)
来直接使用foldr
定义操作:
composeRev :: [a -> a] -> (a -> a)
composeRev = foldr (flip (.)) id
参数化组合
现在假设我们不是拥有一个函数列表[a -> a]
,而是拥有一个列表[b]
和一个函数b -> (a -> a)
,对于列表中的每个项目,它都会产生如上所述的函数a -> a
。我们可以将列表中的每个项目映射到其相应的函数,然后组合生成的函数列表:
compMap :: (b -> (a -> a)) -> [b] -> (a -> a)
compMap f = compose . map f
同样,这可以直接使用foldr
实现:
compMap f = foldr (\x chain -> f x . chain) id
= foldr ((.) . f) id
同样的,要进行反向组合,我们可以采用以下方法之一
compMapRev :: (b -> (a -> a)) -> [b] -> (a -> a)
compMapRev f = composeRev . map f
= compose . map f . reverse
= compMap f . reverse
或者用foldr
重新编写它:
compMapRev f = foldr (\x chain -> chain . f x) id
= foldr ((flip (.)) . f) id
回到折叠
回顾我们最初的小例子,我们可能会感觉到foldr
/foldl
和compMap
/compMapRev
之间存在强烈的关系。
如果我们对齐它们的类型签名,foldr
和compMap
之间的相似之处变得更加明显:
foldr :: (b -> (a -> a)) -> a -> [b] -> a
compMap :: (b -> (a -> a)) -> [b] -> a -> a
我们立即意识到,foldr
和compMap
只是它们的第二个和第三个参数翻转了,即foldr f == flip (compMap f)
,即foldr == flip . compMap
。
让我们看看是否可以用类似的方法来处理foldl
。这次我们必须记得将其与compMapRev
进行比较,因为组合顺序必须相同:
foldl :: (a -> b -> a) -> a -> [b] -> a
compMapRev :: (b -> (a -> a)) -> [b] -> a -> a
除了交换第二个和第三个参数之外,这次还翻转了第一个函数参数,即
foldl f == flip (compMapRev (flip f))
,即
foldl == flip . compMapRev . flip
。
前面的观察表明以下等式成立:
foldr f z list = compMap f list z
== foldr ((.) . f) id list z
foldl f z list = compMapRev (flip f) list z
= foldr ((flip (.)) . (flip f)) id list z
这最后一个正是我们一直在寻找的。
我们还可以简化和对齐这两个身份以突出相似之处:
foldr f == flip $ foldr ( (.) . f ) id
foldl f = flip $ foldr ((flip (.)) . (flip f)) id