What is the time complexity of a Haskell "tail" function?
I was reading a Haskell textbook while thinking about myself; what is the time complexity of a Haskell function tail
(and why)? (I cannot find the answer in any documentation)
I would assume that for a list of size n the function tail
would be O (n) i.e. will just copy the tail into a new list and return it. But then again, I'm not very good at basic Haskell architecture (I'm new to the language).
Of course I could this time. But I don't know yet how to get time in Haskell, and I also want to know how Haskell handles this problem in order to justify why it is O (n) / O (1) or whatever.
Thank you in advance:)
source to share
Haskell language is not specified. But in GHC (the most commonly used implementation) it's O (1). The tail doesn't need to be copied - it's safe to share between the original list and someone using only the tail of the list, because everything in Haskell is immutable.
Problem with calling: why init
, which stores everything but the last element of the list, works in O (n)? Why doesn't the sharing argument apply here?
source to share
Short answer: if the list has already been created before this node, O (1) .
A list in Haskell is a linked list . It is defined as:
data [a] = [] | a : [a]
So this means that either we have an empty list or a construct a : [a]
. So, a node with head
( a
) that refers to an object of type a
and a tail
that refers to a list [a]
(which could be an empty list or another node).
The source code tail
is base
defined as:
tail :: [a] -> [a]
tail (_:xs) = xs
tail [] = errorEmptyList "tail"
It runs in O (1) because we are just following the pointer to the "tail" of this node.
Remember, however, that Haskell is lazy . It's not that we get an object of the type [a]
that we have a materialized list: usually Haskell first has to evaluate the expression tree that was passed before the given node. This can lead to the evaluation of a complex and time consuming algorithm. So it depends on the expression tree you were provided with .
source to share