Implement reverse in Haskell that runs in linear time

I'm just learning Haskell, so sorry if my question is stupid. I'm reading learnyouahaskell.com and now I'm at chapter 5 "Recursion". There's an example of im开发者_StackOverflow中文版plementation of standard 'reverse' function:

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

But it seems that it runs in O(N^2) time, while the standard reverse runs in O(N) (I hope so). The following code illustrates this:

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

So, I started thinking how to implement my own reverse faster. It's pretty easy to do in imperative languages. Maybe I need some more advanced material from subsequent chapters to do this? Any hints are welcomed.

It can be implemented efficiently using an extra accumulator parameter, like the second parameter of fac in this example:

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

If you just want to know how it's done in the standard library, you can also look at the source code.

reverse is defined in the Prelude.

You can implement it as:

reverse = foldl (flip (:)) []

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

foldl (\acc x -> x:acc) [] xs

This runs in O(n). The idea is pretty simple - you take an empty list(accumulator) and transfer elements to it from top to bottom.