在 Haskell 中实现以线性时间运行的反向操作

Question

我刚刚学习 Haskell，如果我的问题很愚蠢，我很抱歉。我正在阅读 learnyouahaskell.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)

如果您只是想知道它在标准库中是如何完成的，您也可以 查看源代码。

Answer 2

reverse 在 前奏。

您可以将其实现为：

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)。这个想法非常简单 - 您采用一个空列表（累加器）并从上到下将元素传输到其中。