# [Haskell-cafe] FFT, via homogeneous functions?

David Banas capn.freako at gmail.com
Mon Nov 7 14:25:20 UTC 2016

```Hi all,

I’m trying to implement the fast Fourier transform (FFT), using the homogeneous functions described in Sec. 4.2 of *Arrows and Computation* by Ross Paterson:

-- FFT implementation
-- Note my reversal of Ross' even/odd convention, below.
-- I did this, to remain consistent with the explanation, above, which came from a pre-existing work.
fft :: RealFloat b => Hom (Complex b) (Complex b)
fft = id :&: proc (e, o) -> do
e' <- fft             -< e
o' <- fft >>> twiddle -< o
unriffle -< f (e', o')
where f (x, y) = (x + y, x - y)

twiddle :: RealFloat b => Hom (Complex b) (Complex b)
twiddle = id :&: twiddle' 1

twiddle' :: RealFloat b => Int -> Hom (Pair (Complex b)) (Pair (Complex b))
twiddle' n = (id *** (* phi)) :&: (((twiddle' n') *** ((twiddle' n') >>> (arr ((* phi) `prod` (* phi))))) >>> unriffle)
where phi = cis (-pi / (fromIntegral (2 ^ n)))
n'  = n + 1

I’m getting this output, which means that, while my *twiddle* function is working for all tree depths tested, my *fft* function fails for tree depths greater than 3:

Tree depth: 0
Testing twiddles...True
Testing FFT...True
Tree depth: 1
Testing twiddles...True
Testing FFT...True
Tree depth: 2
Testing twiddles...True
Testing FFT...True
Tree depth: 3
Testing twiddles...True
Testing FFT...True
Tree depth: 4
Testing twiddles...True
Testing FFT...False
Tree depth: 5
Testing twiddles...True
Testing FFT...False

And I’m wondering if anyone sees the flaw in my code.

More here: