## Abstract

Efficient statically sized vectors.

This file defines a module type, `vector`

, that describes
single-dimensional vectors with an abstract interface. The point
is that the interface has been designed such that it can be
implemented both with an ordinary Futhark array
(`any_vector`

), but also with a tuple-representation for those
cases where the size of the vector is known statically
(`vector_1`

and `cat_vector`

). This is useful for small
vectors, because they will then be kept in registers rather than
memory. It also makes it explicit to the compiler that the
potential parallelism provided by the vector operations is not
worth exploiting. This is generally the case when working with
many points in some space.

## Synopsis

module type vector = {
| |||||||||||||||||||||||||||||

module any_vector | : | vector with vector 'a = []a | |||||||||||||||||||||||||||

module vector_1 | : | vector | |||||||||||||||||||||||||||

module cat_vector | : | (X: vector) -> (Y: vector) -> vector |

## Description

- ↑module type vector
A module type describing a one-dimensional vector (although a length-n vector may well represent a point in an n-dimensional space). Note the absence of run-time vector concatenation - this is omitted to facilitate statically sized representations, such as tuples.

- ↑type vector 'a
- ↑val map 'a 'b: (a -> b) -> vector a -> vector b
Apply a function to every element of the vector.

- ↑val reduce 'a: (a -> a -> a) -> a -> vector a -> a
Perform a reduction of the vector with an associative operator that has the provided neutral element.

- ↑val zip 'a 'b: vector a -> vector b -> vector (a, b)
Construct a vector of pairs from two vectors.

- ↑val get 'a: i32 -> vector a -> a
Retrieve the element at some position.

- ↑val set 'a: i32 -> a -> vector a -> vector a
Set the element at some position.

- ↑val length 'a: vector a -> i32
The length of a vector.

- ↑val to_array 'a: vector a -> []a
Convert a vector to an array.

- ↑val from_array 'a: []a -> vector a
Create a vector from an array.

- ↑module any_vector
An implementation of

`vector`

that uses an ordinary array as the representation. This is efficient for large vectors and the implementation of`map`

and`reduce`

is parallel. However, the`set`

operation is very slow for this implementation, as it requires a full copy of the vector. Unless you are interacting with a parametric module that specifically requires an implementation of`vector`

, it is probably better to use arrays directly than to go through this module.Since the size of the vectors is not constrained by the type, it is possible for

`zip`

to fail with a size error, just as with the ordinary`zip`

.- ↑module vector_1
A module implementing statically-sized single-element vectors. The implementation of

`map`

and`reduce`

is sequential.- ↑module cat_vector
Concatenation of statically sized vector modules. This is used to build up statically sized vectors of some size. For example,

`cat_vector vector_1 vector_1`

produces a module that defines length-2 vectors. The implementation of`map`

and`reduce`

is sequential.

## Examples

The `vector_1`

module provides us with single-element vectors.
We can build those up with `cat_vector`

to produce vectors of any
(static) size:

```
module vector_2 = cat_vector vector_1 vector_1
module vector_3 = cat_vector vector_2 vector_1
module vector_5 = cat_vector vector_2 vector_3
module vector_8 = cat_vector vector_5 vector_3
let main (xs: [8]i32) =
xs
|> vector_8.from_array
|> vector_8.map (+1)
|> vector_8.to_array
```

This is awkward for very long vectors, but these would not be efficient anyway.