Thực hiện đảo ngược trong Haskell chạy trong thời gian tuyến tính

Question

Tôi chỉ học Haskell, vì vậy xin lỗi nếu câu hỏi của tôi là ngu ngốc. Tôi đang đọc learnyouahaskell.com và bây giờ tôi đang ở chương 5 "Đệ quy". Có một ví dụ về việc thực hiện các chức năng 'đảo ngược' tiêu chuẩn:

reverse' :: [a] -> [a] 
reverse' [] = [] 
reverse' (x:xs) = reverse' xs ++ [x] 

Nhưng dường như nó chạy trong thời gian O (N^2) thời gian, trong khi ngược lại tiêu chuẩn chạy trong thời gian O (N) (Tôi hy vọng như vậy). Mã sau đây minh họa điều này:

sum (reverse [1,2..1000000]) -- runs pretty fast 
sum (reverse' [1,2..1000000]) -- never finishes 

Vì vậy, tôi bắt đầu suy nghĩ cách thực hiện hoàn nguyên của riêng mình nhanh hơn. Nó khá dễ dàng để làm trong các ngôn ngữ mệnh lệnh. Có lẽ tôi cần một số tài liệu cao cấp hơn từ các chương tiếp theo để làm điều này? Bất kỳ gợi ý được hoan nghênh.

Answer 1

Nó có thể được thực hiện sử dụng một cách hiệu quả một tham số ắc thêm, giống như tham số thứ hai của fac trong ví dụ này:

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

Nếu bạn chỉ muốn biết làm thế nào nó được thực hiện trong thư viện chuẩn, bạn cũng có thể look at the source code.

Answer 2

reverse được xác định trong Prelude.

Bạn có thể thực hiện nó như:

reverse = foldl (flip (:)) [] 

Answer 3

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