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]