dft in vine

dft.vi

use std::ops::{Cast, arithmetic::{Add, Mul}};
use std::data::Array;
use debug::Show;

struct C32({ re: F32, im: F32 });

mod C32 {
  pub const ZERO: C32 = C32({ re: 0.0, im: 0.0 });

  pub impl fork: Fork[C32] = unsafe::duplicate;
  pub impl drop: Drop[C32] = unsafe::erase;

  pub impl add: Add[C32, C32, C32] {
    fn add(a: C32, b: C32) -> C32 {
      C32({ re: a.re + b.re, im: a.im + b.im })
    }
  }

  pub impl mul: Mul[C32, C32, C32] {
    fn mul(a: C32, b: C32) -> C32 {
      C32({ re: a.re * b.re - a.im * b.im, im: a.re * b.im + a.im * b.re })
    }
  }

  pub impl mul_f32: Mul[C32, F32, C32] {
    fn mul(a: C32, b: F32) -> C32 {
      C32({ re: a.re * b, im: a.im * b })
    }
  }

  pub impl from_f32: Cast[F32, C32] {
    fn cast(x: F32) -> C32 {
      C32({ re: x, im: 0.0 })
    }
  }

  pub impl show: Show[C32] {
    fn show(&self: &C32) -> Show {
      Show::Tuple([self.re.show(), self.im.show()])
    }
  }
}

fn exp_ipi(x: F32) -> C32 {
  C32({ re: cospi(x), im: sinpi(x) })
}

fn sinpi(x: F32) -> F32 {
  const PI: F32 = F32::from_bits(0x40490fdb);
  let t = ((x - 1.0) % 2.0) - 1.0;
  when {
    t == 0.0 { 0.0 }
    t == -1.0 { 0.0 }
    t == 0.5 { 1.0 }
    t == -0.5 { -1.0 }
    _ { t * PI - ((t * PI) ** 3) / 6.0 + ((t * PI) ** 5) / 120.0 - ((t * PI) ** 7) / 5040.0 }
  }
}

fn cospi(x: F32) -> F32 {
  sinpi(x + 0.5)
}

fn dft(&xs: &List[C32]) -> List[C32] {
  let N = xs.len();
  (0..N).map(fn* (k: N32) {
    let kN = (k as F32) / (N as F32);
    xs.into_iter().enumerate().fold(
      C32::ZERO,
      fn* (a, (n: N32, x: C32)) { a + x * exp_ipi(-2.0 * kN * (n as F32)) },
    )
  }).collect[List, _, _]()
}

pub fn main(&io: &IO) {
  let x = [
    1.0 as C32,
    C32({ re: 2.0, im: -1.0 }),
    C32({ re: 0.0, im: -1.0 }),
    C32({ re: -1.0, im: 2.0 }),
  ];
  io.println("{dft(&x).show()}");
}