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.

4.1 Binary Random Access List

4.2 Skew Binary Random Access List

4.1 Binary Random Access List

(require (planet krhari/pfds:1:0/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.

(List A)

A binary random access list of type A.

(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 (planet krhari/pfds:1:0/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.

(List A)

A skew binary random access list type A.

(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