An Approach to Fast Arrays in Haskell

@incollection{citeulike:1875441, 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.}, author = {Chakravarty, Manuel M. and Keller, Gabriele }, citeulike-article-id = {1875441}, journal = {Advanced Functional Programming}, keywords = {arrays, combinators, fusion, performance, rewriting, unboxed-values}, pages = {27--58}, posted-at = {2008-04-23 19:16:11}, priority = {2}, title = {An Approach to Fast Arrays in Haskell}, url = {http://www.springerlink.com/content/93amy8yr5m49kd3u }, year = {2003} }

TY - CHAP ID - citeulike:1875441 L3 - citeulike-article-id:1875441 TI - An Approach to Fast Arrays in Haskell JF - Advanced Functional Programming SP - 27 EP - 58 N2 - 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. KW - arrays KW - combinators KW - fusion KW - performance KW - rewriting KW - unboxed-values AU - Chakravarty, Manuel AU - Keller, Gabriele PY - 2003/// UR - http://www.springerlink.com/content/93amy8yr5m49kd3u ER -