Created
January 18, 2015 22:42
-
-
Save matthewpalmer/e8039ea3b49584c1d2ad to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{- | |
rkat / FFT.hs | |
Created on Apr 9, 2012 | |
https://gist.github.com/rkat/2341767 | |
-} | |
module FFT ( fft | |
) where | |
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment