6 VList

Version: 5.0.1.3

6 VList

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

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)

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

(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

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

(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

← 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