Haskell Fast Fourier Transform

FFT.hs

import Data.Complex
import Control.Arrow
import Control.Monad

fft :: [Complex Double] -> [Complex Double]
fft = fft' . pad

-- perform a fast fourier transform
fft' :: [Complex Double] -> [Complex Double]
fft' [x] = [x]
fft' xs = zipWith (+) evens odds' ++ zipWith (-) evens odds'
   where odds'         = zipWith (*) ws odds
         (evens, odds) = pairMap fft' (halves xs)
         ws            = map (w n) [0..(n - 1)]
         n             = fromIntegral $ length xs

-- apply a function to both elements of a pair
pairMap :: (a -> b) -> (a, a) -> (b, b)
pairMap = join (***)

-- splits a list into a tuple of odd and even elements         
halves :: [a] -> ([a], [a])
halves = foldr (\a ~(x,y) -> (a:y,x)) ([],[])

-- the "-kth" nth complex root of unity
w :: Double -> Double -> Complex Double
w n k = mkPolar 1 ((-2) * k * pi / n)

-- pads a list with zeros so its length becomes a power of 2
pad :: [Complex Double] -> [Complex Double]
pad xs = xs ++ zeros 
   where zeros = replicate n 0
         n = (2 ^ p) - l
         p = ceiling $ logBase 2 (fromIntegral l)
         l = length xs