signal = [
	0, 1, 1.22460635382238e-16, -1, -2.44921270764475e-16, 1, 3.67381906146713e-16, -1
  ]

main = print $ dft signal

dft :: [Double] -> [(Double,Double)]
dft sig = rdft 0 (length sig)
 where
  rdft :: Int -> Int -> [(Double,Double)]
  rdft i n | i == n = []
           | True = let rval = rdft' 0 i n
                        ival = idft' 0 i n
                    in ((if (abs rval) < 1.0e-10 then 0 else rval),(if (abs ival) < 1.0e-10 then 0 else ival)):(rdft (i+1) n)

  rdft' j i n | j == n = 0
              | True = let val = head $ reverse $ take (j+1) sig
                       in (val * (cos ((2 * pi * (fromIntegral i) * (fromIntegral j))/(fromIntegral n)))) + (rdft' (j+1) i n) 

  idft' j i n | j == n = 0
              | True = let val = head $ reverse $ take (j+1) sig
                       in ((val * (sin ((2 * pi * (fromIntegral i) * (fromIntegral j))/(fromIntegral n))))*(-1)) + (idft' (j+1) i n)