4 Random Access Lists

Version: 5.0.1.2

4 Random Access Lists

Following Random Access List structures implement and provide the functions ralist, empty?, kons, head, tail, lookup, update, drop, list-length and ralist->list . Both are polymorphic and have the type (RAList A).

4.1 Binary Random Access List

4.2 Skew Binary Random Access List

4.1 Binary Random Access List

(require "binaryrandomaccesslist.ss")

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.

(list a ...) → (List A)

a : A

Function list creates a Binary Random Access List with the given inputs.

Example:

> (list 1 2 3 4 5 6)

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

#<Root>

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.

empty : (List Nothing)

A empty random access list

(empty? ral) → Boolean

ral : (List A)

Function empty? takes a Binary Random Access List checks if the given list is empty.

Examples:

> (empty? (list 1 2 3))

- : Boolean

> (empty? empty)

- : Boolean

(cons a ral) → (List A)

a : A

ral : (List A)

Function cons takes an element and a list and adds the given element to the front of the given list.

Example:

> (cons 10 (list 5 3 5 6))

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

#<Root>

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

(first ral) → A

ral : (List A)

Function first takes a list and returns the first element of the given list if its not empty else throws an error.

Examples:

> (first (list 5 3 5 6))

- : Positive-Fixnum

> (first empty)

head: given list is empty

(rest ral) → (List A)

ral : (List A)

Function rest takes a list and returns the given list but without its first element if the given list is not empty. If it is empty, rest throws an error

Examples:

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

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

#<Root>

> (rest empty)

tail: given list is empty

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

(list-ref ral index) → A

ral : (List A)

index : Integer

Function list-ref takes an integer(say n) and a list and gives the nth element of the given list. If the given n is larger than the size of the list, list-ref throws an error.

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

(list-set ral index newval) → (List A)

ral : (List A)

index : Integer

newval : A

Function list-set takes an integer(say n), list and a new element. And updates the nth element of the list with the new element.

Examples:
  > (list-set (list 1 2 3 4 5 6) 2 10)
  - : (U Null-RaList (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.

(->list ral) → (Listof A)

ral : (List A)

Function ->list takes a list and returns a list of elements which are in the same order as in the list.

Examples:

> (define ral (list 1 2 3 4 5 6))

> (->list ral)

- : (Listof Positive-Fixnum)

'(1 2 3 4 5 6)

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

(drop ral num) → (List A)

ral : (List A)

num : Integer

Function drop takes a list and an integer(say n) and drops the first n elements of the input list and returns the rest of the list.

Examples:
  > (drop 3 (list 1 2 3 4 5 6))
  - : (U Null-RaList (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.

(list-length ral) → Integer

ral : (List A)

Function list-length takes a list and gives the number of elements in in the given list.

Examples:
  > (list-length (list 1 2 3 4 5 6))
  - : Integer
  6
  > (list-length empty)
  - : Integer
  0

4.2 Skew Binary Random Access List

(require "skewbinaryrandomaccesslist.ss")

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.

(list a ...) → (List A)

a : A

Function list creates a Skew Binary Random Access List with the given inputs.

Example:

> (list 1 2 3 4 5 6)

- : (Listof (Root Positive-Fixnum))

'(#<Root> #<Root>)

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.

empty : (List Nothing)

A empty list.

(empty? ral) → Boolean

ral : (List A)

Function empty? takes a Skew Binary Random Access List checks if the given list is empty.

Examples:

> (empty? (list 1 2 3 4 5 6))

- : Boolean

> (empty? empty)

- : Boolean

(cons a ral) → (List A)

a : A

ral : (List A)

Function cons takes an element and a list and adds the given element to the front of the given list.

Example:

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

- : (Listof (Root Positive-Fixnum))

'(#<Root>)

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

(first ral) → A

ral : (List A)

Function first takes a list and returns the first element of the given list.

Examples:

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

- : Positive-Fixnum

> (first empty)

head: given list is empty

(rest ral) → (List A)

ral : (List A)

Function rest takes a list and returns a list without the first element of the given list.

Examples:

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

- : (Listof (Root Positive-Fixnum))

'(#<Root> #<Root> #<Root>)

> (rest empty)

tail: given list is empty

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

(list-ref ral index) → A

ral : (List A)

index : Integer

Function list-ref takes a list and an index(say n) and gives the nth element of the given list.

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

(list-set ral index newval) → (List A)

ral : (List A)

index : Integer

newval : A

Function list-set takes a list, an index(say n) and a new element and updates the nth element of the list with the new element.

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.

(->list ral) → (Listof A)

ral : (List A)

Function ->list takes a list and returns a list of elements which are in the same order as in the list.

Examples:

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

- : (Listof Positive-Fixnum)

'(1 2 3 4 5 6)

> (->list empty)

- : (Listof Nothing)

'()

(drop num ral) → (List A)

num : Integer

ral : (List A)

Function drop takes a list and an integer(say n) and drops the first n elements of the input list and returns the rest of the list.

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.

(list-length ral) → Integer

ral : (List A)

Function list-length takes a list and gives the number of elements in in the given list.

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

← prev up next →

1	Queues
2	Deques
3	Heaps
4	Random Access Lists
5	Catenable List
6	VList
7	Streams
8	Red-Black Trees
9	Tries
10	Sets

4.1	Binary Random Access List
4.2	Skew Binary Random Access List