FlatPack: an affordable range of large multi-dimensional arrays

FlatPack is a Haskell library for expressing computations on multi-dimensional rectangular arrays. Dimensions are not expressed in Haskell's type system, but there is runtime shape inference/checking instead. Thus, expressions that change the dimension of constituent arrays, or are polymorphic over dimensional shape, are more easily expressed than in any other array library currently available, with the caveat that checking their correctness is not static.

All operations over FlatPack arrays are aggregate operations - at the array level. Algorithms that might traditionally be formulated in terms of incremental creation or modification of arrays must instead be expressed over entire arrays. This raises the abstraction level, and frees the underlying implementation to be more clever in how it computes the specified result.

The name FlatPack comes from the fact that all values held within arrays are unboxed and packed closely into a flat structure, to use space as compactly as possible. In addition, many operations on FlatPack arrays can avoid copying or traversing the array at all - based on a kind of fusion of intermediate arrays. Thus, FlatPack arrays are especially well suited to large quantities of data, which might otherwise overflow the heap.

There are some research questions being actively investigated through the FlatPack representation.

1. How far can we push the fusion mechanism to eliminate intermediate array copying, and unnecessary traversals? At the moment, operations that are purely structural are cheap: this includes slicing, subranging, transposition, and dimensional rotation. But operations that are data-dependent are more expensive because they require intermediate storage allocation: arithmetic expressions, folds, and maps. However, there are real possibilities to eliminate the intermediate structures for the latter operations too, through using more sophisticated representations, together with deeper analysis.
2. Because all array operations are aggregate ops, the opportunities for exploiting data-parallel computational resources (single-CPU SIMD, multi-core, and GPGPU) are very obvious. We already hope that fusion will provide a significant performance boost on sequential hardware; the potential exists to make easy use of parallel hardware in addition.

Right now, FlatPack has not been officially released, but you can freely use the development darcs repo, located at

darcs get http://www.cs.york.ac.uk/fp/darcs/FlatPack

Build and install using

    cabal install

Detailed documentation of the FlatPack API is generated automatically by Haddock directly from the source code.

Development version:

darcs get http://www.cs.york.ac.uk/fp/darcs/FlatPack

To install FlatPack, you must have a Haskell compiler, and cabal. Use the standard Cabal method of installation:

    runhaskell Setup.hs configure [--prefix=...] [--buildwith=...]
    runhaskell Setup.hs build
    runhaskell Setup.hs install

Version 0.1 will be the first official release (not yet available).

We are interested in hearing your feedback on this library - suggestions for improvements, comments, criticisms, bug reports. Please mail

• Malcolm.Wallace@cs.york.ac.uk

Licence: The library is Free and Open Source Software, i.e., copyright to us, but freely licensed for your use, modification, and re-distribution, provided you don't restrict anyone else's use of it. The FlatPack library is distributed under the GNU Lesser General Public Licence (LGPL) - see file LICENCE-LGPL for more details. We allow one special exception to the LGPL - see COPYRIGHT. (If you don't like any of these licensing conditions, please contact us to discuss your requirements.)

• Other array libraries should be described here.