在线性时间内运行的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)