Compilation of Haskell Array Comprehensions for Scientific Computing

Abstract

Monolithic approaches to functional language arrays, such as Haskell array comprehensions, define elements all at once, at the time the array is created, instead of incrementally. Although monolithic arrays are elegant, a naive implementation can be very inefficient. For example, if a compiler does not know whether an element has zero or many definitions, it must compile runtime tests. If a compiler does not know inter-element data dependencies, it must resort to pessimistic strategies such as compiling elements as thunks, or making unnecessary copies when updating an array.