如何将foldl与操作员一起使用

Question

我认为两个代码应该正确运行

foldr (:) [] [1..5]
foldl (:) [] [1..5]

但是我会出现错误使用foldl：

Occurs check: cannot construct the infinite type: a ~ [a]
Expected type: [a] -> [a] -> [a]
Actual type: a -> [a] -> [a]
Relevant bindings include it :: [a] (bound at <interactive>:253:1)
In the first argument of ‘foldl’, namely ‘(:)’
In the expression: foldl (:) [] [1 .. 5]

为什么不运行foldl？

Answer 1

foldl和 foldr的类型签名在函数参数中略有不同（他们已经切换了参数）：

foldl :: (b -> a -> b) -> b -> t a -> b
foldr :: (a -> b -> b) -> b -> t a -> b

对于foldl工作，您可以使用 flip交换函数的参数：

flip :: (a -> b -> c) -> b -> a -> c

即。这应该有效：

foldl (flip (:)) [] [1..5]

Answer 2

理解它的另一种方法是：

foldr (:) [] [1..5]

表示

1 : (2 : (3 : (4 : (5 : []))))

而

foldl (:) [] [1..5]

表示

(((([] : 1) : 2) : 3) : 4) : 5

后者毫无意义：是使用数字，就好像它们是列表一样。此外，:的每种用法都会更改输出的类型（[]是列表，[]:x是列表列表，([]:x):y是列表的名单列表，等等）。

<</p>

Answer 3

让我们从其方程式开始：

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl op z [] = z
foldl op z (x:xs) = foldl op (op z x) xs

foldr和foldl之间的最大区别是操作员op的工作方式：foldl是尾部递归，并且与foldr相比，从左到右应用操作员。

所以，您可能想要的是：

foldl ((currentFold, element) -> element:currentFold) [] [1,2,3,4,5]

可以使用flip（如@mschmidt指出）

来美化的

回想一下foldr方程式：

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr op z [] = z
foldr op z (x:xs) = op x (foldr op z xs)

它会略有不同：

foldr ((element, currentFold) -> element:currentFold) [] [1,2,3,4,5]

与您发布的那个相同：

foldr (:) [] [1,2,3,4,5]