6 VList

Version: 5.0.1.2

6 VList

(require "vlist.ss")

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

(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

(vlist->list vlst) → (Listof A)

vlst : (List A)

Function vlist->list takes a vlist and returns a normal scheme list.

Examples:

> (vlist->list (list 1 2 3 4 5 6))

- : (Listof Positive-Fixnum)

'(1 2 3 4 5 6)

> (vlist->list empty)

- : (Listof Nothing)

'()

(reverse vlst) → (List A)

vlst : (List A)

Function reverse takes a vlist and returns a reversed vlist.

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

In the above example, (reverse (list 1 2 3 4 5 6)), returns the reversed vlist (list 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:

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

- : (Listof Exact-Positive-Integer)

'(2 3 4 5 6 7)

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

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

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

- : (Listof Positive-Fixnum)

'(6)

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

- : (Listof Positive-Fixnum)

'(1 2 3 4)

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

- : (Listof Positive-Fixnum)

'(1 2 3 4)

← 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