Repository navigation
(suggestion) tagged union types #10253
Description
Activity
This is a nice suggestion but needs a lot more explanation as to what exactly's being proposed before we can look at it.
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
caseSplitmethod 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.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 discriminatorsHmm, 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)?Yes, you can. I've rewritten
evaluateTermWithContextusing only expressions (moduloconst 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.evaluateTermWithContext2is 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.
If by "expression level" you meant the object literal, then there are two separate problems to tackle
- Say that the keys of the object are the "enum kinds", for which there is an issue: String literal types as index signature parameter types? #5683
- Say that the value is a function accepting the narrowed option - Proposal: Get the type of any expression with typeof #6606
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.
This is all pretty much doable today with existing syntax.
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: