Lists represent sequences as an inductive structure, which makes adding elements
(to the front) constant time, but accessing random elements \(O(n)\)
time. Typed Racket also provides the built-in type constructor Vectorof for representing
sequences as contiguous arrays of data. This representation gives \(O(1)\)
access, but requires copying the whole vector to add an element.
Similar to the list function, the vector function can be used to construct
a vector from elements and to pattern match against vectors of fixed size.
(vector 1 2 3)Racket also provides a quotation syntax for writing vector literals
'#(1 2 3)This is nearly the same as the list syntax, except for the addition of the hash symbol.
And, like the corresponding list syntax, it is important to be comfortable reading this
format, as it will be printed out by the REPL whenever it needs to show the value of a
vector. But, for the same reason that using the similar list syntax can lead to confusion,
this vector syntax can as well; it is best to use the (vector …) version instead
when constructing vector values.
Typed Racket provides various standard operations on vectors as polymorphic functions. These operations are similar to the corresponding list functions.
We can retrieve the length of a vector with
(: vector-length : (All (X) (Vectorof X) -> Integer))Note that, unlike taking the length of a list, this operation is \(O(1)\) (constant time).
We can extract an element from a vector by its index using
(: vector-ref : (All (X) (Vectorof X) Integer -> X))
(check-expect (vector-ref '#(1 2 3) 0) 1)
(check-expect (vector-ref '#(1 2 3) 1) 2)
(check-expect (vector-ref '#(1 2 3) 2) 3)Notice that indexing starts at 0. Specifying a negative index or one that is too large
results in an error.
Again, in contrast with lists, this operation is constant time.
Two or more vectors can be concatenated using the vector-append function.
(: vector-append : (All (X) (Vectorof X) * -> (Vectorof X)))
(check-expect (vector-append '#(1 2 3) '#(4) '#(5 6))
'#(1 2 3 4 5 6))We can build a vector using a generator function
(: build-vector : (All (X) (Integer (Natural -> X) -> (Vectorof X)))
(check-expect (build-vector 3 number->string) '#("0" "1" "2"))Lastly, the make-vector function creates a vector of the given length filled with the given value
(: make-vector : (All (X) (Integer X -> (Vectorof X)))
(check-expect (make-vector 3 "hi") (vector "hi" "hi" "hi"))Here are other vector functions that you might find useful:
(: list->vector : (All (X) (Listof X) -> (Vectorof X)))
;; convert a list to a vector
(: vector->list : (All (X) (Vectorof X) -> (Listof X)))
;; convert a vector to a list
(: vector-map : (All (X Y) (X -> Y) (Vectorof X) -> (Vectorof Y)))
;; maps a function across a vector to produce a new vector
(: vector-filter : (All (X) (X -> Boolean) (Vectorof X) -> (Vectorof X)))
;; filter a vector using the given predicate
(: vector-count : (All (X) (X -> Boolean) (Vectorof X) -> Integer))
;; count the number of vector elements that satisfy the predicate