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 = {
type vector 'a
val map 'a 'b: (a -> b) -> vector a -> vector b
val reduce 'a: (a -> a -> a) -> a -> vector a -> a
val zip 'a 'b: vector a -> vector b -> vector (a, b)
val get 'a: i32 -> vector a -> a
val set 'a: i32 -> a -> vector a -> vector a
val length 'a: vector a -> i32
val to_array 'a: vector a -> []a
val from_array 'a: []a -> vector a
}
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.