5 VList

7.7

5 VList

package: pfds

A VList is a data structure very similar to a normal 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.

syntax
(List A)

A vlist type A.

procedure
(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-Byte)
#<List>

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

value
empty : (List Nothing)

An empty vlist.

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

procedure
(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-Byte)
#<List>

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

procedure
(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))
- : Integer [more precisely: Positive-Byte]
1
> (first empty)
first: given vlist is empty

procedure
(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))
- : Integer [more precisely: Positive-Byte]
6
> (last empty)
last: given vlist is empty

procedure
(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-Byte)
#<List>
> (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).

procedure
(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)
- : Integer [more precisely: Positive-Byte]
1
> (list-ref (list 1 2 3 4 5 6) 3)
- : Integer [more precisely: Positive-Byte]
4
> (list-ref (list 1 2 3 4 5 6) 10)
list-ref: given index out of bounds

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

procedure
(->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-Byte)
'(1 2 3 4 5 6)
> (->list empty)
- : (Listof Nothing)
'()

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

procedure
(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 Positive-Index)
'(2 3 4 5 6 7)
> (->list (map * (list 1 2 3 4 5 6) (list 1 2 3 4 5 6)))
- : (Listof Positive-Index)
'(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).

procedure
(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))
- : Integer [more precisely: Nonnegative-Integer]
21
> (foldl * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Integer]
518400

procedure
(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))
- : Integer [more precisely: Nonnegative-Integer]
21
> (foldr * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))
- : Integer [more precisely: Positive-Integer]
518400

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

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

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

procedure
(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-Byte)
'(10 10 10 10 10)
> (->list (make-list 5 'sym))
- : (Listof 'sym)
'(sym sym sym sym sym)

procedure
(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-Byte)
'(6)
> (->list (filter (λ:([x : Integer]) (< x 5)) vlst))
- : (Listof Positive-Byte)
'(1 2 3 4)
> (->list (filter (λ:([x : Integer]) (<= x 4)) vlst))
- : (Listof Positive-Byte)
'(1 2 3 4)

procedure
(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- : Integer [more precisely: Positive-Byte]
2

procedure
(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- : Integer [more precisely: Positive-Byte]
3

procedure
(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))
- : Integer [more precisely: Positive-Byte]
4

procedure
(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))
- : Integer [more precisely: Positive-Byte]
5

procedure
(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))
- : Integer [more precisely: Positive-Byte]
6

procedure
(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))
- : Integer [more precisely: Positive-Byte]
7

procedure
(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))
- : Integer [more precisely: Positive-Byte]
8

procedure
(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))
- : Integer [more precisely: Positive-Byte]
9

procedure
(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))
- : Integer [more precisely: Positive-Byte]
10

top ← prev up next →

1	Queues
2	Deques
3	Heaps
4	Random Access Lists
5	VList
6	Streams
7	Red-Black Trees
8	Tries
9	Treap