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

G. Hains (Editor), Pieter H. Hartel, W.G. Vree, L.M.R. Mullin (Editor)

    Research output: Contribution to conferencePaperAcademicpeer-review

    66 Downloads (Pure)

    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.
    Original languageUndefined
    Pages52-66
    Number of pages15
    Publication statusPublished - Jun 1992
    Event2nd Arrays, functional languages and parallel systems (ATABLE) - Montreal, Canada
    Duration: 1 Jun 19921 Jun 1992

    Conference

    Conference2nd Arrays, functional languages and parallel systems (ATABLE)
    Period1/06/921/06/92

    Keywords

    • EWI-1202
    • IR-55744

    Cite this