A question concerning list accesses from a noobie functional programmer

Question

This might be a silly and obvious question, but why are list access algorithm examples implemented in linear time? I understand that most applications involve traversing lists rather than accessing them randomly, but what if you want to perform an access on a list with random accesses?

Answer 1

Because lists are by design a linear structure. They are the canonical recursive data type, defined as:

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

That is, either the empty list, or a cons node, consisting of an element, and a tail, which is also a list.

This structure precisely corresponds to inductive definitions in mathematics, and correspondingly, makes it trivial to write many functions as simple recursive calls.

The recursive data type does not admit random access in non-linear time, however. For that you need hardware support (which we all have), and a more sophisticated data type (or less sophisticated, depending on your viewpoint).

Summary: lists are computer science's encoding of induction as a recursive data structure. It's fundamental, you need it, but it doesn't do random access.

Answer 2

Haskell lists correspond to linked lists in imperative languages; they are inherently sequential since you only have access to the head and need to traverse to find other elements.

If you want random access you should choose some other data type. Perhaps from Data.Array or Data.IntMap.