On this page:
4.1 Binary Random Access List
list
empty
empty?
cons
first
rest
list-ref
list-set
->list
drop
list-length
4.2 Skew Binary Random Access List
list
empty
empty?
cons
first
rest
list-ref
list-set
->list
drop
list-length
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

 (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

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

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

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

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

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

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

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

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