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 implementation 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.