## A Fast Fourier Transform in Lisp

I had learned a little Lisp many years ago and always meant to go
back. For a PLIBMTTBHGATY event (`programming language I've been
meaning to try but haven't got around to yet' --- thanks to
Christine Corbett Moran
who organized it) that seemed close enough. Here's my attempt to
write an FFT with functional programming, without any variable
assignments. It is `fast' in the sense of *N* log(*N*)
time, but the coefficient is surely large.

Program is in the
Scheme
dialect of Lisp.

; Take elements 0,2,4... and 1,3,5... of a list
(define (evens f)
(if (null? f) '()
(cons (car f) (evens (cddr f)))
)
)
(define (odds f)
(if (null? f) '()
(cons (cadr f) (odds (cddr f)))
)
)
; Length of a list
(define (len f)
(if (null? f) 0
(+ 1 (len (cdr f)))
)
)
; Multiply by exp(2 pi i k/N)
(define (phase s k N)
(exp (/ (* 0+2i s k 3.1415926535 ) N) )
)
(define (rotate s k N f)
(if (null? f) '()
(cons (* (phase s k N) (car f)) (rotate s (+ k 1) N (cdr f)))
)
)
; With these preliminaries FFT is simple
(define (four s f)
(if (= 1 (len f)) f
(combine s (four s (evens f)) (four s (odds f)))
)
)
(define (combine s ev od)
(plusminus ev (rotate s 0 (len od) od))
)
(define (plusminus a b)
(append (map + a b) (map - a b))
)
; A little test
(four -1 (four 1 '(1 -6 2 4)))

Lots of very clever people have written about how awesome Lisp is.
Paul Graham
articulates it particularly well. Lisp, he argues, is what every
other programming language, deep down, wants to be. And the reason
Python is so cool is that it's most of the way there. Once in a
while, a new language manages to reach all the way to Lisp. And then
it wakes up and finds it's not a new language at all, it's just
another dialect of Lisp.

Looking at recent developments on ClojureScript, I think he may be
right.