Regular, shape-polymorphic, parallel arrays in Haskell

We present a novel approach to regular, multi-dimensional arrays in Haskell. The main highlights of our approach are that it (1) is purely functional, (2) supports reuse through shape polymorphism, (3) avoids unnecessary intermediate structures rather than relying on subsequent loop fusion, and (4) supports transparent parallelisation. We show how to embed two forms of shape polymorphism into Haskell’s type system using type classes and type families. In par-ticular, we discuss the generalisation of regular array transforma-tions to arrays of higher rank, and introduce a type-safe specifica-tion of array slices. We discuss the runtime performance of our approach for three standard array algorithms. We achieve absolute performance com-parable to handwritten C code. At the same time, our implementa-tion scales well up to 8 processor cores. Categories and Subject Descriptors D.3.3 [Programming Lan