Professional

Home
Learn Shen
Videos
Community Wiki
Community
OS Kernel
OS Library
Shen Professional

The Vector Library

(v.5 20-11-16)
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 i-th element of a list takes linear time, accessing the i-th 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 side-effects. Changing the value of a vector component would therefore require that a copy of the original is made, and the component-value 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. Introduction

1.1 Vectors in Shen
1.2 Built-in Vector Functions

2. Basic Vector Functions

3 Conversion Functions

4 Higher Order Vector Functions

4.1 Predicates
4.2 map and reduce

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 non-negative integer – if not, a platform-dependent error message is raised).
Output: An (uninitialized) N-component 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 Built-in Vector Functions

The following built-in 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 non-empty 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 I-th component changed to X (destructive!)

(let Vec (vector 5)	\\ create a 5-component 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 sub-range of the components. In procedural languages this is easily done using a for-statement. For-statements vary from language to language in terms of expressiveness and complexity (see my unpublished notes on this topic).

A for-function 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 n-component vector with all components initialised to X.

(vector.init 3 "Ho")
<"Ho" "Ho" "Ho"> : (vector string) \\ It’ll soon be X-mas!

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 bad-vector.every?
{(A --> boolean) --> (vector A) --> boolean}
P <> -> true
P (@v X Xs) -> (and (P X) (bad-vector.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 bad-vector.every, it takes 0.15 secs for a 1000-component 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 left-right 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 so-called 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!