The Fast Fourier Transform in Petalisp

fft.lisp

(use-package :petalisp)

(defun fft (x)
  (let ((n (shape-size (shape x))))
    (assert (= (shape-rank (shape x)) 1))
    (assert (zerop (logand n (1- n))) ()
            "The length is not a power of 2")
    (if (<= n 1)
        x
        (let* ((even (fft (reshape x (~ 0 2 (1- n))
                                     (τ (x) ((/ x 2))))))
               (odd  (fft (reshape x (~ 1 2 (1- n))
                                     (τ (x) ((/ (1- x) 2))))))
               (odd* (α #'* odd
                        (α #'cis
                           (α #'*
                              (/ pi (shape-size (shape x)) -0.5)
                              (indices odd))))))
          (fuse (α #'+ even odd*)
                (reshape (α #'- even odd*)
                         (τ (i) ((+ i (shape-size (shape odd)))))))))))

Sure, using pattern matching, collapse and the type is definitely nicer.

The code I had based this off used an append (and was pretty silly for using lists), and I was thinking about making a lazy array concatenate to make the last expression's purpose more obvious. stack is probably a better name if it can go in any dimension.