Abstract | ||
---|---|---|
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 particular, we discuss the generalisation of regular array transformations to arrays of higher rank, and introduce a type-safe specification of array slices. We discuss the runtime performance of our approach for three standard array algorithms. We achieve absolute performance comparable to handwritten C code. At the same time, our implementation scales well up to 8 processor cores. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1145/1932681.1863582 | international conference on functional programming |
Keywords | Field | DocType |
parallel array,standard array algorithm,regular array transformation,array slice,data parallelism,shape polymorphism,type family,multi-dimensional array,novel approach,type class,haskell,absolute performance,type system,arrays,loop fusion,polymorphism | Loop fusion,Programming language,Functional programming,Computer science,Parallel computing,Algorithm,Type theory,Haskell,Declarative programming,Standard array,Multi-core processor,Parallel array | Conference |
Volume | Issue | ISSN |
45 | 9 | 0362-1340 |
Citations | PageRank | References |
49 | 1.84 | 14 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gabriele Keller | 1 | 657 | 36.02 |
Manuel M. T. Chakravarty | 2 | 666 | 41.89 |
Roman Leshchinskiy | 3 | 326 | 14.89 |
Simon L. Peyton Jones | 4 | 5036 | 381.19 |
Ben Lippmeier | 5 | 135 | 7.99 |