Skip to content

Instantly share code, notes, and snippets.

@beerose

beerose/consList.ts

Last active May 2, 2020
Embed
What would you like to do?
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)));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.