What Time Complexity Does Haskell's "tail"-Function Have?

Question

I was reading a tutorial on Haskell when I thought to myself; what time complexity does Haskell's tail function have (and why)? (I cannot find an answer in any documentation)

I would guess that for a list of size n, the tail function would be O(n), i.e just copying over the tail to a new list and returning that one. But then again, I do not know too much about the underlying architecture of Haskell (I'm new to the language).

Of course, I could time it. But I don't know how to time stuff in Haskell yet, and I also want to learn how Haskell handles the problem, to justify why it is O(n)/O(1) or whatever.

Thanks in advance :)

Answer 1

Haskell the language doesn't specify. But in GHC (the most frequently used implementation), it is O(1). The tail does not need to be copied -- it is safe to share between the original list and whoever uses just the tail of the list -- because everything in Haskell is immutable.

Challenge problem: why does init, which keeps all but the last element of a list, run in O(n)? Why doesn't the sharing argument above apply there?

Answer 2

Short answer: if the list is already constructed up to that node, O(1).

A list in Haskell is a linked list. It is defined as:

data [a] = [] | a : [a]

So that means that either we have the empty list, or the a : [a] construct. So a node with a head (the a) that refers to an object of type a, and a tail that refers to a list [a] (which can be the empty list, or another node).

The source code of the tail in base is defined as:

tail                    :: [a] -> [a]
tail (_:xs)             =  xs
tail []                 =  errorEmptyList "tail"

It runs in O(1) since we simply follow the pointer to the "tail" of that node.

Mind however that Haskell works lazily. It is not because we get an object of type [a] that we have a materialized list: usually Haskell will first have to evaluate the expression tree it has been given up to the given node. This can result in evaluating a complex and time consuming algorithm. So it depends on the expression tree you have been given.