GADTs.ts

// Porting of the "Arithmetic expressions" example at https://en.wikibooks.org/wiki/Haskell/GADT

// (partially) related TS discussions:
// - https://github.com/microsoft/TypeScript/issues/12424
// - https://github.com/microsoft/TypeScript/issues/17325

// Definition of `Expr` in Haskell using GADTs
// data Expr a where
//     I   :: Int  -> Expr Int
//     B   :: Bool -> Expr Bool
//     Add :: Expr Int -> Expr Int -> Expr Int
//     Mul :: Expr Int -> Expr Int -> Expr Int
//     Eq  :: Eq a => Expr a -> Expr a -> Expr Bool

// Porting to TS with a few standard techniques:
// - private type def of a "discriminated union" (tagged union type)
// - public constructors for each case
// - phantom fields to carry additional type-level information around

// Expr type def, private / not to be esported:
// e.g. if using these directly, no guarantees on the type of `I { value }`,
// or on the fact that `Eq` is holding (comparing) two expressions of the same `A`.
// `value` is an actual field for primitive values (`I` and `B`), a phantom field for operations.
type Expr<A> =
  | { type: "I"; value: A }
  | { type: "B"; value: A }
  | { type: "Add"; lhs: Expr<number>; rhs: Expr<number>; value: A }
  | { type: "Mul"; lhs: Expr<number>; rhs: Expr<number>; value: A }
  | { type: "Eq"; lhs: Expr<unknown>; rhs: Expr<unknown>; value: A };

// "smart" type constructors
// some of them use the following helper to
// add a phantom field to our return types (just `id` at runtime)
const phantom = <T, A>(v: T): T & { value: A } => v as any;

const I = (value: number): Expr<number> => ({
  type: "I",
  value
});
const B = (value: boolean): Expr<boolean> => ({
  type: "B",
  value
});
const Add = (lhs: Expr<number>, rhs: Expr<number>): Expr<number> =>
  phantom({
    type: "Add",
    lhs,
    rhs
  });
const Mul = (lhs: Expr<number>, rhs: Expr<number>): Expr<number> =>
  phantom({
    type: "Mul",
    lhs,
    rhs
  });
const Eq = <A>(lhs: Expr<A>, rhs: Expr<A>): Expr<boolean> =>
  phantom({
    type: "Eq",
    lhs,
    rhs
  });

// example usage, works
const a = Eq(B(false), I(1)); // $ExpectError
const b: Expr<number> = Mul(I(21), I(2));
const c: Expr<boolean> = Eq(Eq(Add(Mul(I(1), I(2)), I(3)), I(5)), B(true));

// Definition of the eval function in Haskell
// eval :: Expr a -> a
// eval (I n) = n
// eval (B b) = b
// eval (Add e1 e2) = eval e1 + eval e2
// eval (Mul e1 e2) = eval e1 * eval e2
// eval (Eq  e1 e2) = eval e1 == eval e2

// Porting eval to TS
// `declare` is easy:
declare function _eval<T>(expr: Expr<T>): T;
// And usage as expected
const eb: number = _eval(b);
const ec: boolean = _eval(c);

// actual implementation... not so much
function __eval<T>(expr: Expr<T>): T {
  switch (expr.type) {
    case "I":
      return expr.value;
    case "B":
      return expr.value;
    case "Add":
      return __eval(expr.lhs) + __eval(expr.rhs); // Type 'number' is not assignable to type 'T'
    case "Mul":
      return __eval(expr.lhs) * __eval(expr.rhs); // Type 'number' is not assignable to type 'T'
    case "Eq":
      return __eval(expr.lhs) === __eval(expr.rhs); // Type 'boolean' is not assignable to type 'T'
  }
}
// similar results also using the signature:
// `function __eval<E extends Expr<unknown>>(expr: E): E extends Expr<infer T> ? T : never`