Arrays in a lazy functional language -- a case study: the fast Fourier transform


Hartel, P.H. and Vree, W.G. (1992) Arrays in a lazy functional language -- a case study: the fast Fourier transform. In: 2nd Arrays, functional languages and parallel systems (ATABLE), Montreal, Canada. pp. 52-66. Publication 841. (pp. pp. 52-66).

open access
Abstract:The array plays a prominent role in imperative programming languages because the data structure bears a close resemblance to the mathematical notion of a vector and because array operations can be implemented efficiently. Not all lazy functional languages offer arrays as a primitive data structure because laziness makes it difficult to implement arrays efficiently. We study 8 different versions of the Fast Fourier Transform, with and without arrays, to assess the importance of arrays in a lazy functional language. An efficient implementation of arrays contributes significantly to the performance of functional languages in certain areas. However, a clear distinction should bemade between array construction and array subscription. In the FFT example we could not gain efficiency by using array construction, other than for storing precomputed data like the input. Using array subscription improves performance.
Item Type:Conference or Workshop Item
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page