Okasaki, Chris, 1995. Purely functional random-access lists. FPCA '95: In Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture, Association for Computing Machinery, New York, NY, USA, pp. 86–95.
Abstract: We present a new data structure, called a random-access list, that supports array lookup and update operations in O(log n) time, while simultaneously providing O(1) time list operations (cons, head, tail). A closer analysis of the array operations improves the bound to O(min{i, log n}) in the worst case and O(log i) in the expected case, where i is the index of the desired element. Empirical evidence suggests that this data structure should be quite efficient in practice.