Implement reverse in Haskell that runs in linear time

reverse is defined in the Prelude.

You can implement it as:

reverse = foldl (flip (:)) []

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 l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

Related