CODEWITHSUNDEEP
haskellperformancecomplexity-theory
rem
rem

Reputation: 243

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

Upvotes: 19

Views: 13522

Answers (4)

Abhijit Gupta
Abhijit Gupta

Reputation: 21

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.

Upvotes: 1

Ricardo Zorio
Ricardo Zorio

Reputation: 292

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

Upvotes: 10

sth
sth

Reputation: 229754

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.

Upvotes: 23

Kru
Kru

Reputation: 4235

reverse is defined in the Prelude.

You can implement it as:

reverse = foldl (flip (:)) []

Upvotes: 15

Related Questions