在Haskell中实现线性时间运行的反转功能

Question

我刚开始学习Haskell，如果我的问题很傻，请见谅。我正在阅读learnyouahaskell.com的第五章“递归”。其中有一个标准‘reverse’函数实现的例子：

reverse' :: [a] -> [a]  
reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x]  

但似乎它的运行时间是O(N^2)，而标准的反转是O(N)（我希望是这样）。以下代码说明了这一点：

sum (reverse [1,2..1000000]) -- runs pretty fast
sum (reverse' [1,2..1000000]) -- never finishes

所以，我开始思考如何更快地实现自己的反转。在命令式语言中做这件事很容易。也许我需要一些更高级的材料来完成这个任务？欢迎任何提示。

- rem

Answer 1

可以使用额外的累加器参数来有效地实现，就像这个例子中fac的第二个参数一样：

factorial n = fac n 1
  where
    fac 0 r = r
    fac n r = fac (n-1) (r*n)

如果你只想知道标准库中如何实现这个功能，你也可以查看源代码。

- sth

Answer 2

reverse 在 Prelude 中定义。

你可以这样实现它：

reverse = foldl (flip (:)) []

- Kru

---

这个问题是否会受到 foldl 的经典堆栈问题的影响？ - Elliot Cameron

Kru提供的版本直接来自源代码。请注意，列表的内容不会被评估，只有它们的位置会被考虑。此外，如果您不使用整个反转列表，则该列表永远不会被创建。 - Sean Perry

@3noch 我认为这是 foldr 的情况，但不是 foldl。 - symbiont

我想评论一下，这实际上是由OP所猜测的“来自后续章节的更高级材料”的情况。特别是这个实现在章节“高阶函数”中讨论，http://learnyouahaskell.com/higher-order-functions，子章节“只有折叠和马”。 - Sergey Dovgal

Answer 3

reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

- Ricardo Zorio

---

这个来自 GHC 源代码的是哪一个？https://downloads.haskell.org/~ghc/6.12.1/docs/html/libraries/base-4.2.0.0/src/GHC-List.html#reverse。 - Adam Stelmaszczyk

Answer 4

foldl (\acc x -> x:acc) [] xs

这个运行时间为O(n)。思路非常简单 - 你需要取一个空列表(累加器)并将元素从上到下转移至其中。

- Abhijit Gupta