Version: 5.0.1.2

### 4Random 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.1Binary 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)) #

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 #f > (empty? empty) - : Boolean #t

 (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)) #

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 5 > (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)) # > (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)) # > (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)) # > (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.2Skew 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)) '(# #)

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 #f > (empty? empty) - : Boolean #t

 (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)) '(#)

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 1 > (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)) '(# # #) > (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)) '(#) > (drop 0 (list 1 2 3 4 5 6)) - : (Listof (Root Positive-Fixnum)) '(# #) > (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