# 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 `Ordinal`

s 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`MultiIndex`

es. - 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 `show`

n 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`

.