4 Random Access Lists

Following Random Access List structures implement and provide the functions list, empty?, cons, head, tail, list-ref, list-set, drop, list-length and ->list. The implementations of the two data structures are based on numerical representations. Binary random access lists uses the binary number representation and running time of its basic list and random access operations, in worst-case, is logarithmic. Where as skew binary random access lists use skew binary number representation and running time of its basic operations is constant in worst-case. And both the implementations are polymorphic. And our benchmarks indicate that the operations of skew binary random access lists are faster.

4.1 Binary Random Access List

(require (planet krhari/pfds:1:2/binaryrandomaccesslist))

Random Access Lists are list data structures that provide array-like lookup and update operations. They have been implemented as a framework of binary numerical representation using complete binary leaf trees. It has a worst case running time of O(log(n)) for the operations cons, first, rest, list-ref and list-set.

In the above example, (list 1 2 3 4 5 6) gives a Binary Random Access List which is similar to lists but comes with efficient list-ref and list-set operations.

In the above example, (cons 10 (list 5 3 5 6)) returns (list 10 5 3 5 6).

In the above example, (rest ral) returns the rest of the given list, (list 2 3 4 5 6).

Examples:

> (list-ref (list 12 5 3 2 15 23) 4)

- : Positive-Fixnum

15

> (list-ref (list 12 5 3 2 15 23) 10)

list-ref: given index out of bound

Examples:

> (list-set (list 1 2 3 4 5 6) 2 10)

- : (U Null (Root Positive-Fixnum))

#<Root>

> (list-set (list 1 2 3 4 5 6) 10 15)

list-set: given index out of bound

In the above example, (list-set (list 1 2 3 4 5 6) 2 10) returns (list 1 2 10 4 5 6) and (list-set (list 1 2 3 4 5 6) 10 15) throws an error.

In the above example, (->list ral) returns (list 1 2 3 4 5 6).

Examples:

> (drop 3 (list 1 2 3 4 5 6))

- : (U Null (Root Positive-Fixnum))

#<Root>

> (drop 10 (list 1 2 3 4 5 6))

drop: not enough elements to drop

In the above example, (drop 3 (list 1 2 3 4 5 6)) returns the list (list 4 5 6). (drop 10 (list 1 2 3 4 5 6)) throws an error since 10 is larger than the number of elements in the list.

Examples:

> (list-length (list 1 2 3 4 5 6))

- : Integer

6

> (list-length empty)

- : Integer

0

Example:

> (->list (reverse (list 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(6 5 4 3 2 1)

In the above example, (map add1 (list 1 2 3 4 5 6)) adds 1 to each element of the given list and returns (list 2 3 4 5 6 7). (map * (list 1 2 3 4 5 6) (list 1 2 3 4 5 6)) multiplies corresponding elements in the two lists and returns the list (list 1 4 9 16 25 36).

Examples:

> (foldl + 0 (list 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (foldl * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400

Examples:

> (foldr + 0 (list 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (foldr * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400

4.2 Skew Binary Random Access List

(require (planet krhari/pfds:1:2/skewbinaryrandomaccesslist))

Random Access Lists are list data structures that provide array-like lookup and update operations. Skew Binary Random Access Lists are implemented using skew binary numbers. It provides a worst case running time of O(1) for the operations cons, first and rest and O(log(n)) for the operations list-ref and list-set.

In the above example, (list 1 2 3 4 5 6) gives a Skew Binary Random Access List which is similar to lists and has efficient lookup and update operations.

In the above example, (cons 10 (list 1 2 3 4 5 6)) returns a (list 10 1 2 3 4 5 6).

In the above example, (rest (list 1 2 3 4 5 6)) returns the (list 2 3 4 5 6).

Examples:

> (list-ref (list 1 2 3 4 5 6) 0)

- : Positive-Fixnum

1

> (list-ref (list 1 2 3 4 5 6) 3)

- : Positive-Fixnum

4

> (list-ref (list 1 2 3 4 5 6) 10)

list-ref: given index out of bounds

Examples:

> (->list (list-set (list 1 2 3 4 5 6) 3 10))

- : (Listof Positive-Fixnum)

'(1 2 3 10 5 6)

> (->list (list-set (list 1 2 3 4 5 6) 6 10))

list-set: given index out of bounds

In the above example, (list-set (list 1 2 3 4 5 6) 3 10) returns (list 1 2 3 10 5 6), (list-set (list 1 2 3 4 5 6) 6 10) throws an error since there are only six elements in the list and it is trying to update seventh element.

Examples:

> (drop 3 (list 1 2 3 4 5 6))

- : (Listof (Root Positive-Fixnum))

'(#<Root>)

> (drop 0 (list 1 2 3 4 5 6))

- : (Listof (Root Positive-Fixnum))

'(#<Root> #<Root>)

> (drop 10 (list 1 2 3 4 5 6))

drop: not enough elements to drop

In the above example, (drop 3 (list 1 2 3 4 5 6) 3) returns (list 4 5 6). (drop 0 (list 1 2 3 4 5 6)) returns the (list 1 2 3 4 5 6). If the given n is larger than the number of elements in the list, then it throws an error.

Examples:

> (list-length (list 1 2 3 4 5 6))

- : Integer

6

> (list-length (list 1 2 3))

- : Integer

3

> (list-length empty)

- : Integer

0

Example:

> (->list (reverse (list 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(4 5 6 1 2 3)

In the above example, (map add1 (list 1 2 3 4 5 6)) adds 1 to each element of the given list and returns (list 2 3 4 5 6 7). (map * (list 1 2 3 4 5 6) (list 1 2 3 4 5 6)) multiplies corresponding elements in the two lists and returns the list (list 1 4 9 16 25 36).

Examples:

> (foldl + 0 (list 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (foldl * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400

Examples:

> (foldr + 0 (list 1 2 3 4 5 6))

- : Exact-Nonnegative-Integer

21

> (foldr * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))

- : Exact-Positive-Integer

518400