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
7.7

5 VList

 (require pfds/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