An approach to fast arrays in Haskell

Manuel M.T. Chakravarty*, Gabriele Keller

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Many array-centric algorithms from computational science and engineering, especially those based on dynamic and irregular data structures, can be coded rather elegantly in a purely functional style. The challenge, when compared to imperative array languages, is performance. These lecture notes discuss the shortcomings of Haskell's standard arrays in this context and present an alternative approach that decouples array from list processing and is based on program transformation and generic programming. In particular, we will present (1) an array library that uses type analysis to achieve unboxing and flattening of data structures as well as (2) equational array fusion based on array combinators and compiler-driven rewrite rules. We will make use of a range of advanced language extensions to Haskell, such as multi-parameter type classes, functional dependencies, rewrite rules, unboxed values, and locally state-based computations.

Original languageEnglish
Pages (from-to)27-58
Number of pages32
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2638
Publication statusPublished - 1 Dec 2004
Externally publishedYes

Fingerprint

Dive into the research topics of 'An approach to fast arrays in Haskell'. Together they form a unique fingerprint.

Cite this