This morning, I was catching up on the RSS feeds I follow. I noticed an interesting snippet of code in the Abstract Heresies journal for the Discrete-time Fourier Transform. Here is his snippet of code:
(define (dtft samples)
(lambda (omega)
(sum 0 (vector-length samples)
(lambda (n)
(* (vector-ref samples n)
(make-polar 1.0 (* omega n)))))))
My first thought was That’s way too short.
Then, I started reading through it. My next thought was, maybe I don’t understand scheme at all. Then, my next thought was, I do understand this code, it just didn’t do things the way I expected.
Here, I believe is a decent translation of the above into Common Lisp:
(defun dtft (samples)
#'(lambda (omega)
(loop for nn from 0 below (length samples)
summing (let ((angle (* omega nn)))
(* (aref samples nn)
(complex (cos angle) (sin angle)))))))
Now, what I find most interesting here is that most implementations you’ll find for the DTFT (Discrete-Time Fourier Transform) take an array of samples and a wavelength, and returns a result. This, instead, returns a function which you can call with a wavelength omega. It returns an evaluator. This is an interesting pattern that I will have to try to keep in mind. I have used it in some places before. But, I am sure there are other places that I should have used it, and missed. This is one where I would have missed.
Usage for the above would go something like:
(let ((dd (dtft samples)))
(dd angle1)
(dd angle2)
...)
For those not into Lisp either (who are you?), here is a rough translation into C++.
#include <cmath>
#include <complex>
class DTFT {
unsigned int len;
double* samples;
public:
DTFT( double* _samples, unsigned int _len ) {
this->len = _len;
this->samples = new double[ this->len ];
for ( unsigned int ii=0; ii < this->len; ++ii ) {
this->samples[ ii ] = _samples[ ii ];
}
}
~DTFT( void ) {
delete[] this->samples;
}
std::complex< double > operator () ( double omega ) const {
std::complex< double > sum( 0.0, 0.0 );
for ( unsigned int ii=0; ii < this->len; ++ii ) {
sum += this->samples[ ii ] * std::polar( 1.0, omega );
}
return sum;
}
};
With usage like:
DTFT dd( samples, 1024 );
dd( angle1 );
dd( angle2 );
...
So, six lines of Scheme or Lisp. Twenty-five lines of C++ including explicit definition of a class to act as a pseudo-closure, explicit copying and management of the samples buffer, etc. I suppose, a more direct translation would have used a std::vector to hold the samples and would have just kept a pointer to the buffer. That would have shaved off six or seven lines and the whole len and _len variables.
