deepakkumarnd · May 19, 2023 12:45 · May 19, 2023
diff --git a/List.ts b/List.ts
@@ -0,0 +1,223 @@
+const identity = <T extends any>(x: T) => x;
+
+abstract class List<T> {
+    abstract prepend(el: T): List<T>;
+    abstract map<B>(fn: (e: T) => B): List<B>;
+    abstract flatMap<B>(fn: (e: T) => List<B>): List<B>;
+    abstract filter(fn: (e: T) => boolean): List<T>;
+    abstract merge(other: List<T>): List<T>;
+    abstract foldLeft<B>(fn: (e: T, z: B) => B, z: B): B;
+    abstract foldRight<B>(fn: (e: T, z: B) => B, z: B): B;
+    abstract count(): number;
+    abstract reduce(fn: (x: T, acc: T) => T, z: T): T;
+    abstract reverse(): List<T>;
+    abstract head(): T;
+    abstract tail(): List<T>;
+    abstract contains(e: T): boolean;
+    abstract smallest(compareFn: (x: T, y: T) => -1 | 0 | 1): T;
+
+    static of<T>(...args: Array<T>): List<T> {
+        let list: List<T> = this.empty();
+
+        for (let i = args.length - 1; i >= 0; i--) {
+            list = list.prepend(args[i]);
+        }
+
+        return list;
+    }
+
+    static empty() {
+        return Nil.getInstance();
+    }
+}
+
+class Nil<T> extends List<T> {
+    private constructor() {
+        super();
+    }
+
+    private static instance: Nil<unknown>;
+
+    static getInstance(): Nil<any> {
+        if (this.instance) return this.instance;
+
+        this.instance = new Nil<unknown>();
+        return this.instance;
+    }
+
+    head(): T {
+        throw new Error("Illegal operation taking head of an empty list");
+    }
+
+    tail(): List<T> {
+        return List.empty();
+    }
+
+    prepend<T>(el: T): List<T> {
+        return new Cons<T>(el, NIL);
+    }
+
+    map<B>(): Nil<B> {
+        return NIL;
+    }
+
+    flatMap<B>(): List<B> {
+        return NIL;
+    }
+
+    filter(): List<T> {
+        return NIL;
+    }
+
+    foldLeft<B>(fn: (e: T, z: B) => B, z: B): B {
+        return z;
+    }
+
+    foldRight<B>(fn: (e: T, z: B) => B, z: B): B {
+        return z;
+    }
+
+    merge(other: List<T>): List<T> {
+        return other;
+    }
+
+    count(): number {
+        return 0;
+    }
+
+    reduce(fn: (x: T, y: T) => T, z: T): T {
+        return z;
+    }
+
+    reverse(): List<T> {
+        return NIL;
+    }
+
+    sort(): List<T> {
+        return NIL;
+    }
+
+    contains(): boolean {
+        return false;
+    }
+
+    smallest(): T {
+        throw new Error("Invalid operation on empty list");
+    }
+}
+
+const NIL = List.empty();
+
+class Cons<T> extends List<T> {
+    constructor(private readonly _head: T, private readonly _tail: List<T>) {
+        super();
+    }
+
+    head(): T {
+        return this._head;
+    }
+
+    tail(): List<T> {
+        return this._tail;
+    }
+
+    prepend(el: T): Cons<T> {
+        return new Cons(el, this);
+    }
+
+    map<B>(fn: (e: T) => B): List<B> {
+        return new Cons(fn(this._head), this._tail.map(fn));
+    }
+
+    flatMap<B>(fn: (e: T) => List<B>): List<B> {
+        return this.map(fn).reduce((x, z) => z.merge(x), NIL);
+    }
+
+    filter(fn: (e: T) => boolean): List<T> {
+        return fn(this._head)
+            ? new Cons(this._head, this._tail.filter(fn))
+            : this._tail.filter(fn);
+    }
+
+    foldLeft<B>(fn: (e: T, z: B) => B, z: B): B {
+        return fn(this._head, this._tail.foldLeft(fn, z));
+    }
+
+    foldRight<B>(fn: (e: T, z: B) => B, z: B): B {
+        return this._tail.foldRight(fn, fn(this._head, z));
+    }
+
+    merge(other: List<T>): List<T> {
+        return new Cons<T>(this._head, this._tail.merge(other));
+    }
+
+    count(): number {
+        return this.foldRight((x, y) => y + 1, 0);
+    }
+
+    reduce(fn: (x: T, y: T) => T, z: T): T {
+        return this._tail.foldLeft(fn, fn(this._head, z));
+    }
+
+    reverse(): List<T> {
+        return this.foldRight((x: T, y: List<T>) => y.prepend(x), NIL);
+    }
+
+    contains(e: T): boolean {
+        return this._head === e || this._tail.contains(e);
+    }
+
+    smallest(compareFn: (x: T, y: T) => -1 | 0 | 1): T {
+        if (this._tail === NIL) return this._head;
+        const other = this._tail.smallest(compareFn);
+        const result = compareFn(this._head, other);
+        return result === 1 ? other : this._head;
+    }
+}
+
+const l1 = List.of<number>(1, 2, 3, 4);
+
+const m1 = List.of<number>(100, 200);
+
+const printFn = (x: any) => process.stdout.write(x + " ");
+
+console.log("\nPrint elements using map");
+l1.map(identity).map(printFn);
+
+console.log("\nPrint squares of elements using map");
+l1.map((x) => x * x).map(printFn);
+
+console.log("\nFilter even numbers");
+l1.filter((x) => x % 2 === 0).map(printFn);
+
+console.log("\nSum using foldRight is: " + l1.foldRight((x, y) => x + y, 0));
+
+console.log("\nCount : " + l1.count());
+
+console.log("\nSum using reduce is: " + l1.reduce((x, y) => x + y, 0));
+
+console.log("\nMerge two lists");
+l1.merge(m1).map(printFn);
+
+console.log("\nFlat map list");
+const n3 = List.of(l1, m1);
+console.log("\nMerging l1 and m1");
+l1.merge(m1).map(printFn);
+console.log("");
+n3.head().map(printFn);
+console.log("\ntail");
+n3.tail().map((x) => x.map(printFn));
+console.log("\nAfter flatmap");
+n3.flatMap(identity).map(printFn);
+console.log("\nPair map");
+l1.flatMap((x) => List.of(x * 2, x * x)).map(printFn);
+console.log("\nReverse");
+l1.reverse().map(printFn);
+console.log("\nReverse2");
+const r1 = List.of<number>(4, 5, 6, 7);
+r1.reverse().map(printFn);
+console.log("Contains");
+console.log(r1.contains(6));
+console.log(r1.contains(16));
+console.log("Smallest");
+console.log(r1.smallest((x, y) => (x < y ? -1 : 1)));