open System open System.Numerics let rec fft = function | [] -> [] | [x] -> [x] | x -> x |> List.mapi (fun i c -> i % 2 = 0, c) |> List.partition fst |> fun (even, odd) -> fft (List.map snd even), fft (List.map snd odd) ||> List.mapi2 (fun i even odd -> let btf = odd * Complex.FromPolarCoordinates(1., -2. * Math.PI * (float i / float x.Length )) even + btf, even - btf) |> List.unzip ||> List.append // use let input = [for x in 0. .. 15. -> cos(x) + cos(4.0 * x)] let output = input |> List.map (fun r -> Complex(r, 0.)) |> fft |> List.map (fun c -> c.Real)