fft.rkt

#lang racket

(define (split x)
  (match x
    ['() '(() . ())]
    [(list-rest x y zs)
     (match-let ([(cons xs ys) (split zs)])
       (cons
        (cons x xs)
        (cons y ys)))]))

(define (cis a)
  (exp (* 0+1i a)))

(define (double xs) (append xs xs))

(define (fft v)
  (match v
    ['() '()]
    [(list x) (list x)]
    [_ (match-let* ([(cons evens odds) (split v)]
                    [evens-fft (fft evens)]
                    [odds-fft (fft odds)]
                    [n (length v)]
                    [w (cis (/ (* 2 pi) n))]
                    [ks (stream->list (in-range n))]
                    [ws (map (lambda (k) (expt w k)) ks)])
         (map (lambda (a w b) (+ a (* w b)))
              (double evens-fft)
              ws
              (double odds-fft)))]))