Simple single linked list in TypeScript.

lists.ts

export type List<T> = { value: T; next: List<T> } | null;

export const map = <T, U>(list: List<T>, fn: (value: T) => U): List<U> => {
  if (list === null) return null;
  return {
    value: fn(list.value),
    next: map(list.next, fn),
  };
};

export const concat = <T>(list1: List<T>, list2: List<T>): List<T> => {
  if (list1 === null) return list2;
  return cons(list1.value, concat(list1.next, list2));
};

export const flatMap = <T, U>(
  list: List<T>,
  fn: (value: T) => List<U>
): List<U> => {
  if (list === null) return null;
  return concat(fn(list.value), flatMap(list.next, fn));
};

export const foldLeft = <T, U>(
  list: List<T>,
  fn: (acc: U, value: T) => U,
  acc: U
): U => {
  if (list === null) return acc;
  return foldLeft(list.next, fn, fn(acc, list.value));
};

export const head = <T>(list: List<T>): T | null => {
  if (list === null) return null;
  return list.value;
};

export const tail = <T>(list: List<T>): List<T> | null => {
  if (list === null) return null;
  return list.next;
};

export const cons = <T>(value: T, list: List<T>): List<T> => {
  return { value, next: list };
};

export const fromArray = <T>(array: T[]): List<T> => {
  return array.reduceRight((acc, value) => cons(value, acc), null as List<T>);
};

export const listOf = <T>(...values: T[]): List<T> => {
  return fromArray(values);
};

export const toArray = <T>(list: List<T>): T[] => {
  return foldLeft(list, (acc, value) => [...acc, value], [] as T[]);
};

export const product = <T>(lists: List<List<T>>): List<List<T>> => {
  if (lists === null) return null;
  const headList = head(lists);
  const tailLists = tail(lists);
  if (headList === null) return null;
  if (tailLists === null) return map(headList, (value) => cons(value, null));
  const tailCombinations = product(tailLists);
  return flatMap(headList, (value) =>
    map(tailCombinations, (list) => cons(value, list))
  );
};

export const reverse = <T>(list: List<T>): List<T> => {
  return foldLeft(list, (acc, value) => cons(value, acc), null as List<T>);
};