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 map2 'a 'b 'c: (a -> b -> c) -> vector a -> vector b -> vector c
val reduce 'a: (a -> a -> a) -> a -> vector a -> a
val zip 'a 'b: vector a -> vector b -> vector (a, b)
val vzip [n] 'a: vector [n]a -> [n]vector a
val vunzip [n] 'a: [n]vector a -> vector [n]a
val iota: vector i64
val replicate 'a: a -> vector a
val get 'a: i64 -> vector a -> a
val set 'a: i64 -> a -> vector a -> vector a
val foldl 'a 'b: (b -> a -> b) -> b -> vector a -> b
val foldr 'a 'b: (a -> b -> b) -> b -> vector a -> b
val length: i64
val to_array 'a: vector a -> [length]a
val from_array 'a: [length]a -> vector a
}
module any_vector: (P: {
val length: i64
}) -> vector
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 map2 'a 'b 'c: (a -> b -> c) -> vector a -> vector b -> vector c

Apply a function to every pair of elements from two vectors.

↑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 vzip [n] 'a: vector [n]a -> [n]vector a

Turn a vector of arrays into an array of vectors.

↑val vunzip [n] 'a: [n]vector a -> vector [n]a

Turn a array of vectors a vector of arrays.

↑val iota: vector i64

A vector with increasing elements, starting at 0.

↑val replicate 'a: a -> vector a

A vector with filled with a replicated value

↑val get 'a: i64 -> vector a -> a

Retrieve the element at some position.

↑val set 'a: i64 -> a -> vector a -> vector a

Set the element at some position.

↑val foldl 'a 'b: (b -> a -> b) -> b -> vector a -> b

Perform a left-fold over the vector's elements.

↑val foldr 'a 'b: (a -> b -> b) -> b -> vector a -> b

Perform a right-fold over the vector's elements.

↑val length: i64

The length of vectors.

↑val to_array 'a: vector a -> [length]a

Convert a vector to an array.

↑val from_array 'a: [length]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.

When using this module, you need to instantiate it with another module that indicates the dimensionality of the vectors you will be producing.

↑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.

The foldl implementation is unrolled, so beware code explosion if you use a large vector or a complex fold function. You can always use an ordinary loop and get instead.

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.