Time complexity for haskell function

Question

is there a simple way to control time complexity of functions in haskell?

I have constructed a function that reverses a list of any type, the goal is to have it in linear time complexity which i have attempted to solve like this:

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

my intetion is to have it linear, O(n), but i am unsure if it actually is and would therefore like use some type of tool that might analyze the code/function to show that it is infact linear.

i would thus like to know:

Is this function linear? can i show it with any analyzing tools?

Answer 1

(…) have it linear, O(n), but i am unsure if it actually is and would therefore like use some type of tool that might analyze the code/function to show that it is infact linear.

The function is not linear. The append function (++) :: [a] -> [a] -> [a] is linear. Since we do this for each element in the list, we end up with O(n²) time complexity.

What we can do to make this a linear function is use an accumulator: an extra parameter that we use that each time will be passed in an update form:

myrev :: [a] -> [a]
myrev = (`go` [])
  where go (x:xs) ys = go xs (x:ys)
        go [] ys = ys

We thus start the accumulator with an empty list. For each element in the original list x we pop it from the first list, and push it to the second list. When the first list is exhausted, then ys contains the list in reverse.