Latest update Jan 8, 2003
Xarray, the eXtended array library, extends Haskell's ordinary arrays with a number of features:
Every extended array has bounds, that represents the set of indices where the array is defined. Extended arrays are of two kinds: finite arrays, that have ordinary array bounds, and infinite arrays with a special bound representing the universal set. Bounds are defined thus:
data Bounds a = B (a,a) | Universe deriving Eq
Two operations join and meet are defined on bounds. meet corresponds to set intersection, and join to the least bound enclosing the set union of the arguments. See the figure below. These operations are used by some of the operations on extended arrays.
inBounds :: Ix a => Bounds a -> a -> Bool tests indices for membership in the set defined by the bounds of the argument.
Three new array creation functions are provided:
mkarray (B ((1,1),(n,n))) (\(i,j) -> i+j), an nxn Vandermonde
matrix
mkarray Universe (\(i,j) -> i+j), an infinite Vandermonde matrix
finarray ((1,1),(n,n)) (\(i,j) -> i+j), same as first
infarray (\(i,j) -> i+j), same as second
It is common to apply operations elementwise on arrays, or to lift them from the element type to the array type. An example is to add two arrays elementwise. Unary operations can be lifted to arrays by fmap, but it is often desirable to lift operations of higher arity. The Liftable class provides three functions lift0, lift1, lift2 to lift constants, unary, and binary functions. Xarray provides an instance declaration for extended arrays, where lift0 lifts constants into infinite arrays, lift1 equals fmap, and lift2 applies binary operations elementwise on extended arrays. For instance, lift2 (+) a b will add a and b elementwise.
Extended numerical (floating, fractional) arrays are also made instances of Num, Floating, and Fractional respectively. This means that the operations in these classes can be applied directly on extended arrays, e.g., a+b to add a and b elementwise. Special versions of lifted relational operators are provided (they cannot be overloaded due to their type signatures): they have the name of the unlifted operator appended with "*". Thus, for instance, a ==* b returns a boolean array with the result of the elementwise comparison of a and b.
More details about the Liftable class and the provided lifted operations are found here.
Finally, Xarray provides a lifted conditional on extended arrays:
ifA :: (Ix a, Pord a) => (a -> Bool) -> Array a b -> Array a b -> b -> Array a bifA takes four arguments: a predicate over indices, two arrays, and a value of element type. It returns an array whose bounds is the join of the argument arrays' bounds. (ifA p a b x)!i is a!i if p i is True and i is within the bounds of a, b!i if p i is False and i is within the bounds of b, and x otherwise. Thus, x is a kind of "fill-in"-value, and can typically be 0 or Nothing. This kind of conditional can be used, for instance, to select rand values when solving PDE's over regular grids represented by arrays, or to define array concatenation operations.
Example:
ifA (inBounds a) a b x puts the array a "over" b.
You can think of a and b as pixel arrays representing
graphical 2D-objects, and x as a background color.
Projections select various subplanes of arrays, in different directions, and can also swap dimensions. A projection in a dimension means to fix the coordinate for that dimension. Projections can be made in several dimensions: if all dimensions are projected, then only a single array element remains. The unprojected dimensions are then mapped to the dimensions in the resulting array in a way specified by the particular projection.
The syntax of the projection function names is proj_c^n, where the symbols matching c are either "x" or a distinct number between 1 and the number m of non-x-symbols in the string. proj_c^n maps an n-dimensional array onto an m-dimensional array. An x in a certain position means that this dimension is projected, and a number that the dimension is mapped to the dimension with the given number in the resulting array. For instance, proj_1x a j selects column j from matrix a, proj_x1 a i row i, proj_12 a returns a itself, and proj_21 a the transpose of a. Xarray provides all projection operations on arrays up to dimension three. See the figure below for an example.
For convenient handling of common matrix operations, Xarray provides the aliases column = proj_1x, row = proj_x1, and transpose = proj_21.
Nesting operations are operations that convert a multidimensional array into an array of arrays. Since an array can be decomposed into subarrays of different shape, and in different directions, there are several nesting operations: two that decompose a 2D-array into a 1D-array (of rows or columns), three that decompose a 3D-array into a 1D-array of 2D-arrays, and three that decompose a 3D-array into a 2D-array of 3D-arrays. The naming conventions are similar to those for projections. See the figure below.
Xarray has a number of folds over arrays. They are all analogous with the usual folds for lists. There are two families: the first consists of "strict" folds, in the sense that they take all elements of the array into account (given that the folded operation is strict), and the second ignores array elements with the value Nothing. The second family is thus intended for "sparse" arrays with elements of Maybe type. The folds in the first family are named by appending "A" to the name of the corresponding list fold, and those in the second family by appending "M". All array folds give reasonable results only on finite arrays, and will yield an error if applied to an infinite array.
Two examples are:
foldlA :: Ix a => (b -> c -> b) -> b -> Array a c -> b, left fold all elements in an array in the order given by the elems function on standard arrays. Corresponds to foldl on lists.
foldlM :: Ix a => (b -> c -> b) -> b -> Array a (Maybe c) -> b, left fold all elements in an array with Maybe elements skipping the Nothing-valued elements.
Xarray also provides array counterparts to the other three list folds foldr, foldl1, and foldr1.
In combination with nesting operations, the array folds provide powerful means of performing "partial folds" over arrays in various directions resulting in lower-dimensional arrays. For matrices this is so common so Xarray provides two predefined partial folds:
foldrows :: (Functor (Array a), Ix b, Ix a, Ix (a,b)) => (c -> d
-> c) -> c -> Array (a,b) d -> Array a c, fold all rows of a matrix
into a 1D-array,
foldcols :: (Functor (Array a), Ix b, Ix a, Ix (b,a)) => (c -> d -> c)
-> c -> Array (b,a) d -> Array a c, ditto over the columns
For instance, foldrows max minBound a will compute an array of the maximal elements of each row of a. Xarray provides sumrows and sumcols since it is very common to sum over rows and columns in array and spreadsheet applications. It is easy to tailor other partial array folds for various purposes.
Masking operations are operations that select some part of an array without altering the dimensionality (as opposed to projections). Xarray provides the following masking operations:
at :: (Ix a, Pord a) => Array a b -> (a,a) -> Array a b, selects
the part of an array that is "cut out" by a finite bound. This operation
alters the bounds of the result.
when :: Ix a => (a -> Bool) -> Array a b -> b -> Array a b, selects
elements from an array according to a predicate that acts as "mask". The
array positions where the predicate is False are filled with a
given value. (when is therefore closely related to
ifA.) This operation does not alter the bounds of the result.
whenL :: Ix a => [a] -> Array a b -> b -> Array a b, similar to
when but masks out the array elements for the indices given in a
list.
Examples:
a `at` ((2,2),(m,n)) selects the 2..m x 2..n-submatrix of the
matrix a.
when (\i -> a!i /= Just 0) a Nothing returns a matrix with
the same extents as a but "blanked out" for all indices i
except where a!i /= Just 0.
whenL [(1,1),(1,2),(3,4)] a Nothing returns a matrix with the
same extents as a but "blanked out" with Nothing in all
cells except (1,1), (1,2), and (3,4).
It can sometimes be convenient to convert a list of 1D-arrays into a matrix or, conversely, to split a matrix into a list of rows or columns. For these purposes, Xarray provides conversion functions cols2matrix, rows2matrix, matrix2rows, and matrix2cols, with obvious semantics.
