5 VList

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

- : #(struct:List

(Integer

#(struct:Base ((U (Base Positive-Byte) Null) (Listof Positive-Byte)))

Integer))

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

- : Boolean

#f
> (empty? empty )

- : Boolean

#t

procedure
( cons avlst)→(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 123456))

- : #(struct:List

(Integer

#(struct:Base ((U (Base Positive-Byte) Null) (Listof Positive-Byte)))

Integer))

#<List>

In the above example, cons adds the element 10 to (list 123456) and returns (list 10123456).

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

- : 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 123456))

- : 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 123456))

- : #(struct:List

(Integer

#(struct:Base ((U (Base Positive-Byte) Null) (Listof Positive-Byte)))

Integer))

#<List>
> (rest empty )

rest: given vlist is empty

In the above example, (rest (list 123456)), removes the head and returns (list 23456).

procedure
( list-ref vlstindex)→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 123456)0)

- : Integer [more precisely: Positive-Byte]

1
> (list-ref (list 123456)3)

- : Integer [more precisely: Positive-Byte]

4
> (list-ref (list 123456)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 123456))

- : Integer

6
> (length empty )

- : Integer

0

procedure
( ->list vlst)→(ListofA)
vlst:(List A)

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

Examples:

> (->list (list 123456))

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

- : (Listof Positive-Byte)

'(6 5 4 3 2 1)

procedure
( map funcvlst1vlst2...)→(List A)
func:(AB...B->C)
vlst1:(List A)
vlst2:(List B)

Function map is similar to map for lists.

Examples:

> (->list (map add1(list 123456)))

- : (Listof Positive-Index)

'(2 3 4 5 6 7)
> (->list (map *(list 123456)(list 123456)))

- : (Listof Positive-Index)

'(1 4 9 16 25 36)

In the above example, (map add1(list 123456)) adds 1 to each element of the given vlist and returns (list 234567). (map *(list 123456)(list 123456)) multiplies corresponding elements in the two vlists and returns the vlist (list 149162536).

procedure
( foldl funcinitvlst1vlst2...)→C
func:(CAB...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 123456))

- : Integer [more precisely: Nonnegative-Integer]

21
> (foldl *1(list 123456)(list 123456))

- : Integer [more precisely: Positive-Integer]

518400

procedure
( foldr funcinitvlst1vlst2...)→C
func:(CAB...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 123456))

- : Integer [more precisely: Nonnegative-Integer]

21
> (foldr *1(list 123456)(list 123456))

- : Integer [more precisely: Positive-Integer]

518400

procedure
( andmap funclst1lst2...)→Boolean
func:(AB...B->Boolean)
lst1:(List A)
lst2:(List B)

Function andmap is similar to andmap .

Examples:

> (andmap even?(list 123456))

- : Boolean

#f
> (andmap odd?(list 123456))

- : Boolean

#f
> (andmap positive?(list 123456))

- : Boolean

#t
> (andmap negative?(list -1-2))

- : Boolean

#t

procedure
( ormap funclst1lst2...)→Boolean
func:(AB...B->Boolean)
lst1:(List A)
lst2:(List B)

Function ormap is similar to ormap .

Examples:

> (ormap even?(list 123456))

- : Boolean

#t
> (ormap odd?(list 123456))

- : Boolean

#t
> (ormap positive?(list -1-234-56))

- : Boolean

#t
> (ormap negative?(list 1-2))

- : Boolean

#t

procedure
( build-list sizefunc)→(List A)
size:Natural
func:(Natural->A)

Function build-list is similar to build-list .

Examples:

> (->list (build-list 5(λ:([x:Integer])(add1x))))

- : (Listof Integer)

'(1 2 3 4 5)
> (->list (build-list 5(λ:([x:Integer])(*xx))))

- : (Listof Integer)

'(0 1 4 9 16)

procedure
( make-list sizefunc)→(List A)
size:Natural
func:A

Function make-list is similar to make-list.

Examples:

> (->list (make-list 510))

- : (Listof Positive-Byte)

'(10 10 10 10 10)
> (->list (make-list 5'sym))

- : (Listof 'sym)

'(sym sym sym sym sym)

procedure
( filter funcvlst)→(List A)
func:(A->Boolean)
vlst:(List A)

Function filter is similar to filter .

Examples:

> (definevlst(list 123456))
> (->list (filter (λ:([x:Integer])(>x5))vlst))

- : (Listof Positive-Byte)

'(6)
> (->list (filter (λ:([x:Integer])(<x5))vlst))

- : (Listof Positive-Byte)

'(1 2 3 4)
> (->list (filter (λ:([x:Integer])(<=x4))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 12345678910))

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

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

- : 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 12345678910))

- : 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 12345678910))

- : 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 12345678910))

- : 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 12345678910))

- : 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 12345678910))

- : 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 1234567891011))

- : Integer [more precisely: Positive-Byte]

10

top ← prev up next →