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

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 be made 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.