#lang scribble/manual @(require unstable/scribble) @defmodule/this-package[vlist] @(require (for-label (planet krhari/pfds:1:0/vlist)) "helper.rkt") @(require scribble/eval) @(define evaluate (make-base-eval)) @(evaluate '(require typed/racket)) @(evaluate '(require "vlist.ss")) @title{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 @bold{@italic{O(1)}} and @bold{@italic{O(lg N)}} respectively compared to @bold{@italic{O(N)}} in lists. The data structure has been described in the paper @italic{Fast Functional Lists, Hash-Lists, vlists and Variable Length Arrays} by Phil Bagwell. VLists implementation internally uses @secref["sbral"]. @defform[(List A)]{A vlist type @racket[A].} @defproc[(list [a A] ...) (List A)]{ Function @scheme[list] creates a vlist with the given inputs. @examples[#:eval evaluate (list 1 2 3 4 5 6) ] In the above example, the vlist obtained will have 1 as its first element.} @defthing[empty (List Nothing)]{ An empty vlist.} @defproc[(empty? [vlst (List A)]) Boolean]{ Function @scheme[empty?] checks if the given vlist is empty or not. @examples[#:eval evaluate (empty? (list 1 2 3 4 5 6)) (empty? empty) ]} @defproc[(cons [a A] [vlst (List A)]) (List A)]{ Function @scheme[cons] takes an element and a vlist and adds the given element to the vlist. @examples[#:eval evaluate (cons 10 (list 1 2 3 4 5 6)) ] In the above example, @scheme[cons] adds the element 10 to @scheme[(list 1 2 3 4 5 6)] and returns @scheme[(list 10 1 2 3 4 5 6)].} @defproc[(first [vlst (List A)]) A]{ Function @scheme[first] takes a vlist and gives the first element of the given vlist if vlist is not empty else throws an error. @examples[#:eval evaluate (first (list 1 2 3 4 5 6)) (first empty) ]} @defproc[(last [vlst (List A)]) A]{ Function @scheme[last] takes a vlist and gives the last element in the vlist if vlist is not empty else throws an error. @examples[#:eval evaluate (last (list 1 2 3 4 5 6)) (last empty) ]} @defproc[(rest [vlst (List A)]) (List A)]{ Function @scheme[rest] takes a vlist and returns a vlist without the first element if the given vlist is not empty. Else throws an error. @examples[#:eval evaluate (rest (list 1 2 3 4 5 6)) (rest empty) ] In the above example, @scheme[(rest (list 1 2 3 4 5 6))], removes the head and returns @scheme[(list 2 3 4 5 6)].} @defproc[(list-ref [vlst (List A)] [index Integer]) A]{ Function @scheme[list-ref] takes a vlist and an index(say n) and gives the nth element of the given vlist @examples[#:eval evaluate (list-ref (list 1 2 3 4 5 6) 0) (list-ref (list 1 2 3 4 5 6) 3) (list-ref (list 1 2 3 4 5 6) 10) ]} @defproc[(length [vlst (List A)]) Integer]{ Function @scheme[length] takes a vlist and gives the number of elements in the given vlist. @examples[#:eval evaluate (length (list 1 2 3 4 5 6)) (length empty) ]} @defproc[(->list [vlst (List A)]) (Listof A)]{ Function @scheme[->list] takes a vlist and returns a normal scheme list. @examples[#:eval evaluate (->list (list 1 2 3 4 5 6)) (->list empty) ]} @defproc[(reverse [vlst (List A)]) (List A)]{ Function @scheme[reverse] takes a vlist and returns a reversed vlist. @examples[#:eval evaluate (->list (reverse (list 1 2 3 4 5 6))) ]} @defproc[(map [func (A B ... B -> C)] [vlst1 (List A)] [vlst2 (List B)] ...) (List A)]{ Function @scheme[map] is similar to @|racket-map| for lists. @examples[#:eval evaluate (->list (map add1 (list 1 2 3 4 5 6))) (->list (map * (list 1 2 3 4 5 6) (list 1 2 3 4 5 6))) ] In the above example, @scheme[(map add1 (list 1 2 3 4 5 6))] adds 1 to each element of the given vlist and returns @scheme[(list 2 3 4 5 6 7)]. @scheme[(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 @scheme[(list 1 4 9 16 25 36)].} @defproc[(foldl [func (C A B ... B -> C)] [init C] [vlst1 (List A)] [vlst2 (List B)] ...) C]{ Function @scheme[foldl] is similar to @|racket-foldl|. @margin-note{@scheme[foldl] currently does not produce correct results when the given function is non-commutative.} @examples[#:eval evaluate (foldl + 0 (list 1 2 3 4 5 6)) (foldl * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6)) ]} @defproc[(foldr [func (C A B ... B -> C)] [init C] [vlst1 (List A)] [vlst2 (List B)] ...) C]{ Function @scheme[foldr] is similar to @|racket-foldr|. @margin-note{@scheme[foldr] currently does not produce correct results when the given function is non-commutative.} @examples[#:eval evaluate (foldr + 0 (list 1 2 3 4 5 6)) (foldr * 1 (list 1 2 3 4 5 6) (list 1 2 3 4 5 6)) ]} @defproc[(filter [func (A -> Boolean)] [vlst (List A)]) (List A)]{ Function @scheme[filter] is similar to @|racket-filter|. @examples[#:eval evaluate (define vlst (list 1 2 3 4 5 6)) (->list (filter (λ:([x : Integer]) (> x 5)) vlst)) (->list (filter (λ:([x : Integer]) (< x 5)) vlst)) (->list (filter (λ:([x : Integer]) (<= x 4)) vlst)) ]} @(close-eval evaluate)