Discrete Fourier Transform

dft.clj

(ns dft.core)

(defn fft [x]
  (let [length (count x)]
    (if (<= length 1)
      (->> x
           (persistent!)
           (vec))
      (let [x (transient x)
            even (recur (map #(nth % x) (range length)))
            odd (recur (map #(nth % x) (range 1 length)))
            aux (map #(* (Math/exp (/ (* (complex 0 -2) Math/pi %) length))
                         (nth % odd))
                     (range (quot length 2)))] 
        (recur (concat (map + even aux)
                       (map - even aux)))))))

(map #(format "~a~&" %)
     (fft [1 1 1 1 0 0 0 0]))