Skip to content

Instantly share code, notes, and snippets.

@monzee

monzee/list.ts

Created April 25, 2020 05:36
Show Gist options
  • Save monzee/d97519f67736a6fd37cd2327c6ae2372 to your computer and use it in GitHub Desktop.
Save monzee/d97519f67736a6fd37cd2327c6ae2372 to your computer and use it in GitHub Desktop.
Download ZIP
Church-encoded sum types in typescript
Raw
list.ts
type Sum<K> = <T> (cases: Pattern<K, T>) => T;
type Pattern<K, T> = {
[C in keyof K]?: K[C] extends any[] ? (...args: K[C]) => T : never;
} & {
otherwise?: () => T
}
type List<T> = Sum<{nil: [], cons: [T, List<T>]}>;
function fallback<T>(): T {
throw new Error("unimplemented");
}
function empty<A>(): List<A> {
return ({nil = fallback}) => nil();
}
function append<A>(head: A, tail: List<A>): List<A> {
return ({cons = fallback}) => cons(head, tail);
}
function listOf<A>(...elems: A[]): List<A> {
let list = empty<A>();
for (let e of elems.reverse()) {
list = append(e, list);
}
return list;
}
function forEach<A>(list: List<A>, block: (a: A) => void) {
list({
nil() {},
cons(a, as) {
block(a);
forEach(as, block);
}
});
}
function map<A, B>(source: List<A>, transform: (a: A) => B): List<B> {
return ({nil: bNil = fallback, cons: bCons = fallback}) => source({
nil() {
return bNil();
},
cons(head, tail) {
return bCons(transform(head), map(tail, transform));
}
});
}
function reduce<A, B>(list: List<A>, zero: B, combine: (a: A, b: B) => B): B {
return list({
nil() {
return zero;
},
cons(a, as) {
return reduce(as, combine(a, zero), combine);
}
});
}
function count(list: List<any>): number {
return reduce(list, 0, (_, count) => count + 1);
}
function sum(numbers: List<number>): number {
return reduce(numbers, 0, (a, b) => a + b);
}
let ns = listOf(1, 2, 3, 4, 5);
let words = listOf(..."the quick brown fox jumps over the lazy dog".split(" "));
console.log(sum(ns));
console.log(count(words));
forEach(map(words, s => `${s}: ${s.length}`), console.log);
@monzee
Copy link
Author

monzee commented Apr 25, 2020

playground: https://www.typescriptlang.org/v2/en/play?#code/C4TwDgpgBAygrgWwDwGkB8UC8UkBUMAUAxgIYDOEZAXFAAonDAQBOAdqgDRT4CUWGuANwAoUJDoMmbTtwzYA3sKjKoAbQDCUAJasoAawggA9gDMoKALoB+Gig0WoEAB5NWAEzJQSrEKodWoAgA6EJJmAHNqc3s+TAEoGlYIADcWEQBfKAAyKEUVKCNgAAsWAHctChtA2IFhdOFRcGgAGQrgPDlYRCR5Vi0AGxo-LiIjVijVXC5Wsnb8C3S0EWETOFYiYC0xqBMSfv6AIxIiPQ6CHhpcXKUVYuYjUqgkx4BRZnvmAgAiNa0EMH6EAQEFYTDcXx4GQaq3Wm22QLAoCQAEE0OcaDN2qjrvlmBBgHA2IFegMsDs9odjnp0jUngNzlCVmsNltdCQwJB3Ci0SUSG4aMiuMASAMMW1uRcoJjuTiVHiCUSCPJRuMybt9kcTjT+FAVWQCLy3EKRf1IXVocy4bp+m0APImbnBEIQQEIKLIvyS6XYvIqQHAKA22ZkhFI1EMm7KExGZiBf2OApmF1AshBPGpZgUc58X35ZRBgPYdmctwECBcAtm-L1XH4wnWtqMmEs7bR5gvY5FR0FsWzblcA79IwnGgEEgC2nJIxaNw5yOBtpK+f5Pr9c65dIcZcqPVjrjkOd5o9QQfDvRjqvH-JtjtEIpjsgDocnS9HmsqGlNy2sqAIdkorgACE0TIIxCSICBeyxNAhWYbwyDbBBR3HKBkVpQCvXFYDZWUeV62JVcaAOAA5UlsHVSkThGMYogOdQaLVClNWpWlQPAiAlyvVd11zK8oDwokSPpV8803Bor13Q1jQGQ8+NwutBPo8YCGAODxkQg0ID5HguD-MAVJNWD4MQngROredP3NJlYR-PE3DgCCAKgYCCB7KVxVRLgAC8WCMGhAOohADh0SDAhQwUT389DJUAnD+IUhtZk449uNkuSBN0Hz7hEK8xIkmi9y8Mg0r4jL4vsiCH0C4KkkKrKjB03UjCCkKzI-CyzXqayW10UY1mAVy2igpBvBANBJVYRADhYOKyrshyOILLgAAYuAIAB9aj+tpPrQSgABqKAAEZOotGztjIRACEmoKWCiaUbum5hxsSKaZt4uaIAqjjHrula1pIAdaRIA6T1Ohp41VbAC3tAgjq4AAmLgAGYuAAFi4ABWM141KGMPDJGGTCdIIvmKaAAEc4C0E4T3uUpdGjJwoAAK0QMBPCMDMoHJwMSC8kAoDcIxwi+IIyABLQBq+KAITNPUjEBIIh3CAhLoQa7ivlmjFYgZWReIMDQQIPHmA8UyRBvTsCD0k38cfKBPDiKAAAMABJ5DIdIaA91NAVYcJinSF3GoVpWVchIA

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment