Random Access Lists
August 28, 2012
The datatype Rlist
is a list of (int * α Tree)
, where an α Tree
is either a Leaf
of α
or a Node
of (α * α Tree * α Tree)
. We provide the following structures, where an item
is a single element of an Rlist
:
(define-structure leaf x)
(define-structure node x t1 t2)
(define-structure item w t)
The empty Rlist
is trivial:
(define empty (list))
(define empty? null?)
The cons
function, which we spell kons
to distinguish it from the built-in function on normal lists, adds a new item
if the Rlist
is empty or singleton, otherwise it builds a new Node
from the first two Item
s in the Rlist
:
(define (kons x ts)
(if (or (empty? ts) (empty? (cdr ts)))
(cons (make-item 1 (make-leaf x)) ts)
(let ((w1 (item-w (car ts))) (w2 (item-w (cadr ts)))
(t1 (item-t (car ts))) (t2 (item-t (cadr ts))))
(if (= w1 w2)
(cons (make-item (+ 1 w1 w2) (make-node x t1 t2)) (cddr ts))
(cons (make-item 1 (make-leaf x)) ts)))))
The head
and tail
functions look at the first item in the Rlist
and branch on whether it is a Leaf
or a Node
. Both functions are careful to report an error if handed an empty list. Note the “impossible” conditions, which were, sadly, very valuable during development of the functions:
(define (head ts)
(cond ((empty? ts) (error 'head "empty list"))
((leaf? (item-t (car ts)))
(if (= (item-w (car ts)) 1)
(leaf-x (item-t (car ts)))
(error 'head "impossible")))
((node? (item-t (car ts)))
(node-x (item-t (car ts))))
(else (error 'head "impossible"))))
(define (tail ts)
(cond ((empty? ts) (error 'tail "empty list"))
((leaf? (item-t (car ts)))
(if (= (item-w (car ts)) 1)
(cdr ts)
(error 'tail "impossible")))
((node? (item-t (car ts)))
(let* ((w (item-w (car ts))) (w2 (quotient w 2))
(t (item-t (car ts))) (ts (cdr ts))
(t1 (node-t1 t)) (t2 (node-t2 t)))
(cons (make-item w2 t1) (cons (make-item w2 t2) ts))))
(else (error 'tail "impossible"))))
That dispenses with the normal list functions of the random access lists, so it is a good time to stop and test what we have done:
> (define x (kons 7 empty))
> (set! x (kons 6 x))
> (set! x (kons 5 x))
> (set! x (kons 4 x))
> (set! x (kons 3 x))
> (set! x (kons 2 x))
> (set! x (kons 1 x))
> (set! x (kons 0 x))
> (head x)
0
> (head (tail x))
1
> (head (tail (tail x)))
2
Now we can continue with the random access part of the data structure. The lookup
function is similar to the list-ref
function of Scheme; it first finds the right item
in the Rlist
(which takes O(log n) time, since that’s the length of the Rlist
), then the auxiliary function lookup-tree
determines if the item
is a Leaf
or Node
and responds appropriately. Note that lookup
and update!
both check that subscripts are in range:
(define (lookup i ts)
(define (lookup-tree w i t)
(cond ((and (= w 1) (zero? i) (leaf? t))
(leaf-x t))
((and (= w 1) (leaf? t))
(error 'lookup-tree "subscript out of range"))
((and (zero? i) (node? t))
(node-x t))
((node? t)
(let ((w2 (quotient w 2)) (t1 (node-t1 t)) (t2 (node-t2 t)))
(if (<= i w2)
(lookup-tree w2 (- i 1) t1)
(lookup-tree w2 (- i 1 w2) t2))))
(else (error 'lookup-tree "impossible"))))
(cond ((empty? ts) (error 'lookup "subscript out of range"))
((< i (item-w (car ts)))
(let ((w (item-w (car ts))) (t (item-t (car ts))))
(lookup-tree w i t)))
(else (let ((w (item-w (car ts))))
(lookup (- i w) (cdr ts))))))
Update!
is similar to lookup
, except that it returns a newly-allocated Rlist
that shares item
s with its input:
(define (update! i y ts)
(define (update-tree w i y t)
(cond ((and (= w 1) (zero? i) (leaf? t))
(make-leaf y))
((and (= w 1) (leaf? t))
(error 'update-tree "subscript out of range"))
((and (zero? i) (node? t))
(make-node y (node-t1 t) (node-t2 t)))
((node? t)
(let ((w2 (quotient w 2)) (x (node-x t))
(t1 (node-t1 t)) (t2 (node-t2 t)))
(if (<= i w2)
(make-node x (update-tree w2 (- i 1) y t1) t2)
(make-node x t1 (update-tree w2 (- i 1 w2) y t2)))))
(else (error 'update-tree "impossible"))))
(cond ((empty? ts) (error 'update! "subscript out of range"))
((< i (item-w (car ts)))
(let ((w (item-w (car ts))) (t (item-t (car ts))))
(cons (make-item w (update-tree w i y t)) (cdr ts))))
(else (let* ((t (car ts)) (ts (cdr ts)) (w (item-w t)))
(cons t (update! (- i w) y ts))))))
It’s time for some more testing:
> (lookup 2 x)
2
> (set! x (update 2 12 x))
> (lookup 2 x)
12
> (head (tail (tail x)))
12
We used define-structure
from the Standard Prelude. The code is collected at http://programmingpraxis.codepad.org/CDtlf2Sy, but I couldn’t make it run; it runs fine on my machine at home, but something about the macros provided by MzScheme in the codepad system doesn’t work with this code.
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