Algebraic Hierarchy

Oftentimes, we want to create generic operations that can operate on many different types. For instance, we might want to sum up all the elements in a Vector, or we might want to make an algorithm that can find the minimum of a function in a generic way that works for DenseVectors, SparseVectors, Doubles, or even GPU types like Gust's CuVector. In Breeze, we use the typeclass pattern to achieve this, using concepts from abstract algebra as our guide. That possibly sounds scarier than it really is.

Breeze has a fairly elaborate algebraic hierarchy. It is not as complete as Spire's in many ways, but it handles many purposes quite well. We have organized them into two groups: those that are mostly associated with scalar types (like Fields) and those that are associated with Vector types (like VectorSpaces). Note that we actually also provide Rings and Fields for certain vector-y types (notably Vectors, DenseVectors, and SparseVectors), and we also (XXX do we still?) provide VectorSpaces for scalar-y types, e.g. by turning a Field into a VectorSpace (of dimension 1). Nevertheless, we usually think about these types as being separated between Vectors and Scalars.

Using the Algebraic Hierarchy

XXX talk about implicits and sums, etc.

Scalar Types

Types like Semiring and Field provide generic facilities for dealing with scalar types like Double, Int, Complex, and Boolean.

Semiring

The root of the algebraic hierarchy for scalar types is currently the Semiring, which has the following definition:

trait Semiring[V] {
  def zero : V
  def one : V

  def +(a : V, b : V) : V
  def *(a : V, b : V) : V

  def ==(a : V, b : V) : Boolean
  def !=(a : V, b : V) : Boolean
  def close(a: V, b: V, tolerance: Double=1E-4):Boolean = a == b
}

Semirings provide addition and multiplication along with their identities. Addition is associative and commutative, and multiplication is associative and distributes over addition. (Spire calls semirings "Rigs", which is a nonstandard name.) See the Wikipedia entry for more information.

Ring

A Ring adds negative values: every v has an additive inverse -v such that v + -v = zero.

Field

A Field adds division: every v now also has a multiplicative inverse one / v such that v * one / v == one. In addition, multiplication must be commutative. The Real numbers and Complex numbers both have fields. We abuse terminology and make Ints and other integer types into Fields, even though they're not actually fields. (They have division, and we didn't feel like making another type.)

Vector Types

For algorithms and operations that operate at the level of Vectors, we have another set of type classes. XXX Nearly all of these type classes also have mutable variants: many algorithms are more efficiently written using mutation. Note, however, that we can turn most immutable type classes (e.g. VectorSpace) into their mutable equivalents (e.g. MutableVectorSpace) using the MutabilizingAdaptor, which wraps a VectorSpace to make it appear to be mutable.

VectorSpace

A VectorSpace is the typeclass you're most likely to have seen. VectorSpaces are over a scalar type S and a vector type V. The scalar type must have a Field, and the vectors have to interact in particular ways. The operations are defined like so:

XXX

Note that many things can have VectorSpaces besides just Vectors. Matrices can also have VectorSpaces, as can Counters, and even functions!

Module (Advanced)

A Module is a VectorSpace where the underlying type is a Ring, rather than a Field.

AdditiveTensorAbelianGroup (Advanced)

InnerProductSpace

An InnerProductSpace is a VectorSpace where you can take the dot product of two

XXX

Like VectorSpace, the vectors in an InnerProductSpace are not required to have finite dimension, or even to have an "index set" at all. See CoordinateField instead.

NormedVectorSpace

LPSpace (Advanced)

VectorRing (Advanced)

VectorField (Advanced)

CoordinateField

FiniteCoordinateField

EnumeratedCoordinateField (Advanced)

OptimizationSpace