Matrices, monads and the fast Fourier transform

Abstract
Author CBJ

This paper presents a formal semantics for vectors and matrices, suitable for static type-checking. This is not available in {\sc apl}, which produces run-time type errors, or in the usual functional languages, where matrices are typically implemented by lists of lists. Here, a matrix is a vector of vectors.

Vectors are distinguished from lists by requiring that vector computations determine the length of the result from that of the argument, without reference to values. This leads to a two-level semantics, with values above and shapes below. Each operation must then specify its action on shapes as well as its action on values.

Vectors and matrices inherit much of their structure from lists. In particular, the monadic structure given by singleton lists and the flattening of lists of lists extends in this way. Some new constructions, such as transposition of matrices, have no list counterpart.

The power of this calculus for vector and matrix algebra is sufficient to represent the discrete Fourier transform, and to prove that it is equivalent to the fast Fourier transform.