On this page:
List
list
empty
empty?
cons
first
last
rest
list-ref
length
->list
reverse
map
foldl
foldr
andmap
ormap
build-list
make-list
filter
second
third
fourth
fifth
sixth
seventh
eighth
ninth
tenth
Version: 5.0.1.6

6 VList

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

  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)

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