如何在 Haskell 中编写反向函数

Question

所以，我知道，在 Haskell 中有一个用于反转列表的内置函数，但我正在尝试编写自己的小函数，只是为了练习一些 Haskell。我想到了以下代码，遗憾的是它不起作用。你们能告诉我我做错了什么吗？

    rev :: [Int] -> [Int]
    rev [] = []
    rev [x] = last [x] : rev init [x]

Answer 1

你几乎成功了。

rev :: [Int] -> [Int]
rev [] = []
rev x = last x : rev (init x)

解释：[x]是一个包含x的列表，而您想直接对x进行操作

ps。这是 documentation for Data.List。记得 import Data.List

Answer 2

嗯，你可以这样做：

rev :: [Int] -> [Int]
rev [] = []
rev (x:l) = (rev l) ++ [x]

第 3 行从列表中取出第一个元素，然后创建一个仅包含该元素的列表。这附加到递归 rev l 调用的结果。

Answer 3

如果你想高效地做到这一点，我建议你使用累加器：

rev :: [a] -> [a]
rev xs = go xs []
   where
   go :: [a] -> [a] -> [a]
   go []     ys = ys
   go (x:xs) ys = go xs (x:ys)

函数 go 在每一步中从第一个列表 xs 中删除一个元素并将其添加到第二个列表 ys 之前。这类似于从堆栈中弹出并推入另一个堆栈——顺序颠倒。

由于我们在每次递归调用中只使用固定的时间，所以我们得到 O(n) 的复杂度，其中 n 是列表长度。

相反，如果在每次递归调用中我们使用 last 或追加 ... ++ [x]，我们为每次调用支付 O(n)，因此整体 O(n^2)。

How to write a a reverse function in Haskell