Purely Functional Random Access Lists by Chris Okasaki.

The problem this paper addresses is that in the traditional functional lists, accessing the ith element requires log(i) time. The approach proposed in this paper reduces lookup and update operations to log(n).

The idea is to represent a list with a list of full binary trees. A pre-order traversal of the trees gives a linear sequence of all the elements in the list. The whole list is broken into full binary trees by a greedy decomposition, with the sizes of the trees in ascending order. The cons operation distinguish several patterns and remains the invariant. The tail operation trivially keeps the invariant.

Drawbacks we have observed:

• Can not do a usual pattern matching on lists. There is a concept of views proposed in Haskell community which has not become an extention to the language yet. But it might be a solution.
• Seems to me that it does not achieve the ++ operation with the same time complexity. Consider concatenating two lists of length 7 and 1 respectively, say [0,1,2,3,4,5,6] and [7]. They are represented as:

  [    0      ] ++ [7] = [0,     1      ]
     /   \                     /   \
    1     4                   2     5
   / \   / \                 / \   / \
  2   3 5   6               3   4 6   7
  

  Basically all the elements are “shuffled”. However, with lazy evaluation, there might be a better amortized time complexity.