consList.ts

export type ConsList<T> = null | readonly [T, ConsList<T>];

function cons<T>(h: T, t: ConsList<T>): ConsList<T> {
  return [h, t];
}

function head<T>(xs: ConsList<T>): T {
  if (!xs) {
    throw new Error("can't take head of empty ConsList");
  }
  return xs[0];
}

function tail<T>(xs: ConsList<T>): ConsList<T> {
  if (!xs) {
    throw new Error("can't take tail of empty ConsList");
  }
  return xs[1];
}

const of = <T>(...xs: T[]): ConsList<T> => {
  let res: ConsList<T> = null;
  for (let i = xs.length - 1; i >= 0; --i) {
    res = cons(xs[i], res);
  }
  return res;
};

function reduce<T, R = T>(
  xs: ConsList<T>,
  reducer: (acc: R, val: T) => R,
  initialValue: R
): R {
  while (xs) {
    const [head, tail] = xs;
    initialValue = reducer(initialValue, head);
    xs = tail;
  }
  return initialValue;
}

function reverse<T>(xs: ConsList<T>): ConsList<T> {
  return reduce(xs, (acc, v) => cons(v, acc), null as ConsList<T>);
}

function map<A, B>(xs: ConsList<A>, f: (a: A) => B): ConsList<B> {
  let res: ConsList<B> = null;
  while (xs) {
    const [head, tail] = xs;
    res = [f(head), res];
    xs = tail;
  }
  return reverse(res);
}

const BENCHMARK_TIME = 1000; /* ms */

const { performance } = require('perf_hooks');

const benchmark = <TSetup>(setup: () => TSetup, f: (ctx: TSetup) => void) => {
  let ops = 0;
  let timeElapsed = 0;
  while (timeElapsed < BENCHMARK_TIME) {
    const ctx = setup();

    const start = performance.now();
    f(ctx);
    const end = performance.now();

    timeElapsed += end - start;

    ops++;
  }
  return `${f.toString().slice(6)} → ${(
    (ops * BENCHMARK_TIME) /
    timeElapsed
  ).toFixed(3)} ops/s`;
};

/**
 * benchmarks
 */

const REALISTIC_NUMBER_OF_THINGS_IN_PRODUCTION_APP = 10_000;

/**
 * setup
 */

const array = new Array(REALISTIC_NUMBER_OF_THINGS_IN_PRODUCTION_APP)
  .fill(0)
  .map(() => Math.random());

const list = of(...array);

const setupArray = () => [...array];
const setupList = () => list;

/**
 * actual benchmarks
 */

console.log(
  '(Mutable) Array.prototype.unshift vs Array.prototype.push vs cons \n'
);

console.log(benchmark(setupArray, (a) => a.unshift(50)));

console.log(benchmark(setupArray, (a) => a.push(50)));

console.log(benchmark(setupList, (l) => cons(50, l)));

console.log('\n \n(Immutable) array spread vs cons (the important part) \n');

console.log(benchmark(setupArray, (a) => [50, ...a]));

console.log(benchmark(setupArray, (a) => [...a, 50]));

console.log(benchmark(setupList, (l) => cons(50, l)));

console.log('\n\nArray.prototype.map vs map\n');

console.log(benchmark(setupArray, (a) => a.map((x) => x * 2)));

console.log(benchmark(setupList, (l) => map(l, (x) => x * 2)));