# Orthotope

## Disclaimer

This is not an officially supported Google product.

## Summary

This is a library for multi-dimensional arrays inspired by APL.

### See also
The orthotope-hmatrix repo contains some more functionality.

## Multi-dimensional arrays

Each array has a number of elements of the same type, and a *shape*. The shape
can be described by a list of integers that gives the size for each of the
dimensions. E.g. the array shape `[2,3]` is a 2x3 matrix (2 rows, 3
columns), and the shape `[]` is a single value (a scalar).
The number of dimensions is called the *rank* of the array.

The shape may or may not be part of the type, depending on which version of the
API you use.

## API variants

The API comes in many variants, depending on how strongly typed it is and what
the underlying storage is.

### Types

*   `Dynamic`, the shape is not part of the type, but is checked at runtime.
    E.g., `Array Float` is an array of `Float` which can have any shape.

*   `Ranked`, the rank of the array is part of the type, but the actual sizes of
    the dimensions are checked at runtime. E.g., `Array 2 Float` is the type of
    2-dimensional arrays (i.e., matrices) of `Float`.

*   `Shaped`, the shape of the array is part of the type and is checked
    statically. E.g., `Array [2,3] Float` is the type of 2x3 arrays of `Float`.

Converting between these types is cheap since they all share the same underlying
trepresentation.

### Storage

Each of the type variants has several storage variants, indicated by a suffix of
the module names.

*   `G` The generic array type where you can provide your own storage.

*   `S` Uses `Data.Vector.Storable` for storage.

*   `U` Uses `Data.Vector.Unboxed` for storage.

*   ` ` (empty suffix) Uses `Data.Vector` for storage.

Conversion between different storage types requires copying the data, so it is
not a cheap operation.

## API

The library API is mostly structural operations, i.e., operations that
treat the elements in a uniform way.  For more algorithmic operations,
e.g., matrix multiplication, we suggest using a different library,
like `hmatrix`.

### Examples using `Dynamic`

Some preliminaries:

```
> import Data.Array.Dynamic
> import Text.PrettyPrint.HughesPJClass
> pp = putStrLn . prettyShow
```

An easy way to create an array from a list is to use `fromList`;
the first argument is the shape of the array.

```
> m = fromList [2,3] [1..6]
> m
fromList [2,3] [1,2,3,4,5,6]
> shapeL m
[2,3]
> rank m
2
> size m
6
```

Arrays can be pretty printed.  They are shown in the APL way:
The innermost dimension on a line, the next dimension vertically,
the next dimension vertically with an empty line in between, and so on.
Normally there is a box drawn around the array, but this can be changed by lowering
pretty printing level to `pPrintPrec`.

```
> pp m
┌─────┐
│1 2 3│
│4 5 6│
└─────┘
```

We can have an arbitrary number of dimensions.

```
> s = fromList [] [42]
> v = fromList [3] [7,8,9]
> a = fromList [2,3,4] [1..24]
> pp s
┌──┐
│42│
└──┘
> pp v
┌─────┐
│7 8 9│
└─────┘
> pp a
┌───────────┐
│ 1  2  3  4│
│ 5  6  7  8│
│ 9 10 11 12│
│           │
│13 14 15 16│
│17 18 19 20│
│21 22 23 24│
└───────────┘
```

Indexing into an array removes the outermost dimension of it by selecting a subarray with the given index.

```
> pp $ index v 1
┌─┐
│8│
└─┘
> shapeL $ index v 1
[]
> pp $ index a 1
┌───────────┐
│13 14 15 16│
│17 18 19 20│
│21 22 23 24│
└───────────┘
> pp $ a `index` 1 `index` 2 `index` 0
┌──┐
│21│
└──┘
```

The `scalar` and `unScalar` functions can be used to convert an element to/from and array.
```
> :type scalar 42
scalar 42 :: Num a => Array a
> :type index v 1
index v 1 :: Num a => Array a
> :type unScalar (index v 1)
unScalar (index v 1) :: Num a => a
```

The `constant` function makes an array with all identical elements.

```
> pp $ constant [2,3] 8
┌─────┐
│8 8 8│
│8 8 8│
└─────┘
```

Arrays are also instances of `Functor`, `Foldable`, and `Traversable`.

```
> pp $ fmap succ v
┌────────┐
│ 8  9 10│
└────────┘
> foldr (+) 0 a
300
```

The `transpose` operation can be used to rearrange the dimensions of an array.
The first argument describes how to transpose.

```
> shapeL a
[2,3,4]
> shapeL (transpose [1,0,2] a)
[3,2,4]
> pp $ transpose [1,0,2] a
┌───────────┐
│ 1  2  3  4│
│13 14 15 16│
│           │
│ 5  6  7  8│
│17 18 19 20│
│           │
│ 9 10 11 12│
│21 22 23 24│
└───────────┘
```

The `reshape` operation keeps the elements of an array,
but changes its shape.

```
> pp $ reshape [3,8] a
┌───────────────────────┐
│ 1  2  3  4  5  6  7  8│
│ 9 10 11 12 13 14 15 16│
│17 18 19 20 21 22 23 24│
└───────────────────────┘
```

An array can be turned into an array of arrays, where the outermost
array will have rank 1.
```
> pp $ unravel a
┌───────────────────────────┐
│┌───────────┐ ┌───────────┐│
││ 1  2  3  4│ │13 14 15 16││
││ 5  6  7  8│ │17 18 19 20││
││ 9 10 11 12│ │21 22 23 24││
│└───────────┘ └───────────┘│
└───────────────────────────┘
```

The `foldr` operation reduces an array to something of the element type.
Using `reduce` you will instead get an array result.
```
> pp $ reduce (+) 0 a
┌───┐
│300│
└───┘
```

Note how this operated on the entire array.  Using `rerank` it is possible
to use a function "deeper down".
```
> pp $ rerank 1 (reduce (+) 0) a
┌───────┐
│ 78 222│
└───────┘
> pp $ rerank 2 (reduce (+) 0) a
┌────────┐
│10 26 42│
│58 74 90│
└────────┘
> pp $ rerank 3 (reduce (+) 0) a
┌───────────┐
│ 1  2  3  4│
│ 5  6  7  8│
│ 9 10 11 12│
│           │
│13 14 15 16│
│17 18 19 20│
│21 22 23 24│
└───────────┘
```

To reduce along some dimension(s) that are not the innermost we can make them innermost by transpostion.
So to sum the columns:
```
> pp $ rerank 2 (reduce (+) 0) $ transpose [0,2,1] a
┌───────────┐
│15 18 21 24│
│51 54 57 60│
└───────────┘
```


### Similar examples using `Shaped`

```
> import Data.Array.Shaped
> :set -XDataKinds
> :set -XTypeApplications
```

The shape is now given by the type.

```
> m :: Array [2,3] Integer; m = fromList [1..6]
> m
fromList @[2,3] [1,2,3,4,5,6]
> shapeL m
[2,3]
> rank m
2
> size m
6
```

The type information can be given in different ways.

```
> s :: Array '[] Integer; s = fromList [42]
> v = fromList [7,8,9] :: Array '[3] Integer
> m = fromList @[2,3,4] [1..24]
```

There are also numeric instances for shaped arrays.
They allow pointwise arithmetic on arrays with the same shape.
Numeric constants are automatically of the right shape.

```
> import Data.Array.Shaped.Instances
> pp $ v * 2
┌────────┐
│14 16 18│
└────────┘
> pp $ a + a
┌───────────┐
│ 2  4  6  8│
│10 12 14 16│
│18 20 22 24│
│           │
│26 28 30 32│
│34 36 38 40│
│42 44 46 48│
└───────────┘
```

What is value arguments for `Dynamic` arrays sometimes turn into type arguments
for shaped arrays.

```
> pp $ reshape @[3,8] a
┌───────────────────────┐
│ 1  2  3  4  5  6  7  8│
│ 9 10 11 12 13 14 15 16│
│17 18 19 20 21 22 23 24│
└───────────────────────┘
```