I translated a simple and elegant fft from lisp to smalltalk. The smalltalk was as nice if not nicer. The fft algorithm seemed simple once details of storage allocation were passed off to the garbage collector.

I can't remember where I found the lisp code. It must have been from some tutorial engineering notes from MIT or something. I remember it having a structure similar to this version in OCaml. rosettacode

let fac k n = let m2pi = -4.0 *. acos 0.0 in polar 1.0 (m2pi*.(float k)/.(float n)) let merge l r n = let f (k,t) x = (succ k, (mul (fac k n) x) :: t) in let z = List.rev (snd (List.fold_left f (0,[]) r)) in (List.map2 add l z) @ (List.map2 sub l z) let fft lst = let rec ditfft2 a n s = if n = 1 then [List.nth lst a] else let odd = ditfft2 a (n/2) (2*s) in let even = ditfft2 (a+s) (n/2) (2*s) in merge odd even n in ditfft2 0 (List.length lst) 1;;

A friend and visiting professor in our lab took interest in this work. He told me that it was the beauty of the fft that attracted him to a career in academic ee/cs.