haskell - 在可线性运行的Haskell中实现反向

我正在学习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

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

最佳答案

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

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

如果您只想知道标准库中的操作方式，也可以look at the source code。