在Haskell中以线性时间执行反向运算

Question

我正在学习Haskell，如果我的问题很愚蠢，请抱歉。我正在阅读learningyouahaskell.com，现在在第5章“递归”。有一个实现标准“反向”功能的示例：

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

因此，我开始思考如何更快地实现自己的反向。使用命令式语言很容易做到。也许我需要后续章节中的一些更高级的材料来做到这一点？欢迎任何提示。

Answer 1

可以使用一个额外的累加器参数来有效地实现，例如本例中的fac的第二个参数：

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

如果只想知道它在标准库中是如何完成的，也可以look at the source code。

Answer 2

[reverse在Prelude中定义。

您可以将其实现为：

reverse = foldl (flip (:)) []

Answer 3

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

Answer 4

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

这在O（n）中运行。这个想法非常简单-您可以使用一个空列表（累加器）并将元素从上到下传输到该列表。