Skip to content

(suggestion) tagged union types #10253

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
negatratoron opened this issue Aug 10, 2016 · 7 comments
Closed

(suggestion) tagged union types #10253

negatratoron opened this issue Aug 10, 2016 · 7 comments
Labels
Needs Proposal This issue needs a plan that clarifies the finer details of how it could be implemented. Suggestion An idea for TypeScript

Comments

@negatratoron
Copy link

Javascript objects generally represent tagged intersection types, for example {a : Number, b : Number }, the intersection of two numbers.

Tagged union types can also be represented using Javascript objects. An instance of a tagged union type has one property, of the specified type. Values of a tagged union type can only be used in a program through case splitting. Here's a quick code example:

var toString : (x : oneOf({
  a : Number,
  b : Number,
})) => String = caseSplit({
  a: function (x) {
    return "a: " + x;
  },
  b: function (x) {
    return "b: " + x;
  },
});

var a = toString({
  a: 3
}); // "a: 3"

var b = toString({
  b: 4
}); // "b: 4"

var c = toString({
  c: 5
}); // error
@RyanCavanaugh RyanCavanaugh added Suggestion An idea for TypeScript Needs Proposal This issue needs a plan that clarifies the finer details of how it could be implemented. labels Aug 10, 2016
@RyanCavanaugh
Copy link
Member

This is a nice suggestion but needs a lot more explanation as to what exactly's being proposed before we can look at it.

@negatratoron
Copy link
Author

negatratoron commented Aug 10, 2016

Well, they are also called algebraic data types. Using a combination of tagged OR types (union types) and tagged AND types (objects), you could implement a lambda calculus like this (not tested):

type Term = oneOf({
  var: String,
  lambda: {
    var: String,
    expr: Term,
  },
  app: {
    func: Term,
    val: Term,
  },
});

var evaluateTermWithContext : (context : Object) => (term : Term) => Term = function (context) {
  return caseSplit({
    var: function (name) {
      return context[name];
    },
    lambda: function (obj) {
      return obj;
    },
    app: function (obj) {
      context = Object.clone(context); // clone the context
      context[obj.func.var] = obj.val;
      return evalTermWithContext(context)(obj.func.expr);
    },
  });
};

var evaluateTerm : (term : Term) => Term = evaluateTermWithContext({});

The caseSplit method would have to be built in. It would take an object with a function for each alternative of the union type, then a value of the union type, and apply the correct function.

@gcnew
Copy link
Contributor

gcnew commented Aug 11, 2016

@jeffersoncarpenter Have you taken a look at What's new in TypeScript - Tagged union types? They are very cool :)

PS: with #9407 (already merged in master and available in typescript@next) you can even use booleans and numbers as discriminators

@negatratoron
Copy link
Author

Hmm, is it possible to narrow those types at the expression level rather than at the statement level (i.e. with a construct that's like my caseSplit)?

@gcnew
Copy link
Contributor

gcnew commented Aug 12, 2016

Yes, you can. I've rewritten evaluateTermWithContext using only expressions (modulo const term = _term, it's needed because types are reset in closures; it's only helping the compiler determine no mutations are made and my be fixed in later versions). This is a very non-idiomatic way though, TS syntax is not what you may expect from an ML language. evaluateTermWithContext2 is a much nicer way to write it, still keeping functional flavour (and very close to what you would write with guards and do notation).

type Var    = { kind: 'var',    name: string }
type Lambda = { kind: 'lambda', var:  string, expr: Term }
type App    = { kind: 'app',    func: Term,   val: Term  }
type Term = Var | Lambda | App

function never(x: never): never {
    throw new Error(`Not a never ${x}`);
}

function fail(reason?: string): never {
    throw new Error(reason);
}

// Only expressions
let evaluateTermWithContext: (context: Object) => (term: Term) => Term =
    context => _term => {
        const term = _term;
        return term.kind === 'var'    ? context[term.name]
             : term.kind === 'lambda' ? term
             : term.kind === 'app'    ?
                  ((func: Term) => func.kind !== 'lambda'
                        ? fail('lambda expected')
                        : evaluateTermWithContext(
                            Object.assign({}, context, { [func.var]: term.val })
                          )(func.expr)
                  )(evaluateTermWithContext(context)(term))
             : never(term);
    }

// More idiomatic and much more readable
function evaluateTermWithContext2(context: Object): (term: Term) => Term {
    return term => {
        switch (term.kind) {
            case 'var':    return context[term.name];
            case 'lambda': return term;
            case 'app': {
                const func = evaluateTermWithContext2(context)(term);

                if (func.kind !== 'lambda') {
                    throw new Error('lambda expected');
                }

                const newContext = Object.assign({}, context, {
                    [func.var]: term.val
                });

                return evaluateTermWithContext(newContext)(func.expr);
            }
        }
    };
}

var evaluateTerm : (term : Term) => Term = evaluateTermWithContext({});

One interesting thing to note is that TypeScripts Discriminated unions are much more powerful than e.g. Haskell's ADTs - they can be discriminated on arbitrary fields, not only "constructor", can be freely extended through intersection types/other unions, or have their options reduced by checking for specific ones and factoring them out. As a nice bonus "constructors" (they really are a shape, not a function) are first class types, which is huge - you can make your functions accept or return just a specific option and it all works.

@gcnew
Copy link
Contributor

gcnew commented Aug 12, 2016

If by "expression level" you meant the object literal, then there are two separate problems to tackle

It's hard to imagine the need for typing such an object literal though (except for faking ADT functionality, which is already built-in with a better machinery). On the other hand, having the upper two issues implemented will bring a lot of flexibility to what can be expressed.

@RyanCavanaugh
Copy link
Member

This is all pretty much doable today with existing syntax.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Needs Proposal This issue needs a plan that clarifies the finer details of how it could be implemented. Suggestion An idea for TypeScript
Projects
None yet
Development

No branches or pull requests

3 participants