VictorTaelin

Implementing complex numbers and FFT with just datatypes (no floats)

In this article, I'll explain why implementing numbers with just algebraic datatypes is desirable. I'll then talk about common implementations of FFT (Fast Fourier Transform) and why they hide inherent inefficiencies. I'll then show how to implement integers and complex numbers with just algebraic datatypes, in a way that is extremely simple and elegant. I'll conclude by deriving a pure functional implementation of complex FFT with just datatypes, no floats.

snoyberg

#!/usr/bin/env stack
-- stack --resolver lts-11.10 script
{-# LANGUAGE NoImplicitPrelude #-}
import RIO
import Conduit
import Control.Concurrent.STM.TBMQueue

doesn'tStall
  :: MonadUnliftIO m
  => Int -- ^ number of microseconds