LinkedList.ts

namespace List {
  const EmptyList = new TypeError('The list is empty');
  const IndexOutOfBounds = new RangeError('Index out of bounds');

  type Empty = '@@EMPTY';
  export const EMPTY: Empty = '@@EMPTY';

  export type IList<T> = Empty | readonly [T, IList<T>];

  export const head = <T>(list: IList<T>): T => {
    if (list === EMPTY) throw EmptyList;
    const [head, tail] = list;
    return head;
  }

  export const tail = <T>(list: IList<T>): IList<T> => {
    if (list === EMPTY) throw EmptyList;
    const [head, tail] = list;
    return tail;
  }

  export const get = <T>(list: IList<T>, idx: number): T => {
    if (list === EMPTY) {
      throw IndexOutOfBounds;
    }
    const [head, tail] = list;
    if (idx === 0) return head;
    return get(tail, idx - 1);
  }

  export const set = <T>(list: IList<T>, idx: number, item: T,): IList<T> => {
    if (list === EMPTY) {
      throw IndexOutOfBounds;
    }
    const [head, tail] = list;
    if (idx === 0) return [item, tail];
    return [head, set(tail, idx - 1, item)];
  }

  export const _delete = <T>(list: IList<T>, idx: number): IList<T> => {
    if (list === EMPTY) {
      throw IndexOutOfBounds;
    }
    const [head, tail] = list;
    if (idx === 0) return tail;
    return [head, _delete(tail, idx - 1)];
  }

  export const concat = <T>(list1: IList<T>, list2: IList<T>): IList<T> => {
    if (list1 === EMPTY) return list2;
    const [head, tail] = list1;
    return [head, concat(tail, list2)];
  }
  
  export const append = <T>(list: IList<T>, el: T): IList<T> => {
    if (list === EMPTY) return [el, EMPTY];
    const [head, tail] = list;
    return [head, append(tail, el)];
  }
  
  export const prepend = <T>(list: IList<T>, el: T): IList<T> =>
    [el, list]
  
  export const len = <T>(list: IList<T>): number => {
    if (list === EMPTY) return 0;
    const [head, tail] = list;
    return 1 + len(tail);
  }
  
  export const map = <T, R>(list: IList<T>, mapper: (item: T) => R): IList<R> => {
    if (list === EMPTY) return EMPTY;
    const [head, tail] = list;
    return [mapper(head), map(tail, mapper)];
  }

  export const forEach = <T>(list: IList<T>, f: (item: T) => void): void => {
    if (list === EMPTY) return;
    const [head, tail] = list;
    f(head);
    return forEach(tail, f);
  }
  
  export const filter = <T>(list: IList<T>, f: (item: T) => boolean): IList<T> => {
    if (list === EMPTY) return EMPTY
    const [head, tail] = list;
    if (f(head)) return [head, filter(tail, f)];
    return filter(tail, f);
  }
  
  export const reduce = <T, R>(list: IList<T>, reducer: (item: T, acc: R) => R, val: R): R => {
    if (list === EMPTY) return val;
    const [head, tail] = list;
    return reduce(tail, reducer, reducer(head, val));
  }
  
  export const toArray = <T>(list: IList<T>): T[] => {
    if (list === EMPTY) return [];
    const [head, tail] = list;
    return [head, ...toArray(tail)];
  }
  
  export const fromArray = <T>(arr: T[]): IList<T> => {
    if (arr.length === 0) return EMPTY;
    const [head, ...tail] = arr;
    return [head, fromArray(tail)];
  }
  
  export const reverse = <T>(list: IList<T>): IList<T> => {
    if (list === EMPTY) return EMPTY;
    const [head, tail] = list;
    return append(reverse(tail), head);
  }

  export const print = <T>(list: IList<T>): void => {
    if (list === EMPTY) {
      console.log('List []')
    } else {
      console.log(`List [ ${List.toArray(list).join(', ')} ]`);
    }
  }
}

class LinkedList<T> {
  private readonly list: List.IList<T>;

  static fromArray = <T>(arr: T[]) => new LinkedList(List.fromArray(arr));
  static fromElements = <T>(...args: T[]) => new LinkedList(List.fromArray(args));

  constructor(_list: List.IList<T> = List.EMPTY) {
    this.list = _list;
  }

  // Calculatable values

  head = () => List.head(this.list);
  length = () => List.len(this.list);
  get = (idx: number) => List.get(this.list, idx);
  reduce = <R>(reducer: (item: T, acc: R) => R, val: R) => List.reduce(this.list, reducer, val);
  toArray = () => List.toArray(this.list);

  // Side effect methods

  forEach = (f: (item: T) => void) => List.forEach(this.list, f);
  print = () => List.print(this.list);
  
  // Methods which generate new LinkedLists
  
  tail = () => new LinkedList(List.tail(this.list));
  set = (idx: number, item: T) => new LinkedList(List.set(this.list, idx, item));
  delete = (idx: number) => new LinkedList(List._delete(this.list, idx));
  append = (el: T): LinkedList<T> => new LinkedList(List.append(this.list, el));
  prepend = (el: T): LinkedList<T> => new LinkedList(List.prepend(this.list, el));
  concat = (list2: LinkedList<T>) => new LinkedList(List.concat(this.list, list2.list));
  map = <R>(mapper: (item: T) => R) => new LinkedList(List.map(this.list, mapper));
  filter = (f: (item: T) => boolean) => new LinkedList(List.filter(this.list, f));
  reverse = () => new LinkedList(List.reverse(this.list));
  clear = () => new LinkedList();
}