Random Access Lists
August 28, 2012
Lists are ubiquitous in programming, especially in languages like Scheme, but elsewhere as well. Their primary advantage over arrays is that they can easily grow as needed, but that brings a corresponding disadvantage: it takes O(n) time to access the nth item in a list, but only O(1) time to access the nth item an an array.
Chris Okasaki has invented a remarkably clever data structure that provides the normal O(1) time complexity for the cons, head and tail operators of lists but reduces random access to the nth item in a list to O(log n), which means lists can sometimes be used in place of arrays, especially when it is inconvenient to determine the size of the array in advance or when the items of the array are normally accessed in sequence.
I won’t try to explain Okasaki’s data structure here; you can look at http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.5156 for the details, or look at Figure 9.7 in Okasaki’s book Purely Functional Data Structures, as I did.
Your task is to implement a library for random access lists, including the functions cons, head, tail, lookup and update. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Your link appears to be broken (as in the page loads, but the PDF link from there doesn’t work), but you can get a copy here
Hmmm. Works for me.
Ah, oops. The direct link ([www.cs.columbia.edu]) doesn’t work (for me), but the PDF link () works fine.
(There was supposed to be an image there, but it got stripped out. Just imagine a black and white PDF icon.)
I expect CONS, CAR and CDR to be O(1), not O(n)…
[…] Pages: 1 2 […]
A Haskell implementation: http://hamberg.no/erlend/posts/2012-08-29-purely-functional-random-access-list.html
In this data structure, cons, car and cdr are O(1), not O(n). I’ve fixed the incorrect comment. Thanks.
[…] time around, Programming Praxis had a challenge to take the algorithm presented in Chris Okasaki’s 1995 paper Purely Functional Random-Access […]
After all that noise above, I figured that I should actually go about implementing it. I’ve got a version here that is pretty much a direct translation from the paper’s ML (I think) to Scheme. I’m strongly reminded of skip lists, just with a better way for dynamically resizing.
My implementation in Common Lisp