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.