Typescript discriminated unions example (ropes)

rope.ts

// A non-empty rope is either a leaf (string) or a node with two children
// that are both non-empty ropes

interface Tagged<T> {
  tag: T;
}
type RopeNode =
  | Tagged<"node"> & {
      left: RopeNode;
      right: RopeNode;
    }
  | Tagged<"leaf"> & {
      data: string;
    };

// An empty string is represented by the rope null
type Rope = RopeNode | null;

function concat(r1: Rope, r2: Rope): Rope {
  if (r1 === null) return r2;
  if (r2 === null) return r1;
  return { tag: "node", left: r1, right: r2 };
}

function impossible(x: never): never {
  throw new Error("Unexpected object: " + x);
}

function max(x: number, y: number): number {
  if (x > y) return x;
  else return y;
}

function height(r: Rope): number {
  if (r === null) return 0;
  switch (r.tag) {
    case "leaf":
      return 1;
    case "node":
      return 1 + max(height(r.left), height(r.right));
    default:
      return impossible(r);
  }
}

function ropeToString(r: Rope): string {
  if (r === null) return "";
  switch (r.tag) {
    case "leaf":
      return r.data;
    case "node":
      return ropeToString(r.left) + ropeToString(r.right);
    default:
      return impossible(r);
  }
}

function leaf(s: string): RopeNode {
  return { tag: "leaf", data: s };
}

function node(r1: RopeNode, r2: RopeNode): RopeNode {
  return { tag: "node", left: r1, right: r2 };
}

let r = node(node(leaf("a"), node(leaf("b"), leaf("c"))), leaf("d"));

console.log(height(r));
console.log(height(concat(r, concat(r, r))));
console.log(ropeToString(r));
console.log(ropeToString(concat(r, concat(r, r))));