在線性時間運行的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) 

如果你只是想知道它是如何在標準庫中完成的，你也可以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)