I've come to internalize the Fourier transform as a type of sparse matrix algorithm. I.e. something that implements a particular matrix-vector product without requiring explicit construction of said matrix.
It's linear and so in the discrete case can be expressed as matrix multiplication (every discrete linear operation is expressible as matmul).