Fast Fourier transform: Difference between revisions

Content added Content deleted

Inline

@@ Line 360: / Line 360: @@
 =={{header|Haskell}}==
-<lang haskell>import Control.Monad
+<lang haskell>import Data.Complex
-import Data.Array
-import Data.Complex
 -- Cooley-Tukey
@@ Line 369: / Line 367: @@
 fft xs = zipWith (+) ys ts ++ zipWith (-) ys ts
     where n = length xs
-          xs' = listArray (1,n) xs
+          ys = fft evens
-          ys = fft $ map (xs'!) [1,3..n]
+          zs = fft odds
-          zs = fft $ map (xs'!) [2,4..n]
+          (evens, odds) = split xs
-          ts = zipWith (\z k -> (exp' k n) * z) zs [0..(n `div` 2)-1]
+          split [] = ([], [])
+          split [x] = ([x], [])
+          split (x:y:xs) = (x:xt, y:yt) where (xt, yt) = split xs
+          ts = zipWith (\z k -> exp' k n * z) zs [0..]
           exp' k n = cis $ -2 * pi * (fromIntegral k) / (fromIntegral n)
+main = mapM_ print $ fft [1,1,1,1,0,0,0,0]</lang>
-main =
-    do let res = fft [1,1,1,1,0,0,0,0]
-       forM_ res print</lang>
 And the output: