<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Hi all,<div class=""><br class=""></div><div class="">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:</div><div class=""><br class=""></div><div class=""><div class=""><font face="Menlo" class="">-- FFT implementation</font></div><div class=""><font face="Menlo" class="">-- Note my reversal of Ross' even/odd convention, below.</font></div><div class=""><font face="Menlo" class="">-- I did this, to remain consistent with the explanation, above, which came from a pre-existing work.</font></div><div class=""><font face="Menlo" class="">fft :: RealFloat b => Hom (Complex b) (Complex b)</font></div><div class=""><font face="Menlo" class="">fft = id :&: proc (e, o) -> do</font></div><div class=""><font face="Menlo" class=""> e' <- fft -< e</font></div><div class=""><font face="Menlo" class=""> o' <- fft >>> twiddle -< o</font></div><div class=""><font face="Menlo" class=""> unriffle -< f (e', o')</font></div><div class=""><font face="Menlo" class=""> where f (x, y) = (x + y, x - y)</font></div><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><font face="Menlo" class="">twiddle :: RealFloat b => Hom (Complex b) (Complex b)</font></div><div class=""><font face="Menlo" class="">twiddle = id :&: twiddle' 1</font></div><div class=""><font face="Menlo" class=""><br class=""></font></div><div class=""><font face="Menlo" class="">twiddle' :: RealFloat b => Int -> Hom (Pair (Complex b)) (Pair (Complex b))</font></div><div class=""><font face="Menlo" class="">twiddle' n = (id *** (* phi)) :&: (((twiddle' n') *** ((twiddle' n') >>> (arr ((* phi) `prod` (* phi))))) >>> unriffle)</font></div><div class=""><font face="Menlo" class=""> where phi = cis (-pi / (fromIntegral (2 ^ n)))</font></div><div class=""><font face="Menlo" class=""> n' = n + 1</font></div><div class=""><br class=""></div></div><div class="">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:</div><div class=""><br class=""></div><div class=""><pre style="box-sizing: border-box; overflow: auto; font-size: 14px; padding: 0px; margin-top: 0px; margin-bottom: 0px; line-height: inherit; word-break: break-all; word-wrap: break-word; border: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; border-bottom-right-radius: 0px; border-bottom-left-radius: 0px; white-space: pre-wrap; vertical-align: baseline;" class="">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</pre><div class=""><br class=""></div></div><div class="">And I’m wondering if anyone sees the flaw in my code.</div><div class=""><br class=""></div><div class="">More here:</div><div class=""><a href="https://htmlpreview.github.io/?https://github.com/capn-freako/Haskell_Misc/blob/master/Arrows_and_Computation/Arrows_and_Computation.html#ex17x" class="">https://htmlpreview.github.io/?https://github.com/capn-freako/Haskell_Misc/blob/master/Arrows_and_Computation/Arrows_and_Computation.html#ex17x</a></div><div class=""><br class=""></div><div class="">Thanks!</div><div class="">-db</div><div class=""><br class=""></div></body></html>