Version: 5.0.1.3

4Random 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.1Binary Random Access List

 (require (planet krhari/pfds:1:2/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)) #

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

 (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

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

4.2Skew Binary Random Access List

 (require (planet krhari/pfds:1:2/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)) '(# #)

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

 (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) '(4 5 6 1 2 3)

 (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

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