# Introduction

tensor is a library for type-safe, fixed dimension vectors and tensors. It means, for example, that there is a specific type for representing a vector of dimension 2, a type for a vector of dimension 3, a type for a matrix of 3 rows and 4 columns, and so on.

The first ingredient to realize this, is to define types for different numbers; these numbers differ from other implementations of type-level naturals in the fact that they are not just empty symbols for naturals, but they contain values inside, exactly a numbers of values equal to the number they represent. We call these types Ordinals.

In this library objects like vectors and matrices are particular cases of a more general data type: the tensor. This is a multidimensional array of values, and the indeces array, which we call MultiIndex, has fixed dimensions; this is the second ingredient for defining a tensor type. We define the MultiIndex using the special type constructor :|: as a type-level list, where the single types are Ordinals.

A Tensor type is a mere container of values organized in a multidimensional rectangular shape. When the values are numeric types, this library also provides many useful linear algebra functions, organized as class methods, ranging from solving linear systems to calculating the characteristic polynomial of a matrix.

## Module structure

### Data.Cardinal

Types-level natural number, useful for expressing the cardinality of another type. The Cardinals differ from Ordinals in that they are empty and start from 0 rather than 1.

### Data.Ordinal

Types representing fixed size sets of the form $$\{1,\ldots,n\}$$. See the section below.

### Data.Tensor

Classes for handling tensor data types. See the section below.

### Data.Tensor.LinearAlgebra

More classes for linear algebra specific operations.

### Data.Tensor.Pure

Implementation of Tensor data type that uses recursively defined type families.

### Data.Tensor.Vector

Implementation of Tensor data type that uses the vector package for its internal representation.

### Data.TypeAlgebra

Classes for algebraic operation on type-level numbers. This module should not be imported directly as it is already exported by Data.Ordinal and Data.Cardinal.

### Data.TypeList

Generic classes for handling type-level lists. This module should not be imported directly as it is already exported by Data.TypeList.MultiIndex.

### Data.TypeList.MultiIndex

Implementation of a type-level list that uses Ordinals as its components. See the section below.

## Release notes

### Version 0.3.0

• New backend Data.Tensor.Pure.
• QuickCheck tests.
• Instance of Applicative.
• New method generateM in class Tensor, and new function replicateM.
• Removed classes: FromVector and Zip (use liftA2 from Applicative).
• New class instances for Tensor: Bounded, Random.
• Removed Ord instances for MultiIndexes.
• Bug fixes and code improvements.

### Version 0.2.0

• Added GHC.Generics support for Cardinality class.
• New classes: Sliceable in Data.Tensor, Component, Extend and HeadTail in Data.TypeList, Dimensions in Data.TypeList.MultiIndex.
• Removed classes: MatrixProduct and TensorProduct from Data.Tensor.LinearAlgebra.
• New functions: elemMap and indexMap in Data.Tensor.
• New method split in class DirectSum for splitting into the two components.
• New methods in class SquareMatrix: polyEval for evaluating a polynomial on a matrix, and minPoly for computing the minimal polynomial.
• The methods dimensions in Data.TypeList.MultiIndex and dims in Data.Tensor are replaced by the method dimensions of the new class Dimensions.
• Bug fixes and code improvements.

# Ordinals

An ordinal is an equivalence class of totally ordered set. Let's take the sets $$O_1=\{1\}$$, $$O_2=\{1,2\}$$, ..., $$O_n=\{1,\ldots,n\}$$ as standard representatives of ordinals, and try to represent these sets as Haskell types.

We first define:

data One = One

to represent the singleton set $$O_1$$, where the constructor One plays the role of the single element $$1$$ in this set.

In order to represent ordinals of higher cardinality, we proceed inductively:

data Succ n = First
| Succ n

This means the following: suppose the type n corresponds to the set $$O_n=\{1,\ldots,n\}$$, then the type Succ n will be representative of the set $$\{1,2,\ldots,n+1\}$$ in which the element 1 corresponds to the constructor First, while the elements $$2,\ldots,n+1$$ correspond to the constructors Succ 1, ... , Succ n respectively.

For example, the type Succ One, which correspond to the set $$O_2$$, has two possible values: First and Succ One. The type Succ (Succ One), which corresponds to $$O_3$$, has three values: First, Succ First and Succ (Succ One).

If you need to express the ordinal set $$O_3$$ you will use the type Succ (Succ One), for $$O_4$$ Succ (Succ (Succ One)), and so on. For convenience there are type synonyms

type Two = Succ One
type Three = Succ Two
type Four = Succ Three

these are provided up to Ten.

What if you want to express $$O_{143}$$? Nobody wants to write Succ Succ ... Succ Ten with 133 Succ's, that's why we need the type algebra. In the module Data.TypeAlgebra there are two classes

class Sum a b where
type a :+: b
(<+>) :: a -> b -> a :+: b

class Prod a b where
type a :*: b
(<*>) :: a -> b -> a :*: b

One and all its Succ's happen to be instances of Sum and Prod. The meaning of the two associated type synonyms above is exactly what one expects: for example, the type Three :+: Five is a synonym of Eight, and Three :*: Two is a synonym of Six. So, back to our question how to express $$O_{143}$$, we can do (Ten :*: Ten) :+: (Four :*: Ten) :+: Three; much better! If you do not believe, try the following

maxBound :: (Ten :*: Ten) :+: (Four :*: Ten) :+: Three

the result will be 143! This is because One and all its Succ's are instances of Bounded, so the maxBound of the type above is the highest number in the set $$O_{143}=\{1,2,\ldots,143\}$$.

You might have noticed that a couple of times already I used the expression "One and all its Succ's" to refer to all the types that we defined in order to represent ordinal sets. We need a way to refer collectively to all these types, because ultimately our goal is to use them to parametrize another type. This is the reason for introducing a new class that contains all these types as instances:

class Ordinal where
fromOrdinal :: Num i => n -> i
toOrdinal :: (Eq i, Num i) => i -> n

The two methods in this class, as you can guess from the name, are used to convert to and from a numeric type: for example, if you what the element 57 of the set $$O_{143}$$ you can write

toOrdinal 57 :: (Ten :*: Ten) :+: (Four :*: Ten) :+: Three

Simple, isn't it! Notice however that fromOrdinal and toOrdinal have a complexity $$O(n)$$.

# MultiIndex

The next step after constructing ordinals is to have a type for representing a multidimensional index, or multiindex for short. A multiindex is described by the list of its dimensions, however since each dimension is different and is represented by a different type, we cannot use a standard Haskell list but rather a list of types. We do that recursively. The first step is

data Nil = Nil

It represents a 0-dimensional index, and the reason for its name is that it represents the empty list in the context of type lists. Next we need the analog of the cons for constructing lists:

data a :|: b = a :|: b

The first argument of :|: is the head of the list, and the second is the tail. Thus, if for example you want to express a multiindex of dimension 3 using Ordinal types, you can write n1 :|: (n2 :|: (n3 :|: Nil)), where n1 n2 n3 are Ordianls.

In the picture above we have three examples of multiindices, represented graphically according to their dimension. Together with each example we have the possible values of the multiindex itself, expressed in the form $$[i_1,\ldots,i_k]$$; this is the form the values are printed on the screen according to the Show instance of a standard multiindex. For example the single value, Nil, of the type Nil is printed as $$[]$$, the values a :|: Nil are printed as [show a], the values a1 :|: (a2 :|: Nil) are printed as [show a1, show a2], and so on.

All the multiindex types of the form a1 :|: (a2 :|: ... :|: (ak :|: Nil)...) are instances of the class MultiIndex

class TypeList i => MultiIndex i where
fromMultiIndex :: Num n => i -> [n]
toMultiIndex :: (Eq n, Num n) => [n] -> i

Using the methods in this class facilitates converting to and from a MultiIndex. For example, the following are two ways of creating the same [3,2] inside the 2-dimensional MultiIndex of 5 rows and 6 columns:

(toOrdinal 3 :: Five) :|: ((toOrdinal 2 :: Six) :|: Nil)
toMultiIndex [3,2] :: Five :|: (Six :|: Nil)

Although the second line is just a little bit shorter, it will become much more readable in all cases when the type is inferred and the second part beginning with :: can be dropped.

If you want the list of dimensions of a MultiIndex as an ordinary list of numbers, there is the following class:

class Dimensions i where
dimensions :: Num n => i -> [n]

Its method dimensions depends only the type of the MultiIndex and it should always be independent on the particular input values. For example:

dimensions (undefined :: Five :|: (Six :|: Nil))
[5,6]

# Tensor

A tensor is a multidimensional array of values. In order to define a tensor type in Haskell we need to specify the type of the values that it stores and the array of indices that we use to access these values. For the latter we use a MultiIndex.

data Tensor i e

In the definition above i is a MultiIndex type and e is the type of the value. We do not expose the constructor; in fact we can have different definitions of Tensor using different internal representations, (which we will call beckends). At the moment we provide two backends, denoted by the name of the module where they are defined:

• Data.Tensor.Vector is based on Data.Vector module of the vector package.
• Data.Tensor.Pure offers a pure Haskell backend, although less efficient and still incomplete.

All backends are accessed by importing their module.

One feature of the tensor package is that not only allows the possibility of multiple backends, but also is abstracted from the particular backend choosen: this means that all the most important functions that we use to operate on a data type like Tensor i e defined above, are infact methods of classes of which Tensor i e is an instance. So, if you switch to another definition of Tensor you can still operate on it with the same functions, provides that it is instance of the same classes.

For example, suppose that you want to generate a vector of dimension 4 with Int components 1,2,3,4; simple write

fromList [1,2,3,4] :: Tensor (Four :|: Nil) Int

The Show instance of Tensor will print it as the list [1,2,3,4]. The function fromList is a method of the class

class FromList t where
fromList :: [e] -> t e

and it is used to form a tensor from a list of elements.

fromList [3,1,4,1,5,9] :: Tensor (Three :|: (Two :|: Nil)) Int

The Show instance of Tensor always prints the result as a list of lists [[3,1],[4,1],[5,9]] where the inner most lists are the rows of the matrix. This is the general rule: Tensor is shown as a list of lists of ... of lists where the inner most list refers to the modification of the last index of the MultiIndex and the outer most refers to the modification of first index. A particular case is that of Tensor Nil e which is isomorphic to e, and is printed without square brackets.

Any Tensor data type, regardless of the backend, should be an in instance of the class Tensor

class Tensor t where
type Index t
type Elem t
(!) :: t -> Index t -> Elem t
generate :: (Index t -> Elem t) -> t

This class is defined in the module Data.Tensor, which is exported by Data.Tensor.Vector (and should be exported by any other backend). First of all, there are two associated type synonyms, Index t and Elem t, which represent the indexing type and the type of the values contained inside the Tensor. In particular Index t should be an instance of MultiIndex.

Next we have the methods (!), for retrieving a particular element, and generate, for generating a Tensor given a function from indices to elements.

Another important class in Data.Tensor is DirectSum: it is a class for generating bigger tensors from smaller ones, by juxtaposing them.

class DirectSum n t1 t2 where
type SumSpace n t1 t2
directSum :: n -> t1 -> t2 -> SumSpace n t1 t2
split :: n -> SumSpace n t1 t2 -> (t1, t2)

Above, t1 and t2 are two tensors, while n is a Cardinal type. Let's make an example

let t1 = fromList [3,1,4,1,5,9] :: Tensor (Three :|: (Two :|: Nil)) Int
let t2 = fromList [2,7,1,8,2,8] :: Tensor (Three :|: (Two :|: Nil)) Int

These are two 3x2 matrices, and there are two ways we can juxtapose them: vertically and horizontally. If we juxtapose them vertically then the result will be a 6x2 matrix, i.e. the first dimension of resulting matrix is the sum of the first dimensions of t1 and t2, while the second dimension is the same across t1, t2 and the result; we denote this operation by directSum (undefined :: C0) t1 t2, where undefined :: C0 is used to tell that we want to "sum vertically", i.e. by growing the first dimension (C0 is the first Cardinal). Here SumSpace C0 t1 t2 is Tensor (Six :|: (Two :|: Nil)) Int.

If we juxtapose t1 and t2 horizontally the result will be a 3x4 matrix, i.e. the first dimension is the same across t1, t2 and the result, while the second dimension of the result is the sum of the second dimensions of t1 and t2. That is directSum (undefined :: C1) t1 t2, where undefined :: C1 (generic element of the second Cardinal) tells us that we are growing the second dimension. Here SumSpace C1 t1 t2 is Tensor (Three :|: (Four :|: Nil)) Int.

The same directSum operation can be carried out on higher orders tensors (parallelepipes, hyperparallelepipeds, ...) with one condition: all dimensions of the two tensor that we are summing must match, except possibly the one indicated by the Cardinal n, or else the type system will rise an error.

The method split does the opposite thing of directSum: it splits the SumSpace into its two components along the dimension indicated by n.