FFT With Circat  ## Metadata - Author: [[begriffs.com]] - Full Title: FFT With Circat - Category: #articles - Summary: David Banas uses the Fast Fourier Transform (FFT) in his daily work and is trying to find a way to make the calculation faster. His approach to this specific problem illustrates how to work at a high level of abstraction to minimize definition and maximize derivation. - URL: http://begriffs.com/posts/2015-12-14-fft-with-circat.html [David Banas](https://github.com/capn-freako) uses the Fast Fourier Transform (FFT) in his daily work and is trying to find a way to make the calculation faster. His approach to this specific problem illustrates how to work at a high level of abstraction to minimize definition and maximize derivation.  ##### Summary * David works with the Fast Fourier Transform which can be optimized with a logarithmic breakdown * Conal Elliott used a similar technique to find a solution to the “parallel scan” problem at below the order of algorithmic complexity previously believed to be a theoretical minimum * David wrote [TreeViz](https://github.com/capn-freako/treeviz) to visualize ways of breaking the computations down. The visualizations would help in attacking the FFT problem * Example of a dataflow graph * To build a general purpose FFT, why not start with how it operates on simple structures, then derive the more complicated cases? * Conal’s Mantra: “Minimal definition, maximal derivation!” * [Circat](https://github.com/conal/circat) represents circuits (and other things) using cartesian closed categories + It compiles regular Haskell right down into Verilog * The reason Circat is applicable to David’s work is its data structures and operations + It allows us to express FFT at a much higher level of abstraction than we typically do + We’ll use `RTree`, a perfect binary leaf tree parameterized only by its depth * Example of transition from list-based FFT (circa 2014) to the RTree way * Dive into the code * Future directions + Making FFT a typeclass + At first glance it’s not too significant, just a syntactic shuffle + But it may serve as a stepping stone toward defining primitives and deriving more complex structures + For instance they have defined a `phasor` for any Foldable + Next steps: define FFT instances for Id, Pair, and functor composition + Then use them to derive more complex structures on pairs of trees or trees of pairs * If you find this interesting David and Conal would love your help!, FFT With Circat, begriffs.com, 01gnmcyh07xyv97km0vvt7py9m.