Evaluate expressions with F-algebras in TypeScript

expralgebra.ts

// inspiration:
// https://www.schoolofhaskell.com/user/bartosz/understanding-algebras
/**
 * Higher-kinded Types.
 * A higher-kinded type is a type that abstracts over some type that, in turn,
 * abstracts over another type.
 *
 * To support them in TypeScript we have to write a few types first.
 */
declare const Type: unique symbol;
declare const Variable: unique symbol;
declare const Indirect: unique symbol;

/**
 * A mechanism for delaying the instantiation of a generic type. See `$` next.
 */
interface HKT {
  [Type]?: unknown;
  [Variable]?: unknown;
}

/**
 * Intuition: `$<FHKT, T>` eventually will evaluate to `F<T>` for some generic
 * type `F` and its friend `FHKT`.
 */
type $<T extends HKT, A> = T extends { [Type]: unknown }
  ? (T & {
    [Variable]: A;
  })[typeof Type]
  : {
    [Indirect]: T; // forces tsc to retain reference to T
    [Variable]: A;
  };

/**
 * A "Functor" is a type which supports a "map" operation.
 * Array<T> is a functor: you can map a function `isEven(n: number): boolean`
 * over an `Array<number>` to produce an `Array<boolean>`.
 */
interface Functor<T extends HKT> {
  map<B>(
    this: $<T, T[typeof Variable]>,
    f: (a: T[typeof Variable]) => B
  ): $<T, B>;
}

/**
 * Defines a fixed point for a higher-kinded type.
 * Unfortunately this is more complicated than it should be to evade
 * TypeScript's circularity checks.
 */
type Fix<F extends HKT> = {
  fixed: $<F, Fix<F>>;
};

function fix<F extends HKT>(fixed: $<F, Fix<F>>): Fix<F> {
  return { fixed };
}

function unfix<F extends HKT>(fixed: Fix<F>): $<F, Fix<F>> {
  return fixed.fixed;
}

/**
 * An F-algebra is
 * - a Functor, F (with an HKT representation FHKT);
 * - a carrier type A; and
 * - a function `(fa: $<FHKT, A>) => A`.
 */
interface Algebra<F extends HKT, A> {
  (fa: $<F, A>): A;
}

/**
 * A simple arithmetic expression language supporting number constants,
 * addition, and multiplication.
 *
 * Instead of directly referencing itself to represent nested expressions, the
 * type of nested expressions is turned into a type variable and `ExprF` is a
 * functor wrt that type variable.
 */
abstract class ExprF<A> implements Functor<ExprFHKT> {
  abstract map<B>(f: (a: A) => B): ExprF<B>;
}

interface ExprFHKT extends HKT {
  [Type]: ExprF<this[typeof Variable]>;
}

type Expr = Fix<ExprFHKT>;

/**
 * Expression type 1: Number constants.
 */
class Constant<A> extends ExprF<A> {
  constructor(public readonly value: number) {
    super();
  }

  // eslint-disable-next-line @typescript-eslint/no-unused-vars
  map<B>(_f: (a: A) => B): ExprF<B> {
    return new Constant(this.value);
  }
}

// Constructor that hides some unfortunate boilerplate I will hopefully
// eliminate in a future version.
function mkConstant(value: number): Expr {
  return fix<ExprFHKT>(new Constant(value));
}

/**
 * Expression type 2: Addition.
 */
class Add<A> extends ExprF<A> {
  constructor(public readonly lhs: A, public readonly rhs: A) {
    super();
  }

  map<B>(f: (a: A) => B): ExprF<B> {
    return new Add(f(this.lhs), f(this.rhs));
  }
}

function mkAdd(lhs: Expr, rhs: Expr): Expr {
  return fix<ExprFHKT>(new Add(lhs, rhs));
}

/**
 * Expression type 3: Multiplication.
 */
class Mul<A> extends ExprF<A> {
  constructor(public readonly lhs: A, public readonly rhs: A) {
    super();
  }

  map<B>(f: (a: A) => B): ExprF<B> {
    return new Mul(f(this.lhs), f(this.rhs));
  }
}

function mkMul(lhs: Expr, rhs: Expr): Expr {
  return fix<ExprFHKT>(new Mul(lhs, rhs));
}

/**
 * An F-algebra which evaluates an `ExprF<number>` to `number`.
 * Note I wrote `ExprF`, not `Expr`.
 * Also note how simple this function is.
 */
type ExprAlgebra = Algebra<ExprFHKT, number>;
const exprAlgebra: ExprAlgebra = (expr) => {
  if (expr instanceof Constant) {
    return expr.value;
  }
  else if (expr instanceof Add) {
    return expr.lhs + expr.rhs;
  }
  else if (expr instanceof Mul) {
    return expr.lhs * expr.rhs;
  }
};

/**
 * The main event.
 * We have defined an expression grammar as a non-recursive functor type and an
 * F-algebra defining how to evaluate the base case of each expression.
 * With one line we can define an evaluator for any arbitrary `Expr`.
 */
function evaluate(expr: Expr): number {
  return exprAlgebra(unfix<ExprFHKT>(expr).map(evaluate));
}

/**
 * Demonstration: evaluation of a non-trivial nested arithmetic expression.
 */
const t1: Expr = mkAdd(
  mkMul(mkConstant(5), mkAdd(mkConstant(-1), mkConstant(2))),
  mkMul(mkConstant(2), mkConstant(7))
);

console.log(evaluate(t1)); // prints "19"