The Vector Library
(v.5
201116)
© W O Riha

1. Introduction A mathematician thinks of
a vector as an element of a linear space over
some field, a physicist and an engineer as an
object that has direction and length.
In this package,
we regard a vector as a (polymorphic)
computational object, similar to a list. Just as
a list consists of a sequence of elements, a
vector is also composed of elements, called
components, which are referenced via an index.
But whereas, accessing the ith element of a list
takes linear time, accessing the ith component
of a vector is done in constant time.
In procedural
languages, a vector component cannot only be
referenced but can also be ‘updated’ by
assigning to it a new value. In functional
programming such an operation is frowned upon,
because mutable objects are (usually) not
permitted in view of the obvious sideeffects.
Changing the value of a vector component would
therefore require that a copy of the original is
made, and the componentvalue updated in this new
vector. A vector would then not be much different
from a list.
For this reason,
Shen implements a vector as a mutable object.


1.1 Vectors in Shen
In Shen, vectors (like
lists) are polymorphic, i.e. can be of any type. The
following function is used to create an (uninitialized)
vector of arbitrary type A
vector : number > (vector A)
Input: A number N (should be a nonnegative integer
– if not, a platformdependent error message is
raised).
Output: An (uninitialized) Ncomponent vector of
unspecified type A.
Example:
(vector 3)
<... ... ...> : (vector A)
(vector 0)
<> : (vector A) \\ the ‘empty vector’
Note: ... indicates that the component has no value.
Accessing such a component results in an error.
1.2 Builtin Vector Functions
The following builtin
functions are available.
vector?
: A > boolean \\ recogniser
Input: Any
object X.
Output: true if X is a vector, otherwise false.
(vector?
(vector 5))
true : boolean
(vector? Mark)
false : boolean
To construct a vector
from its components the (polyadic) constructor @v is used
– it can take any number of arguments (at least
one), and therefore has no official type. Its type would
be
@v : A
> A > ... > A > (vector A) \\
constructor
(@v 1 3
5 7 <>)
<1 3 5 7> : (vector number)
(@v This is a Shen vector <>)
<This is a Shen vector> : (vector symbol)
limit :
(vector A) > number
Input: A
vector V.
Output: The dimension of V, i.e. the number of components
of V.
(limit
(@v 1 3 5 7 <>))
4 : number
(limit <>)
0 : number
hdv :
(vector A) > A
Input: A
vector V.
Output: The value held in the 1st component, or an error,
if V is empty.
(hdv (@v 12
13 <>))
12 : number
(hdv (vector 3))
hdv needs a nonempty vector as an argument; not <...
... ...>
tlv :
(vector A) > (vector A)
Input: A vector V.
Output: The vector consisting of all but the first
component of V, or an error, if V is empty.
(tlv (@v
12 13 14 <>))
<13 14> : (vector number)
(tlv <>)
cannot take the tail of the empty vector
<vector
: (vector A) > number > A \\ access a vector
component
Input: A
vector V and an integer I, between 1 and (limit V),
inclusive.
Output: The value held in component I, or an error
message, if undefined.
(<vector
(vector 5) 3)
vector element not found
(<vector (@v 12 14 16 <>) 2)
14 : number
vector>
: (vector A) > number > A > (vector A) \\
update component
Input: A
vector V, an index I and a value X.
Output: Vector V, with Ith component changed to X
(destructive!)
(let Vec (vector 5) \\ create a 5component vector Vec
(vector> Vec 3 "Shen")) \\ assign a string to the 3rd component
<... ... "Shen" ... ...> : (vector string)
As can be seen, there are
certain similarities between lists, vectors and strings
which are set out next.
type 
(vector
A) 
(list
A) 
string 
empty case 
<>
: (vector A) 
[]
: (list A) 
""
: string 
constructor
(arity = 2) 
(@v
x <>)
<x> : (vector symbol) 
(cons
x [])
[x] : (list symbol) 
(cn
"x" "")
"x" : string 
constructor
(polyadic) 
(@v
a b (vector 3))
<a b ... ... ...> : (vector symbol) 
[a
b  [a b c]]
[a b a b c] : (list symbol)

(@s
"a" "b" "abc")
"ababc" : string 
recogniser 
(vector?
@v A B <>))
true : boolean 
(cons?
[A B])
true : boolean 
(string?
"AB")
true : boolean 
head (the first
entry) 
(hdv
(@v A B a b c <>))
A : symbol 
(head
[A B a b c])
A : symbol 
(hdstr
"ABabc")
"A" : string 
tail (all but
first entry) 
(tlv
(@v A B a b c <>))
<B a b c> : [B a b c] : (vector symbol) 
(tail
[A B a b c])
[B a b c] : (list symbol) 
(tlstr
"ABabc")
"Babc" : string 
size 
(limit
(vector 5))
5 : number 
(length
[A B a b c])
5 : number 
(string.length
"ABabc")
5 : number 
selector 
(<vector
(@v A B a b c <>) 3)
a : symbol 
(nth
3 [A B a b c])
a : symbol 
(pos
"ABabc" 3)
"a" : string 
Because of this
similarity, any list function can, literally, be
translated into an equivalent vector function. This,
however, is not good practice, as will be illustrated in
section 3.1.
2 Basic Vector Functions
When working with vectors it is often necessary to run
through the components in a systematic manner, either
starting with index 1 or, at the last index, or
processing a subrange of the components. In procedural
languages this is easily done using a forstatement.
Forstatements vary from language to language in terms of
expressiveness and complexity (see my unpublished notes
on this topic).
A forfunction which is
used in this library, has been introduced by Mark Tarver
(see package hof).
vector.init
: number > A > (vector A)
Input: An
integer N and a value X of type A.
Output: An ncomponent vector with all components
initialised to X.
(vector.init
3 "Ho")
<"Ho" "Ho" "Ho"> :
(vector string) \\ It’ll soon be Xmas!
Note: The following
functions will also work for partially initialised
vectors, as shown in the examples.
vector.copy
: (vector A) > (vector A)
Input: A
vector V.
Output: A copy of V.
(let Vec (vector 8)
(do (vector> Vec 1 Mark) (vector> Vec 5 Willi)
(vector.copy Vec)))
<Mark ... ... ... Willi ... ... ...> : (vector symbol)
vector.extend : (vector
A) > number > (vector A)
Input: A vector V and a positive integer N
Output: A new vector V’ that extends V by N
components.
(vector.extend (@v 1
3 5 <>) 4)
<1 3 5 ... ... ... ...> : (vector number)
vector.print : (vector A)
> symbol
Input: A vector V.
Output: V printed as a column vector.
(let Vec (vector 8)
(do (vector> Vec 1 "Mark") (vector> Vec 5 "Willi") (vector.print Vec)))
"Mark"
...
...
...
"Willi"
...
...
...
done : symbol
vector.index
: A > (vector A) > number
Input: A
value X of type A and a vector V of type (vector A).
Output: The first index (in V) where X occurs or –1,
if it does not.
(let Vec
(vector 8)
(do (vector> Vec 1 Mark) (vector> Vec 5
Willi) (vector.index Willi Vec)))
5 : number
(vector.index 1 (vector.init 10 0))
1 : number
vector.append
: (vector A) > (vector A) > (vector A)
Input: Two
vectors V1 and V2 of type A.
Output: The two vectors appended.
(vector.append
(@v 2 3 5 7 11 <>) (@v 13 17 <>))
<2 3 5 7 11 13 17> : (vector number)
(vector.append (@v 2 3 5 7 11 <>) (vector 5))
\\ an alternative to vector.extend!
<2 3 5 7 11 ... ... ... ... ...> : (vector
number)
3 Conversion Functions
vector>list
: (vector A) > (list A)
Input: A
vector (must be completely initialised – otherwise,
not meaningful!).
Output: The vector converted into a list with the same
elements.
(vector>list
(vector.init 5 Ha))
[Ha Ha Ha Ha Ha] : (list symbol)
list>vector
: (list A) > (vector A)
Input: A
list.
Output: The list converted into a vector with the same
elements.
(list>vector
[])
<> : (vector A)
(list>vector [2 3 5 7 11])
<2 3 5 7 11> : (vector number)
3.1 Vector Functions as List
Functions
Using the preceding
conversion functions it is not difficult to apply list
processing functions to vectors. The idea is to convert
the vector to a list, apply the list operation, and then,
if necessary, convert the list back to a vector.
Example 1: (the list functions some? and
every? for vectors)
To check if some or all of the components of a vector V
satisfy a certain property P : A > boolean, we can
define functions
(define
vector.some?
{(A > boolean) > (vector A) > boolean}
F Vec > (some? F (vector>list Vec)))
(define vector.every?
{(A > boolean) > (vector A) > boolean}
F Vec > (every? F (vector>list Vec)))
For illustrations, see
next section under vector.some? and vector.every?
Aside: One could be tempted to implement these functions
directly in analogy to the equivalent list functions. For
example every? can be implemented as
(define
every?
{(A > boolean) > (list A) > boolean}
P [] > true
P [X  Xs] > (and (P X) (every? P Xs)))
This may be translated,
literally, as
(define
badvector.every?
{(A > boolean) > (vector A) > boolean}
P <> > true
P (@v X Xs) > (and (P X) (badvector.every? P
Xs)))
The reason why this is
bad, is due to the fact that unlike the pattern matching
of [X  Xs], which is fast, the pattern matching (@v X
Xs) is very expensive, as it requires copying of vectors.
Using vector.every?, it
takes less than 0.001 secs to check a random vector with
10000 components, all less than one. With
badvector.every, it takes 0.15 secs for a 1000component
vector and 19.5 secs for a vector with 10000 entries!
Example 2: (reversing a vector)
To reverse a vector, for example, (@v 2 3 5 7 11
<>), we could use the function invocation
(list>vector
(reverse (vector>list (@v 2 3 5 7 11 <>))))
<11 7 5 3 2> : (vector number)
More generally, we could
define a function
(define
vector.reverse
{(vector A) > (vector A)}
Vec > (list>vector (reverse (vector>list
Vec))))
It is possible, however,
to implement vector functions directly, using for,
instead of vector>list conversion. This requires more
thought, but may result in better performance for large
vectors (> 100000 components).
As an illustration
consider the vector.reverse function. Here is a possible
implementation
(define vector.reverse
{(vector A) > (vector A)}
<> > <>
Vec > (let N (limit Vec)
N1 (+ N 1)
V (vector N)
(for I = 1 to N
(vector> V I (<vector Vec ( N1 I))))))
This implementation will
not deal with partially initialised vectors, but a slight
modification to the code will do the trick.
vector.reverse
: (vector A) > (vector A)
Input: A
vector V.
Output: A new vector with the components of V in reverse
order.
(vector.reverse
(@v 2 3 5 7 11 <>))
<11 7 5 3 2> : (vector number)
(let Vec (vector 8)
(do (vector> Vec 1 Mark) (vector> Vec 5
Willi)
(vector.reverse Vec)))
<... ... ... Willi ... ... ... Mark> : (vector
symbol)
In the following section
we describe the higher order vector functions available
in the package. We shall not explain how these functions
are implemented.
4 Higher Order Vector Functions
4.1
Predicates
vector.element?
: A > (vector A) > boolean
Input: A
value X of type A and a vector V.
Output: true or false depending on whether X is a
component of V.
(vector.element?
3 (@v 7 10 3 <>))
false : boolean
vector.every?
: (A > boolean) > (vector A) > boolean
Input: A
predicate P: A > boolean and a vector V.
Output: true or false depending on whether all components
of V satisfy P.
(vector.every?
(function uppercase?) (@v "A" "B"
"C" <>))
true : boolean
Note: for partially
initialised vectors this function will always return
false!
vector.some?
: (A > boolean) > (vector A) > boolean
Input: A predicate P: A > boolean and a vector V.
Output: true or false depending on whether at least one
component of V satisfies P.
(let Vec
(vector 8) \\ partially initialised vector of numbers
(do (vector> Vec 2 15.5) (vector> Vec 5 0)
(vector.some? (function integer?) Vec))) \\ works
correctly
true : boolean
4.2 map and reduce
vector.map1
: (A > B) > (vector A) > (vector B)
Input: A
function f : A > B, and a vector V of type A.
Output: A vector of type B obtained by applying f to the
components of V.
(vector.map1
(function n>string) (@v 20 30 40 50 <>))
<"¶" "?" "("
"2"> : (vector string)
If B is the same as A,
then f : A > A is a unary operation on A which map1
extends to a vector.
(vector.map1
(function ~) (@v 1 1 2 <>)) \\ additive
inverse of a real vector
<1 1 2> : (vector number)
(let V (@v (c# 1 1) (c0) (i) <>)
(vector.map1 (function c') V)) \\ complex conjugate
of a vector
<(c# 1 1) (c# 0 0) (c# 0 1)> : (vector
complex)
(vector.map1 (* 3) (@v 1 1 2 <>)) \\ scalar
multiplication by 3
<3 3 6> : (vector number)
Similarly, if A is
endowed with binary operations (e.g. +, –) these can
be extended to vectors over A by making use of the
following function:
vector.map2
: (A > A > A) > (vector A) > (vector
A) > (vector A)
Input: A
binary operation f : A > A > A on A and two
vectors of type A.
Output: The vector obtained by applying f to the
corresponding components of the two vectors.
(vector.map2
(function +) (@v 1 1 2 <>) (@v 1 1 1
<>))
<0 0 1> : (vector number)
(vector.map2 (function ) (@v 1 1 2 <>) (@v 1
1 1 <>))
<2 2 3> : (vector number)
Note: These functions
allow us to do vector arithmetic also with complex
numbers and, more generally, with vectors over finite
fields.
vector.reduce
: (A > A > A) > A > (vector A) >
A
Input: A
binary operation f : A > A > A on A , a special
element S of type A, and a vector V of type A.
Output: The leftright reduction of V with respect to f
and start element S.
(vector.reduce
(function +) 0 (@v 1 2 3 4 5 6 <>)) \\
component sum
21 : number
(vector.reduce (function *) 1 (@v 1 2 3 4 5 6
<>)) \\ product of the components
720 : number
Combined with function
vector.map2, we can very succinctly work out the
socalled inner product, IP, of two vectors, which is
defined as follows:
For X = <x1, x2, …, xn> and Y = <y1, y2,
…, yn>
IP = x1 y1 + x2 y2 + … + xn yn
(vector.reduce
(function +) 0 (vector.map2 (function *) (@v 1 1 2
<>) (@v 1 1 1 <>)))
4 : number
The following piece of
code computes the square of the length of the complex
vector V.
Note: +c and *c denote complex addition and
multiplication, (c0) is complex 0, short for (c# 0 0)
(let V (@v (c# 1 1) (c# 2 3) (c# 2 1) <>)
V' (vector.map1 (function c') V) \\ complex conjugate
(vector.reduce (function +c) (c0) (vector.map2 (function *c) V V')))
(c# 20 0) : complex \\ is always a real number!
