🚀 go-pugleaf

farrell@coral.cs.jcu.edu.au (John Farrell) writes:

>"A Functional Program for the Fast Fourier Transform"
>by Fer-Jan de Vries, Dept of Philosophy, University of Utrecht,
>Heidelberglaan 2, 3584 CS Utrecht, The Netherlands.

>It's on pp67-74 but I didn't copy what of! The papers are typeset differently,
>so it's not an actual proper book.

My biblio file says:

de Vries, F. J., "A Functional Program For The Fast Fourier
Transform," SIGPLAN, vol. 23, no. 1, pp. 67 - 75, ACM, 1988.

-- 
Yasuo Kozato                      kozato@canon.co.uk
Canon Research Centre Europe

At the last ATABLE-92 workshop in Montreal we presented a paper
discussing the FFT in Miranda. The proceedings are not out yet, but I
can send out copies of a technical report to those interested:

\title{ Arrays in a Lazy Functional Language -- \\
        a case study: the Fast Fourier Transform}

\author{Pieter H. Hartel and Willem G. Vree \\
        Department of Computer Systems \\
        University of Amsterdam \\
        Kruislaan 403, 1098 SJ Amsterdam, The Netherlands}

\begin{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 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.
\end{abstract}