### FFT With Circat

##### December 14, 2015

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.

### 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
- Can we implement FFT below \(O(n\log{}n)\)?
- David wrote 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 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 - It’s nice for FFT because it enforces a \(\log_2\) breakdown of any input vector

- 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!