Proposed implementation of GADTs with Javascript and Flow

adt.js

/*
 * `match` is a helper function for writing pattern matches on types that are
 * implemented using Scott encoding.
 *
 * @flow
 */

export function match<A,B>(matcher: A): (match: (matcher: A) => B) => B {
  return match => match(matcher)
}

expr.js

/*
 * This example demonstrates how to use Scott encoding to express an algebraic
 * data type (ADT) in Flow. Under Scott encoding values are functions that are
 * applied to access the data inside. That means that we get pattern matching
 * for free, and the compiler will make sure that pattern matching is
 * exhaustive.
 *
 * Scott encoding can be used to write generalized algebraic data types in
 * Flow (GADTs) - but as of Flow v0.53.1 there are some limitations on
 * typechecking functions that operate on GADTs.
 *
 * @flow
 */

import { match } from './adt'

/*
 * The type `Expr<A>` represents an abstract syntax tree for arithmatic and
 * boolean expressions. Constructors for this type specify their return type,
 * which means that we can track the type of the value that an expression will
 * evaluate to at each point in the AST by specifying concrete types for
 * a phantom type variable (the A in Expr<A>).
 */
export type Expr<A> = <R>(matcher: ExprMatcher<A,R>) => R

type ExprMatcher<A,R> = {
  I:   (i: number)                        => R,
  B:   (b: boolean)                       => R,
  Add: (x: Expr<number>, y: Expr<number>) => R,
  Mul: (x: Expr<number>, y: Expr<number>) => R,
  Eq:  (x: Expr<number>, y: Expr<number>) => R,
}

/*
 * These are constructors for the `Expr<A>` type. Note the concrete type
 * parameters in the input and return types of each constructor. The fact that
 * different constructors return different types (i.e., constructor return
 * types vary in the choice of the type of `A`) means that `Expr<A>` is
 * a *generalized* algebraic data type (GADT).
 */

export function I(i: number): Expr<number> {
  return <R>(matcher: ExprMatcher<number,R>): R => matcher.I(i)
}

export function B(b: boolean): Expr<boolean> {
  return <R>(matcher: ExprMatcher<boolean,R>): R => matcher.B(b)
}

export function Add(x: Expr<number>, y: Expr<number>): Expr<number> {
  return <R>(matcher: ExprMatcher<number,R>): R => matcher.Add(x, y)
}

export function Mul(x: Expr<number>, y: Expr<number>): Expr<number> {
  return <R>(matcher: ExprMatcher<number,R>): R => matcher.Mul(x, y)
}

export function Eq(x: Expr<number>, y: Expr<number>): Expr<boolean> {
  return <R>(matcher: ExprMatcher<boolean,R>): R => matcher.Mul(x, y)
}

/*
 * An expression is resolved to a value using the `evaluate` function.
 * Unfortunately `evaluate` does not typecheck as of Flow v0.53.1
 *
 * $FlowFixMe
 */
const evaluate: <A>(_: Expr<A>) => A = match({
  I:   i      => i,
  B:   b      => b,
  Add: (x, y) => evaluate(x) + evaluate(y),
  Mul: (x, y) => evaluate(x) * evaluate(y),
  Eq:  (x, y) => evaluate(x) == evaluate(y),
})

/*
 * This example represents the expression (2 + 1) * 4
 */
const expr = Mul(
  Add(I(2), I(1)),
  I(4)
)

/*
 * The expression evaluates to the numeric value `12`
 */
console.log(evaluate(expr))

/*
 * Although `evaluate` cannot currently be typechecked, Flow does note the type
 * signature that is given. So Flow will correctly typecheck expressions that
 * use `evaluate`
 */

const a: number = evaluate(expr)
const b: boolean = evaluate(Eq(I(1), I(1)))

/*
 * Does not typecheck because `expr` evaluates to a `number` not a `boolean`
 * $FlowFixMe
 */
const c: boolean = evaluate(expr)