Task

Calculate the   FFT   (Fast Fourier Transform)   of an input sequence.

The most general case allows for complex numbers at the input
and results in a sequence of equal length, again of complex numbers.
If you need to restrict yourself to real numbers, the output should
be the magnitude   (i.e.:   sqrt(re2 + im2))   of the complex result.

The classic version is the recursive Cooley–Tukey FFT. Wikipedia has pseudo-code for that.
Further optimizations are possible but not required.




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]