使用foldl'和foldr进行列表连接

Question

我现在正在学习Haskell，遇到了以下问题：

我想使用foldl'和foldr重写++函数。 我已经使用foldr完成了它：

myConcat xs ys = foldr (:) ys xs

我无法使用 foldl' 完成这个任务。我在 RealWorldHaskell 中读到，foldr 对于做这种事情非常有用。 好的，但是我能否也使用 foldl 来编写一个等效于 ++ 的函数呢？如果可以的话，有人能向我展示如何实现吗（如果可以的话……书中没有提到任何相关内容）…… Haskell 的类型机制是否会阻止我这样做？每次尝试时，我都会得到一个类型错误……

- Adi

Answer 1

我猜你得到的错误是因为尝试简单地将foldr切换为foldl'：

myConcat xs ys = foldl' (:) ys xs

这会产生错误（使用我的 Hugs REPL）：

ERROR - Type error in application
*** Expression     : foldl' (:) xs ys
*** Term           : (:)
*** Type           : a -> [a] -> [a]
*** Does not match : [a] -> a -> [a]

注意最后两行（提供的类型和期望的类型），[a]和a的位置是相反的。这意味着我们需要一个函数，类似于(:)，但它接受的参数顺序相反。

Haskell有一个为我们完成此操作的函数：flip函数。基本上，flip等同于

flip :: (a -> b -> c) -> (b -> a -> c)
flip f y x = f x y

也就是说，flip 接收一个二元函数作为参数，并返回另一个将原始参数反转（"翻转"）的二元函数。因此，虽然 (:) 的类型为 a -> [a] -> [a]，但我们可以看到 flip (:) 的类型为 [a] -> a -> [a]，使它成为 foldl' 参数的完美选择。

使用 flip，我们现在有以下代码：

myConcat xs ys = foldl' (flip (:)) ys xs

这是因为 foldl' 具有类型 (a -> b -> c) -> a -> [b] -> c。

如果我们用参数 [1..5] 和 [6..10] 运行它，我们会得到一个结果 [5,4,3,2,1,6,7,8,9,10]，几乎是我们想要的。唯一的问题是第一个列表在结果中反向出现了。将一个简单的调用 reverse 添加进去就可以得到我们最终的 myConcat 定义：

myConcat xs ys = foldl' (flip (:)) ys (reverse xs)

审视这个过程，展示了在编写Haskell代码时经常出现的美好事物之一：当遇到问题时，您可以一步一步地解决它（小问题）。当您已经有一个工作实现，并且只是尝试编写另一个实现时，这一点尤其重要。需要注意的重要一点是，如果您更改实现的某个部分（在本例中，更改foldr为foldl'），则许多其他所需的更改将简单地落在类型定义中。剩下的几个问题是正确性问题，可以通过运行测试用例或查看使用的函数的确切性质来轻松找到。

PS：任何熟悉Haskell的人都可以更新一下最后一行代码，如果愿意的话。虽然它并不可怕，但我认为它并不太好看。不幸的是，我还不太擅长Haskell。

- Ken Wayne VanderLinde

---

你的帖子真的帮了我很多，感谢你的解释 :) - Adi

Answer 2

:运算符将一个单个元素（左参数）连接到列表（右参数）。 foldl的参数包括：

• 折叠函数
• 初始值
• 要处理的值的列表

特别要注意，折叠函数以当前值作为其左参数，该值最初是初始值。因此，折叠函数的左参数是一个列表，其右参数是一个单一值。如果您尝试一下，您可以得到像[仅通过交换参数来使类型匹配]之类的东西。

> foldl (\x y -> y:x) [1, 2, 3] [4, 5, 6]
[6,5,4,1,2,3]

但是，这并不是你想要的。你需要自己解决它；我能够使用foldl构建一个反转函数，并将其作为子程序调用--但如果你能找到其他解决方法，请随意尝试。

- gatoatigrado

---

你的解决方案非常优雅 :) 谢谢你帮助我理解。 - Adi

Answer 3

并非总是可能的，因为foldr（以及++）适用于无限列表，但foldl不适用。然而，foldl可以用foldr的方式编写：http://www.haskell.org/haskellwiki/Foldl_as_foldr 更新：对于有限列表，foldr也可以用foldl的方式编写：

foldr :: (b -> a -> a) -> a -> [b] -> a
foldr f a bs =
  foldl (\g b x -> g (f b x)) id bs a

所以，你可以通过使用foldl来实现(++)。

- newacct

Answer 4

data [] a = ... | a : [a]
(:) :: a -> [a] -> [a]

在IT技术中，(:)操作符通常会对左右两个操作数进行不同的处理。

a :: Char
b :: Char
c :: [Char]

a:[b] 可行

a:b 不可行

a:c 可行。

查找 foldr (:) 和 foldl (:) 的类型签名，您将发现它们之间的区别。

- wuxb

Answer 5

你可以使用foldl来实现，但与基于foldr的实现相比，效率不高。

使用foldl的示例：

show $ (\xs ys -> foldl­ (\s e -> e:s ) ys (reve­rse xs)) [1,2]­ [3,4]

- Ankur

---

foldr 为什么更高效？ - Jeffrey Benjamin Brown