31 lines
924 B
Text
31 lines
924 B
Text
module Main
|
|
|
|
import Data.Complex
|
|
|
|
|
|
concatPair : List (a, a) -> List (a)
|
|
concatPair xs with (unzip xs)
|
|
| (xs1, xs2) = xs1 ++ xs2
|
|
|
|
fft' : List (Complex Double) -> Nat -> Nat -> List (Complex Double)
|
|
fft' (x::xs) (S Z) _ = [x]
|
|
fft' xs n s = concatPair $ map (\(x1,x2,k) =>
|
|
let eTerm = ((cis (-2 * pi * ((cast k) - 1) / (cast n))) * x2) in
|
|
(x1 + eTerm, x1 - eTerm)) $ zip3 left right [1..n `div` 2]
|
|
|
|
where
|
|
left : List (Complex Double)
|
|
right : List (Complex Double)
|
|
left = fft' (xs) (n `div` 2) (2 * s)
|
|
right = fft' (drop s xs) (n `div` 2) (2 * s)
|
|
|
|
|
|
-- Recursive Cooley-Tukey with radix-2 DIT case
|
|
-- assumes no of points provided are a power of 2
|
|
fft : List (Complex Double) -> List (Complex Double)
|
|
fft [] = []
|
|
fft xs = fft' xs (length xs) 1
|
|
|
|
|
|
main : IO()
|
|
main = traverse_ printLn $ fft [1,1,1,1,0,0,0,0]
|