4 Random Access Lists

Version: 5.0.1.6

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

4.2 Skew Binary Random Access List

4.1 Binary Random Access List

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

(length ral) → Integer

ral : (List A)

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

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

(reverse list) → (List A)

list : (List A)

Function reverse takes a list and returns a reversed list.

Example:
  > (->list (reverse (list 1 2 3 4 5 6)))
  - : (Listof Positive-Fixnum)
  '(6 5 4 3 2 1)

(map func lst1 lst2 ...) → (List A)

func : (A B ... B -> C)

lst1 : (List A)

lst2 : (List B)

Function map is similar to map for lists.

Examples:

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

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

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

- : (Listof Exact-Positive-Integer)

'(1 4 9 16 25 36)

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

(foldl func init lst1 lst2 ...) → C

func : (C A B ... B -> C)

init : C

lst1 : (List A)

lst2 : (List B)

Function foldl is similar to foldl.

foldl currently does not produce correct results when the given function is non-commutative.

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

(foldr func init lst1 lst2 ...) → C

func : (C A B ... B -> C)

init : C

lst1 : (List A)

lst2 : (List B)

Function foldr is similar to foldr.

foldr currently does not produce correct results when the given function is non-commutative.

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

(andmap func lst1 lst2 ...) → Boolean

func : (A B ... B -> Boolean)

lst1 : (List A)

lst2 : (List B)

Function andmap is similar to andmap.

Examples:
  > (andmap even? (list 1 2 3 4 5 6))
  - : Boolean
  #f
  > (andmap odd? (list 1 2 3 4 5 6))
  - : Boolean
  #f
  > (andmap positive? (list 1 2 3 4 5 6))
  - : Boolean
  #t
  > (andmap negative? (list -1 -2))
  - : Boolean
  #t

(ormap func lst1 lst2 ...) → Boolean

func : (A B ... B -> Boolean)

lst1 : (List A)

lst2 : (List B)

Function ormap is similar to ormap.

Examples:
  > (ormap even? (list 1 2 3 4 5 6))
  - : Boolean
  #t
  > (ormap odd? (list 1 2 3 4 5 6))
  - : Boolean
  #t
  > (ormap positive? (list -1 -2 3 4 -5 6))
  - : Boolean
  #t
  > (ormap negative? (list 1 -2))
  - : Boolean
  #t

(build-list size func) → (List A)

size : Natural

func : (Natural -> A)

Function build-list is similar to build-list.

Examples:

> (->list (build-list 5 (λ:([x : Integer]) (add1 x))))

- : (Listof Integer)

'(1 2 3 4 5)

> (->list (build-list 5 (λ:([x : Integer]) (* x x))))

- : (Listof Integer)

'(0 1 4 9 16)

(make-list size func) → (List A)

size : Natural

func : A

Function make-list is similar to make-list.

Examples:

> (->list (make-list 5 10))

- : (Listof Positive-Fixnum)

'(10 10 10 10 10)

> (->list (make-list 5 'sym))

- : (Listof 'sym)

'(sym sym sym sym sym)

(filter pred lst) → (List A)

pred : (A -> Boolean)

lst : (List A)

Function filter is similar to filter.

Examples:

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

> (->list (filter (λ:([x : Integer]) (> x 5)) lst))

- : (Listof Positive-Fixnum)

'(6)

> (->list (filter (λ:([x : Integer]) (< x 5)) lst))

- : (Listof Positive-Fixnum)

'(1 2 3 4)

> (->list (filter (λ:([x : Integer]) (<= x 4)) lst))

- : (Listof Positive-Fixnum)

'(1 2 3 4)

(remove pred lst) → (List A)

pred : (A -> Boolean)

lst : (List A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (->list (remove (λ:([x : Integer]) (> x 5)) (list 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

> (->list (remove (λ:([x : Integer]) (< x 5)) (list 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

> (->list (remove (λ:([x : Integer]) (<= x 4)) (list 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

(second lst) → A

lst : (List A)

Function second returns the second element of the list.

Example:
  > (second (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  2

(third lst) → A

lst : (List A)

Function third returns the third element of the list.

Example:
  > (third (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  3

(fourth lst) → A

lst : (List A)

Function fourth returns the fourth element of the list.

Example:
  > (fourth (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  4

(fifth lst) → A

lst : (List A)

Function fifth returns the fifth element of the list.

Example:
  > (fifth (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  5

(sixth lst) → A

lst : (List A)

Function sixth returns the sixth element of the list.

Example:
  > (sixth (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  6

(seventh lst) → A

lst : (List A)

Function seventh returns the seventh element of the list.

Example:
  > (seventh (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  7

(eighth lst) → A

lst : (List A)

Function eighth returns the eighth element of the list.

Example:
  > (eighth (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  8

(ninth lst) → A

lst : (List A)

Function ninth returns the ninth element of the list.

Example:
  > (ninth (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  9

(tenth lst) → A

lst : (List A)

Function tenth returns the tenth element of the list.

Example:
  > (tenth (list 1 2 3 4 5 6 7 8 9 10 11))
  - : Positive-Fixnum
  10

(last lst) → A

lst : (List A)

Function last returns the last element of the list.

Examples:
  > (last (list 1 2 3 4 5 6 7 8 9 10 11))
  - : Positive-Fixnum
  11
  > (last (list 1 2 3 4 5))
  - : Positive-Fixnum
  5

4.2 Skew Binary Random Access List

(require (planet krhari/pfds:1:5/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 (Pairof Integer (U (Leaf Positive-Fixnum) (Node Positive-Fixnum))))

(list (cons 3 (Node 1 (Leaf 2) (Leaf 3))) (cons 3 (Node 4 (Leaf 5) (Leaf 6))))

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 (Pairof Integer (U (Leaf Positive-Fixnum) (Node Positive-Fixnum))))

(list (cons 7 (Node 10 (Node 1 (Leaf 2) (Leaf 3)) (Node 4 (Leaf 5) (Leaf 6)))))

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 (Pairof Integer (U (Leaf Positive-Fixnum) (Node Positive-Fixnum))))

(list (cons 1 (Leaf 2)) (cons 1 (Leaf 3)) (cons 3 (Node 4 (Leaf 5) (Leaf 6))))

> (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 (Pairof Integer (U (Leaf Positive-Fixnum) (Node Positive-Fixnum))))
  (list (cons 3 (Node 4 (Leaf 5) (Leaf 6))))
  > (drop 0 (list 1 2 3 4 5 6))
  - : (Listof (Pairof Integer (U (Leaf Positive-Fixnum) (Node Positive-Fixnum))))
  (list (cons 3 (Node 1 (Leaf 2) (Leaf 3)))  (cons 3 (Node 4 (Leaf 5) (Leaf 6))))
  > (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.

(length ral) → Integer

ral : (List A)

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

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

(reverse list) → (List A)

list : (List A)

Function reverse takes a list and returns a reversed list.

Example:
  > (->list (reverse (list 1 2 3 4 5 6)))
  - : (Listof Positive-Fixnum)
  '(6 5 4 3 2 1)

(map func lst1 lst2 ...) → (List A)

func : (A B ... B -> C)

lst1 : (List A)

lst2 : (List B)

map currently works on only upto 3 lists because of some issues with contracts.

Function map is similar to map for lists.

Examples:

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

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

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

- : (Listof Exact-Positive-Integer)

'(1 4 9 16 25 36)

(foldl func init lst1 lst2 ...) → C

func : (C A B ... B -> C)

init : C

lst1 : (List A)

lst2 : (List B)

Function foldl is similar to foldl.

foldl currently does not produce correct results when the given function is non-commutative.

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

(foldr func init lst1 lst2 ...) → C

func : (C A B ... B -> C)

init : C

lst1 : (List A)

lst2 : (List B)

Function foldr is similar to foldr.

foldr currently does not produce correct results when the given function is non-commutative.

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

(andmap func lst1 lst2 ...) → Boolean

func : (A B ... B -> Boolean)

lst1 : (List A)

lst2 : (List B)

Function andmap is similar to andmap.

(ormap func lst1 lst2 ...) → Boolean

func : (A B ... B -> Boolean)

lst1 : (List A)

lst2 : (List B)

Function ormap is similar to ormap.

(build-list size func) → (List A)

size : Natural

func : (Natural -> A)

Function build-list is similar to build-list.

Examples:

> (->list (build-list 5 (λ:([x : Integer]) (add1 x))))

- : (Listof Integer)

'(1 2 3 4 5)

> (->list (build-list 5 (λ:([x : Integer]) (* x x))))

- : (Listof Integer)

'(0 1 4 9 16)

(make-list size func) → (List A)

size : Natural

func : A

Function make-list is similar to make-list.

Examples:

> (->list (make-list 5 10))

- : (Listof Positive-Fixnum)

'(10 10 10 10 10)

> (->list (make-list 5 'sym))

- : (Listof 'sym)

'(sym sym sym sym sym)

(filter pred lst) → (List A)

pred : (A -> Boolean)

lst : (List A)

Function filter is similar to filter.

Examples:

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

> (->list (filter (λ:([x : Integer]) (> x 5)) lst))

- : (Listof Positive-Fixnum)

'(6)

> (->list (filter (λ:([x : Integer]) (< x 5)) lst))

- : (Listof Positive-Fixnum)

'(1 2 3 4)

> (->list (filter (λ:([x : Integer]) (<= x 4)) lst))

- : (Listof Positive-Fixnum)

'(1 2 3 4)

(remove pred lst) → (List A)

pred : (A -> Boolean)

lst : (List A)

Function remove is similar to filter but remove removes the elements which match the predicate.

Examples:

> (->list (remove (λ:([x : Integer]) (> x 5)) (list 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5)

> (->list (remove (λ:([x : Integer]) (< x 5)) (list 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

> (->list (remove (λ:([x : Integer]) (<= x 4)) (list 1 2 3 4 5 6)))

- : (Listof Positive-Fixnum)

'(5 6)

(second lst) → A

lst : (List A)

Function second returns the second element of the list.

Example:
  > (second (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  2

(third lst) → A

lst : (List A)

Function third returns the third element of the list.

Example:
  > (third (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  3

(fourth lst) → A

lst : (List A)

Function fourth returns the fourth element of the list.

Example:
  > (fourth (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  4

(fifth lst) → A

lst : (List A)

Function fifth returns the fifth element of the list.

Example:
  > (fifth (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  5

(sixth lst) → A

lst : (List A)

Function sixth returns the sixth element of the list.

Example:
  > (sixth (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  6

(seventh lst) → A

lst : (List A)

Function seventh returns the seventh element of the list.

Example:
  > (seventh (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  7

(eighth lst) → A

lst : (List A)

Function eighth returns the eighth element of the list.

Example:
  > (eighth (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  8

(ninth lst) → A

lst : (List A)

Function ninth returns the ninth element of the list.

Example:
  > (ninth (list 1 2 3 4 5 6 7 8 9 10))
  - : Positive-Fixnum
  9

(tenth lst) → A

lst : (List A)

Function tenth returns the tenth element of the list.

Example:
  > (tenth (list 1 2 3 4 5 6 7 8 9 10 11))
  - : Positive-Fixnum
  10

(last lst) → A

lst : (List A)

Function last returns the last element of the list.

Examples:
  > (last (list 1 2 3 4 5 6 7 8 9 10 11))
  - : Positive-Fixnum
  11
  > (last (list 1 2 3 4 5))
  - : Positive-Fixnum
  5

← 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
11	Treap

4.1	Binary Random Access List
4.2	Skew Binary Random Access List