Multidimensional arrays inspired by APL.

Multidimensional arrays inspired by APL. The library contains a wide variety of structural operations on arrays, but not actual algorithms.

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│
└───────────────────────┘