## 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.

Pages: 1 2

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)…

In this data structure, cons, car and cdr

areO(1), notO(n). I’ve fixed the incorrect comment. Thanks.[…] Pages: 1 2 […]

A Haskell implementation: http://hamberg.no/erlend/posts/2012-08-29-purely-functional-random-access-list.html

[…] 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