这个基于foldl的函数"Myreverse = foldl(flip(:))[]"如何工作？

Question

我正在学习Haskell，并尝试编写自己的反转函数，但不使用递归。

这个解决方案是这个函数：

myreverse = foldl (flip (:)) []

我正在尝试理解在评估以下内容时会发生什么:

myreverse [1..5]

我不明白 flip 在这里的作用。有人能写下这里发生了什么，并逐步解释吗？

- basti12354

---

我不明白这里的 flip 是做什么的。如果你把 (:) 写成 lambda 形式：\x xs -> x : xs，可能会更有帮助。如果你将 flip 应用于这个 lambda，得到的函数是 \xs x -> x : xs。 - jub0bs

专业提示：在列表模块中使用foldl'而不是foldl。除非你正在解决一些疯狂的虚构问题，否则普通的foldl永远不是最佳选择。 - hugomg

@hugomg，我认为在这种情况下应该完全没问题。flip（:)不进行任何实际计算，因此我希望GHC将其视为构造函数。但是，您必须进行测试以确保。 - dfeuer

Answer 1

翻转函数非常简单：

如果有一个函数f :: a -> b -> c，那么flip f是一个函数:: b -> a -> c，它会返回一个新函数并且翻转您需要传递的参数顺序。

(:) :: a -> [a] -> [a]是这种模式的函数，因此flip (:)现在将首先获取即将成为尾部的元素，然后是新的头部元素，并返回一个包含这些元素的新列表：

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

现在你需要这个是因为foldl是这样定义的:

foldl :: (b -> a -> b) -> b -> [a] -> b

你需要传递的函数应该是先接收一个列表，然后接收一个元素，并返回一个新列表。这将把所有内容都折叠成以下形式：

myreverse [1..5]
= foldl (flip (:)) [] [1,2,3,4,5]
= foldl (flip (:)) (((flip (:)) [] 1)) [2,3,4,5]
= foldl (flip (:)) (1:[]) [2,3,4,5]
= foldl (flip (:)) (((flip (:)) [1] 2)) [3,4,5]
= foldl (flip (:)) (2:[1]) [3,4,5]
= ...
= [5,4,3,2,1]

- Random Dev

---

小小的反对：foldl 不会导致范围从开头完全评估。 - jub0bs

当然可以 - 但我认为如果我写下这个序列并寻找所有惰性部分，这将变得非常混乱且几乎无法阅读 - 我希望缩进和flip、(:)和foldl的工作方式能更明显。 - Random Dev

没问题，你毕竟写了“类似这样”的东西。 - jub0bs

Answer 2

您可以在ghci中尝试使用flip命令来理解它的作用：

:t (:)
(:) 1 [2..4]

[1,2,3,4]

:t flip (:)
(flip (:)) [2..4] 1

[1,2,3,4]

- daniel.kahlenberg