Version: 5.0.1.3

### 6VList

 (require (planet krhari/pfds:1:3/vlist))

A VList is a data structure very similar to noraml Scheme List but the corresponding operations are significantly faster for most of the List operations. Indexing and length operations have a running time of O(1) and O(lg N) respectively compared to O(N) in lists. The data structure has been described in the paper Fast Functional Lists, Hash-Lists, vlists and Variable Length Arrays by Phil Bagwell. VLists implementation internally uses Skew Binary Random Access List.

 (List A)
A vlist type A.

 (list a ...) → (List A) a : A
Function list creates a vlist with the given inputs.

 Example: > (list 1 2 3 4 5 6) - : (List Positive-Fixnum) #

In the above example, the vlist obtained will have 1 as its first element.

 empty : (List Nothing)
An empty vlist.

 (empty? vlst) → Boolean vlst : (List A)
Function empty? checks if the given vlist is empty or not.

 Examples: > (empty? (list 1 2 3 4 5 6)) - : Boolean #f > (empty? empty) - : Boolean #t

 (cons a vlst) → (List A) a : A vlst : (List A)
Function cons takes an element and a vlist and adds the given element to the vlist.
 Example: > (cons 10 (list 1 2 3 4 5 6)) - : (List Positive-Fixnum) #

In the above example, cons adds the element 10 to (list 1 2 3 4 5 6) and returns (list 10 1 2 3 4 5 6).

 (first vlst) → A vlst : (List A)
Function first takes a vlist and gives the first element of the given vlist if vlist is not empty else throws an error.

 Examples: > (first (list 1 2 3 4 5 6)) - : Positive-Fixnum 1 > (first empty) first: given vlist is empty

 (last vlst) → A vlst : (List A)
Function last takes a vlist and gives the last element in the vlist if vlist is not empty else throws an error.
 Examples: > (last (list 1 2 3 4 5 6)) - : Positive-Fixnum 6 > (last empty) last: given vlist is empty

 (rest vlst) → (List A) vlst : (List A)
Function rest takes a vlist and returns a vlist without the first element if the given vlist is not empty. Else throws an error.

 Examples: > (rest (list 1 2 3 4 5 6)) - : (List Positive-Fixnum) # > (rest empty) rest: given vlist is empty

In the above example, (rest (list 1 2 3 4 5 6)), removes the head and returns (list 2 3 4 5 6).

 (list-ref vlst index) → A vlst : (List A) index : Integer
Function list-ref takes a vlist and an index(say n) and gives the nth element of the given vlist

 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

 (length vlst) → Integer vlst : (List A)
Function length takes a vlist and gives the number of elements in the given vlist.

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

 (->list vlst) → (Listof A) vlst : (List A)
Function ->list takes a vlist and returns a normal scheme list.
 Examples: > (->list (list 1 2 3 4 5 6)) - : (Listof Positive-Fixnum) '(1 2 3 4 5 6) > (->list empty) - : (Listof Nothing) '()

 (reverse vlst) → (List A) vlst : (List A)
Function reverse takes a vlist and returns a reversed vlist.

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

 (map func vlst1 vlst2 ...) → (List A) func : (A B ... B -> C) vlst1 : (List A) vlst2 : (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 vlist 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 vlists and returns the vlist (list 1 4 9 16 25 36).

 (foldl func init vlst1 vlst2 ...) → C func : (C A B ... B -> C) init : C vlst1 : (List A) vlst2 : (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 vlst1 vlst2 ...) → C func : (C A B ... B -> C) init : C vlst1 : (List A) vlst2 : (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 func vlst) → (List A) func : (A -> Boolean) vlst : (List A)
Function filter is similar to filter.
 Examples: > (define vlst (list 1 2 3 4 5 6)) > (->list (filter (λ:([x : Integer]) (> x 5)) vlst)) - : (Listof Positive-Fixnum) '(6) > (->list (filter (λ:([x : Integer]) (< x 5)) vlst)) - : (Listof Positive-Fixnum) '(1 2 3 4) > (->list (filter (λ:([x : Integer]) (<= x 4)) vlst)) - : (Listof Positive-Fixnum) '(1 2 3 4)

 (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)) 1- : 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)) 2- : 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