为什么你可以用foldl反转列表,而不是在Haskell中使用foldr

Question

为什么你可以用foldl反转列表？

reverse' :: [a] -> [a]
reverse' xs = foldl (\acc x-> x : acc) [] xs

但是这个给了我一个编译错误.

reverse' :: [a] -> [a]
reverse' xs = foldr (\acc x-> x : acc) [] xs

错误

Couldn't match expected type `a' with actual type `[a]'
`a' is a rigid type variable bound by
  the type signature for reverse' :: [a] -> [a] at foldl.hs:33:13
Relevant bindings include
x :: [a] (bound at foldl.hs:34:27)
acc :: [a] (bound at foldl.hs:34:23)
xs :: [a] (bound at foldl.hs:34:10)
reverse' :: [a] -> [a] (bound at foldl.hs:34:1)
In the first argument of `(:)', namely `x'
In the expression: x : acc

Answer 1

每一个foldl都是foldr.

让我们记住这些定义.

foldr :: (a -> s -> s) -> s -> [a] -> s
foldr f s []       = s
foldr f s (a : as) = f a (foldr f s as)

这是列表的标准问题一步迭代器.我曾经让我的学生敲打桌子并唱"你用空名单怎么办？你做什么a : as"？这就是你分别弄清楚什么s和f是什么的方法.

如果你考虑发生了什么,你会发现它foldr有效地计算了大量的f a函数,然后将这些函数应用于s.

foldr f s [1, 2, 3]
= f 1 . f 2 . f 3 . id $ s

现在,让我们看看 foldl

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g t []       = t
foldl g t (a : as) = foldl g (g t a) as

这也是一个列表上的一步迭代,但是随着累加器的改变我们去了.让我们最后移动它,以便列表参数左边的所有内容保持不变.

flip . foldl :: (t -> a -> t) -> [a] -> t -> t
flip (foldl g) []       t = t
flip (foldl g) (a : as) t = flip (foldl g) as (g t a)

现在我们可以看到一步迭代,如果我们=向左移动一个地方.

flip . foldl :: (t -> a -> t) -> [a] -> t -> t
flip (foldl g) []       = \ t -> t
flip (foldl g) (a : as) = \ t -> flip (foldl g) as (g t a)

在每种情况下,我们计算如果我们知道累加器,我们将做什么,抽象\ t ->.因为[],我们会回来t.因为a : as,我们将处理尾部g t a作为累加器.

但现在我们可以flip (foldl g)变成一个foldr.摘要递归调用.

flip . foldl :: (t -> a -> t) -> [a] -> t -> t
flip (foldl g) []       = \ t -> t
flip (foldl g) (a : as) = \ t -> s (g t a)
  where s = flip (foldl g) as

现在我们很高兴将它变成一个foldrwhere类型s被实例化t -> t.

flip . foldl :: (t -> a -> t) -> [a] -> t -> t
flip (foldl g) = foldr (\ a s -> \ t -> s (g t a)) (\ t -> t)

所以s说"什么as会对累加器做什么",我们回馈\ t -> s (g t a)哪个是" a : as与累加器有什么关系".翻转.

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g = flip (foldr (\ a s -> \ t -> s (g t a)) (\ t -> t))

ETA-扩大.

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g t as = flip (foldr (\ a s -> \ t -> s (g t a)) (\ t -> t)) t as

减少flip.

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g t as = foldr (\ a s -> \ t -> s (g t a)) (\ t -> t) as t

所以我们计算"如果我们知道累加器我们会做什么",然后我们将它作为初始累加器.

对于高尔夫球来说,这有点适中.我们可以摆脱\ t ->.

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g t as = foldr (\ a s -> s . (`g` a)) id as t

现在让我使用>>>from 来反转该组合Control.Arrow.

foldl :: (t -> a -> t) -> t -> [a] -> t
foldl g t as = foldr (\ a s -> (`g` a) >>> s) id as t

也就是说,foldl计算一个大的反向组合.所以,例如,给定[1,2,3],我们得到

foldr (\ a s -> (`g` a) >>> s) id [1,2,3] t
= ((`g` 1) >>> (`g` 2) >>> (`g` 3) >>> id) t

"管道"从左边开始提供参数,所以我们得到了

((`g` 1) >>> (`g` 2) >>> (`g` 3) >>> id) t
= ((`g` 2) >>> (`g` 3) >>> id) (g t 1)
= ((`g` 3) >>> id) (g (g t 1) 2)
= id (g (g (g t 1) 2) 3)
= g (g (g t 1) 2) 3

如果你采取g = flip (:),t = []你得到

flip (:) (flip (:) (flip (:) [] 1) 2) 3
= flip (:) (flip (:) (1 : []) 2) 3
= flip (:) (2 : 1 : []) 3
= 3 : 2 : 1 : []
= [3, 2, 1]

那是,

reverse as = foldr (\ a s -> (a :) >>> s) id as []

通过实例化to 的一般转换.foldlfoldr

仅适用于数学社会.做cabal install newtype和导入Data.Monoid,Data.Foldable和Control.Newtype.添加悲惨的实例:

instance Newtype (Dual o) o where
  pack = Dual
  unpack = getDual

观察到,一方面,我们可以实现foldMap通过foldr

foldMap :: Monoid x => (a -> x) -> [a] -> x
foldMap f = foldr (mappend . f) mempty

但反之亦然

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f = flip (ala' Endo foldMap f)

因此,foldr积累在组成内功能的幺半群中,但现在要得到foldl,我们告诉foldMap在Dual幺半群中工作.

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl g = flip (ala' Endo (ala' Dual foldMap) (flip g))

什么是mappend对Dual (Endo b)？Modulo包装,它正是反向组合,>>>.

Answer 2

首先,类型签名不排队:

foldl :: (o -> i -> o) -> o -> [i] -> o
foldr :: (i -> o -> o) -> o -> [i] -> o

所以,如果你交换你的参数名称:

reverse' xs = foldr (\ x acc -> x : acc) [] xs

现在它编译.它不起作用,但它现在编译.

事情是,foldl从左到右(即向后)工作,而foldr从右到左(即向前)工作.这就是为什么foldl让你逆转一个清单; 它以相反的顺序递给你东西.

说完了这一切,你就可以做到

reverse' xs = foldr (\ x acc -> acc ++ [x]) [] xs

然而,它会非常缓慢.(二次复杂度而不是线性复杂度.)

Answer 3

你可以用来有效foldr地反转列表(好吧,GHC 7.9中的大部分时间 - 它依赖于一些编译器优化),但它有点奇怪:

reverse xs = foldr (\x k -> \acc -> k (x:acc)) id xs []

我写了一篇关于Haskell Wiki如何工作的解释.

Answer 4

foldr基本上以规范的方式解构列表:foldr f initial与具有模式的函数相同:( ^{这基本上是foldr 的定义)}

 ff [] = initial
 ff (x:xs) = f x $ ff xs

即它逐个取消元素并将它们提供给它们f.好吧,如果一切f都是让他们再次回来,那么你得到你原来的名单!(另一种说法:foldr (:) [] ? id.

foldl以相反的顺序"解构"列表,所以如果你收回元素,你会得到反向列表.要获得相同的结果foldr,您需要追加到"错误"的结尾 - 无论是MathicalOrchid显示,效率低下++还是使用差异列表:

reverse'' :: [a] -> [a]
reverse'' l = dl2list $ foldr (\x accDL -> accDL ++. (x:)) empty l

type DList a = [a]->[a]
(++.) :: DList a -> DList a -> DList a
(++.) = (.)
emptyDL :: DList a
emptyDL = id
dl2list :: DLList a -> [a]
dl2list = ($[])

这可以紧凑地写成

reverse''' l = foldr (flip(.) . (:)) id l []

Answer 5

这就是foldl op acc具有 6 个元素的列表的作用：

(((((acc `op` x1) `op` x2) `op` x3) `op` x4) `op` x5 ) `op` x6

虽然foldr op acc这样做：

x1 `op` (x2 `op` (x3 `op` (x4 `op` (x5 `op` (x6 `op` acc)))))

当你看到这个时，很明显，如果你想foldl反转列表，op应该是一个“将右操作数粘在左操作数的开头”的操作符。这只是(:)参数颠倒，即

reverse' = foldl (flip (:)) []

（这与您的版本相同，但使用内置函数）。

当您想foldr反转列表时，您需要一个“将左操作数粘贴到右操作数的末尾”运算符。我不知道有什么内置函数可以做到这一点；如果你愿意，你可以把它写成flip (++) . return.

reverse'' = foldr (flip (++) . return) []

或者如果你更喜欢自己写

reverse'' = foldr (\x acc -> acc ++ [x]) []

不过这会很慢。