// module bench_list_sum

data IntList = INil | ICons(Int, IntList)

/// Tail-recursive list builder. Result = accumulator-prepended list.
fn cons_n_acc(n: Int, acc: IntList) -> IntList {
  if n == 0 {
    acc
  } else {
    tail cons_n_acc(n - 1, ICons(n - 1, acc))
  }
}

/// Build [0, 1, ..., n-1] :: IntList. Order doesn't matter for sum.
fn cons_n(n: Int) -> IntList {
  cons_n_acc(n, INil)
}

/// Tail-recursive sum.
fn sum_acc(xs: IntList, acc: Int) -> Int {
  match xs {
    INil => acc,
    ICons(h, t) => tail sum_acc(t, acc + h)
  }
}

/// Sum every element. Calls sum_acc with seed 0.
fn sum_list(xs: IntList) -> Int {
  sum_acc(xs, 0)
}

/// Build a list of length n, sum it, print the sum.
fn run_one(n: Int) -> Unit with IO {
  do io/print_int(sum_list(cons_n(n)))
}

fn main() -> Unit with IO {
  run_one(100000);
  run_one(1000000);
  run_one(3000000)
}
