fleshing out type operators (discussion)

This is a discussion thread where I'd like to give a high-level overview of the type-level operations (as opposed to expression-level) that we can and can not yet do today.

This differs from the TS roadmap by identifying holes, while complementing the issues list by trying to show some of the bigger picture, the goal being to see what issues tie into which points, and how we could address them.

I'd like stimulate discussion on how we could fill the holes here; for all I know there are holes we can find solutions to with no changes to TS!

Below is my list of imaginable basic type operations. The reason I focus on these is that, with basic operators down, most more complicated use-cases could be addressed simply by combining these. Names are based on my implementations here.

Additions / corrections / related issues / comments welcome!

Operations:

Built-in operators:

union |: allow either of two types. also helps get the more lenient of two types, i.e. T | never -> T. you'll encounter this in type inference since optional params yield | undefined types. no known warts.
intersection &: get the stricter of two types, i.e. T & never -> never. shouldn't need this very often. also helps combine two objects. warts:
- overlapping keys when combining objects will & their contents too (alt: Overwrite / MergeAll)
keyof: create a union of string literals from a type's keys. warts:
- returning a string union means number literal keys get converted to string literals
- returning a string union means symbol keys get ignored
- when a string index is present, there is no known way to get the individual string keys
- somehow also gives prototype keys for array types, yet not for object types
in: construct an object type based on a union of strings (keys) and corresponding calculated values based on these. warts:
- since this is based on strings, anything else, such as numbers, symbols, or indices, needs to be specified separately (-> &).
member access: get the type at a certain index of an object/tuple type (considering intersections as a single object, getting multiple result for union'd objects). warts:
- there is ambiguity w.r.t. whether the prototype or the index should trump. it currently lets the prototype trump, even if you wanted it not to, meaning you're likely to get unexpected behavior for member access operations for e.g. toString.
- does implicit conversion between numeric literals and string literals, not unlike JS. not a problem though. :)

& is a bit less straight-forward from the rest in its use-cases:

a way to make impossible types like string & number (uses?)
a redundant way to write never (T & never), which gets more useful given conditionals, but then you could just use those to conditionally produce never right away
a poor man's Overwrite / MergeAll (inferior in its behavior intersecting types in overlapping keys, which poorly reflects actual JS). if you know keys won't overlap though, it's great since it's short, built-in and performant.
'get the most specific type of these two': haven't found use-cases for this, but could also be done given Matches
add a symbol to an existing object
have an index type with keys not bound to sub-classing it

Boolean operations:

Not, And, Or, Eq, Neq

Note: these can currently be implemented through string literal representations. It would be possible to convert these to boolean literals (StringToBool), but cannot yet map boolean literals to these (BoolToString) or other values for that matter.

Array (tuple) operations

Unary:

TupleLength: check the length of a given tuple type.
ArrayProp: get the element type for a homogeneous array type (similar for extracting generics from other parameterized types)

Binary:

~~[x] TupleProp: get the type at a certain index for a tuple/array type. just T[I].~~
TupleHasIndex: check whether a tuple type contains a given index.
TupleHasElem: check whether a tuple type contains a given type among its elements. This could be done given TypesEq.
concatenate / append / prepend. possible today using numeric objects (compatible with ArrayLike), but could become possible for tuple types natively with the variadic kinds proposal at Proposal: Variadic Kinds -- Give specific types to variadic functions #5453. ~~There has been talk there this would also depend on Proposal: strict and open-length tuple types #6229.~~
destructuring tuples: see above
difference: remove indices in one tuple type from another tuple type. see above.
Vector: create a tuple type for a given element type plus size.

Advanced:

array iteration, used for e.g. TupleLength
reduce: the function needs ReturnType for its dynamic reducer functions; otherwise doable using iteration. see Proposal: add a built-in reduce function on the type level #12512.
map over tuples: doable now through numerical objects for fixed conditions; also needs ReturnType in case the mapping function is given as a function (e.g. map itself).

object operations

Unary:

ObjectLength: check the length (number of keys) of a given heterogeneous object type. doable given UnionLength or (object iteration + Inc).

Binary:

Advanced:

map over heterogeneous objects: probably just needs ReturnType.
object iteration: useful for e.g. ObjectToArray. This could enable union iteration, or the other way around.
- One strategy that comes to mind relies on converting keys to tuple (given UnionToArray) then using array iteration.
- Alternatively, break string literals into characters, convert to numbers, convert objects to a nested version with one key at each stage using key sort, which could then be traversed in order... Nope, no member access on string literals.

Type operations

Type checks (binary):

Matches: check whether a given type matches another type (inclusive, e.g. true for string and string). This could be done given ReturnType.
TypesEq: check whether two types are 'equal', that is, A satisfies B and vice versa. This could be done given Matches.
InstanceOf: check whether a given type represents a subset of another type (-> exclusive match). This could be done given Matches.
PrototypeOf: get the prototype (-> methods) of a type. Partial helps, though Symbol-based keys get killed.

Type casts (unary):

Union operations

Unary:

a way to access union elements, e.g. going from "a" | "b" | "c" to "a". this could enable union iteration using Diff if they're all string literals, which in turn could enable object iteration. or the other way around.
IsUnionType -- solvable today only for unions consisting of known sets of keys, see my Indeterminate; a proper solution could be made using union iteration or a way to access arbitrary / random elements (e.g. with conversion to tuple type)
UnionLength: check the length of a union, i.e. how many options it is composed of.

Binary:

union: A | B
UnionHasKey: check whether a union of string literals contains a given key.
UnionHasType: general case, check whether a union of arbitrary types contains a given type.
- could be achieved using TypesEq. plugging a union into it should return e.g. "0" | "1" in case it contains a match -- at that point UnionHasKey works.
IntersectionUnions: get the intersection of two union types, possible today given unions of string literals.
DifferenceUnions: subtract any keys from one union from those contained in another union.
UnionContained: verify whether one union is fully contained in another.

Advanced:

union iteration: helps implement UnionToArray, IsUnionType. could be achieved given UnionToArray or a way to access elements from a union. This could enable object iteration, or the other way around.

intersection operations

function/parameter operations

ReturnType: get the return type of function expressions -- Proposal: Get the type of any expression with typeof #6606 (dupes: Suggestion: Using typeof with an expression #4233, Type query for a result of a function call #6239, Get return type of interface function #16372)
conversion of parameters from/to tuple types: see variadic kinds at Proposal: Variadic Kinds -- Give specific types to variadic functions #5453
function composition -- still issues with generics, see Supporting generic type inference over the other higher-order functions #9366. current approach relies on overloads; might be alleviated as part of variadic kinds, see above.
currying: see function composition.
conditionally throwing 'custom' errors: given ReturnType, apply a function with arguments that would not match its requested param types
pattern matching: given ReturnType, use overloaded type-level function application to emulate pattern matching from other languages.
constraints: e.g. divisor of a division function may not be 0. given pattern matching (above), just add an extra generic to said division function using a default with pattern matching to only resolve for non-0 input, e.g. function div<B extends number, NotZero = { (v: '1') => 'whatever'; }({ (v: 0) => '0'; (v: number) => '1'; }(B))>(a: number, b: B).

operations on primitives (string/number/boolean literals)

These are currently considered out of scope, see #15645.

That said we can do a bit with natural numbers:

Numbers: Inc, Dec, Add, Subtract, Mult, Pow, DivFloor, Modulo, comparators: Gt (>), Lt (<), Gte (>=), Lte (<=)

Strings:

member access on string literals
appending string literals

Progress:

Type	Member Access	Manipulation	Iteration
Tuple	⭕	⭕ (as numerical objects until #5453)	⭕
Object	⭕	⭕	❌
Union (of string literals*)	❌	⭕	❌
Function	❌ (#6606)	❌ (#5453)	n/a
Bool	n/a	⭕ (as strings)	n/a
Number	n/a	⭕ (low-ish natural numbers)	n/a
String	❌	❌ (#15645)	n/a

*: union operators are pretty much limited to unions of string literals as it stands, as the only basic operators on unions (in + member access) both operate exclusively on these.

Not listed: type-level type checks (also need #6606)

Top features needed:

type-level function application #17961 type level function application, needed for BoolToString, map over tuples / heterogeneous objects, FilterObject, reduce, function composition
Allow calls to overloaded functions when all possible combinations of union type parameters resolve to valid overloads #17471 overload resolution / evaluation order issue: make chooseOverload consider type parameter values, not just their constraints. needed for: ReturnType, Matches / TypesEq / InstanceOf, ObjectHasElem, TupleHasElem, throwing errors, pattern matching, constraints, ObjectHasNumberIndex.
tuple type spread #17884 [...a] (tuple manipulation): can be emulated with numerical objects, but they lack methods.
extract rest params #17898 (...args: Args) => (capturing params)
WIP: type call spreads #18007 Fn(...Args) - relevant for e.g. composition, curry and bind.
consider spread tuples when matching signature #18004 spread tuples
... from union into tuple: casting union/object to tuple. note this one is tougher in that order is technically undefined. Challenges this would address include UnionLength, ObjectLength, UnionHasType, UnionToArray, ObjectNumberKeys, union member access, and ObjectToArray. this last one helps type e.g. R.toPairs; the current compromise alternative Array<a|b|c> there is less useful since it can't be iterated over (for e.g. map).
add compiler flag to enable granular inference outside var/let #17785 - skip automatic type widening for const / params
~~#16072 - generics erased~~

There are several dead links: #12215(x2), #13470, #16114, their /issues/ are missing.

Ika (@ikatyang)

Ika (@ikatyang) fixed them, thanks!

Update: I fleshed out operations on number literals (if restricted to whitelisted natural numbers), and realized that, although we can't really manipulate tuple types without ... operator, we can actually iterate over these to reconstruct them as numerical objects satisfying the ArrayLike interface (numbers + length), which could suffice as a workaround to operate on 'tuples' for now.

The implication here is that the vast majority of the remaining unresolved challenges now suddenly hinge on a single outstanding feature request (#6606).

As Playground became less suitable as things grew, I now moved the types into a repo.

Stellar work. I'm going to pour over this when I get home tonight. Maybe we should turn this into a test suite too and get it accepted into Typescript, so there's no regressions?

Simon Meskens (@SimonMeskens)

Simon Meskens (@SimonMeskens): I'd certainly love to improve lib.d.ts, though an official blessing might be more justifiable for types that could already be used to help type it than for the ones that have yet to be applied there. I investigated opportunities to improve it earlier, but haven't found many that'd work out today yet. Specifically:

much of the iteration becomes more useful when we can do stuff with function parameters (Proposal: Get the type of any expression with typeof #6606) to improve e.g. reduce, filter, and tuple-based map
~~Overwrite does not yet suffice to tackle Object.assign as (mutation aside) variadic functions need Proposal: Variadic Kinds -- Give specific types to variadic functions #5453.~~ edit: moreover, they recently added syntax that does this too.
if tuples were granted their own interfaces, iteration might already help the likes of concat there, yet though iterations works in types, it still magically breaks when used in functions (bug: functions dislike iteration? #17086)
as noted in Mapped types intersections are too eagerly resolved #17456, some of the basic building blocks like ObjectHasKey still suffer from some bugs as wel

tl;dr: hopefully, but things might not be mature enough yet.

That said I did see two types failing I'd sworn worked before, specifically Indeterminate and Ramda attempt PathOrFn. I might need to look into those again.

It feels like we should be able to do ReturnType right now. What's stopping us?

Simon Meskens (@SimonMeskens)

Simon Meskens (@SimonMeskens): try it!

interface MyFn {
  (s: string): string;
  (b: boolean): boolean;
}
// ^ example of a problematic function: overloads. similar for generics.
type Ret<F extends (...args: any[]) => R, R> = R;
type Bar = Ret<MyFn>;
// ^ error: Generic type 'Ret' requires 2 type argument(s).
declare function ret<R>(f: (...args: any[]) => R): R;
let baz = ret(null! as MyFn);
// ^ expression level, can't be composed into bigger types
// -> boolean. other option got ignored?

In function declarations, we can do an easy version naively extracting a return type, see the snippet below; a type-level-only version fails meaning we can't really put this to use in other types.
It also fails if the function's return type depended on generics, overloads, or this binding types.
There are a dozen use-cases that depend on the ability to calculate a return type appropriate for given inputs though, which is a topic that could be resolved with that 6606.

Ah yes, it's basically the issue I talked about on the dynamic function type issue. You can create such a function (well, once 2.5 lands to fix a few of the mapped type bugs), but I don't think TypeScript could ever support complex functions (generics, overloads, not sure about this bindings, you can probably support those eventually) dynamically. You could specifically write a return type construct as in 6606 of course, but the general case is probably not possible, due to the way generics are constructed.

You can create such a function (well, once 2.5 lands to fix a few of the mapped type bugs)

Could you show a snippet of how you'd go about it with that?

but I don't think TypeScript could ever support complex functions (generics, overloads, not sure about this bindings, you can probably support those eventually) dynamically.
You could specifically write a return type construct as in 6606 of course, but the general case is probably not possible, due to the way generics are constructed.

If you mean the awkward Ret attempt in that snippet, yeah.
If you mean 6606, it already calculates types of return values based on all of that for function calls made on the expression level. It's just about getting that existing operator (() / <>()) exposed in type land.

Could you show a snippet of how you'd go about it with that?

Not really, because I ran into several bugs trying to make it. The basic idea is that you specify arity by hand and the compiler will complain if the arity is incorrect. Unless we get some way to pattern match types, we can't make the compiler infer arity unfortunately. The arity can be somewhat inferred through a number of overloads at call-site.

Once 2.5 lands, I'll try to produce this type.

I'm somewhat skeptical of 6606, because if it would actually provide a fully working return type, it would be more powerful than Haskell's compiler, if I understand correctly, and I simply don't see how Typescript's generic system would give rise to such a construct. I just returned from a vacation, so my brain is currently too fried to provide an example, I'll try to do so later.

Simon Meskens (@SimonMeskens)

Simon Meskens (@SimonMeskens):

If you want you can try 2.5 nightly outside of playground. Heck, even if the code doesn't work yet, the concepts would still be interesting anyway. We'd have progress even if just for arity 0 it works purely on the type level.
On another note, alternatives would be reminiscent of #14400.
Arity I guess could be addressed by either 5453 (capturing variadics) or 6606 (overloads) itself.

I'm somewhat skeptical of 6606, because if it would actually provide a fully working return type, it would be more powerful than Haskell's compiler, if I understand correctly, and I simply don't see how Typescript's generic system would give rise to such a construct.

TypeScript has been doing type literal computations that Haskell never bothered with, e.g. property access on tuples / heterogeneous objects using number / string literals. Ditto for boolean literals, see the type guards in the tutorial.
Note that none of that required generics in the first place.

I'd asked a few Haskell friends this same question before, and their response was just kinda that it wouldn't have as much use for it, in the sense its tuples lacked number-based access, and that heterogeneous objects with string index access basically also lacked a Haskell equivalent.

I see your point now, you want to be able to infer the return type, not just typecheck it. I don't think that's possible without something like #14400.

Honestly, I feel like not having #14400 is holding the language back. That's probably my number one feature request, more inference on generic arguments.

Well, #14400 itself wouldn't address overloads/generics or the like, while we can already get the return type like that in function definitions already (ret example above). In that sense it'd be a relatively smaller step. If we could get 6606 then from what I can see that'd cover it.
Then again I also just don't know how implementing 14400 would actually work.

Giulio Canti (@gcanti)

Giulio Canti (@gcanti) Oh wow, that looks fantastic, thanks for that link! Maybe not quite suited to the rapid iteration during prototyping, but great for marking things down once we've got them wrangled a bit. That was basically what I was going to try to make anyway, so that's saved me a lot of wasted time. 😅

Giulio Canti (@gcanti)

@TheOtherSamP:

I loved PlayGround as well, and regressions weren't much of an initial concern; I was just forced to convert it as eventually a few types snuck in that had terrible performance / did not terminate.
I wanted to just comment half the types to find them binary search style, but the types depended on each other in many directions and finding the culprit was terrible.
My current situation slightly improved over that by allowing an attempt to compile one file (+ all deps) at a time.

Giulio Canti (@gcanti):

Fair enough, that does look like a potential improvement in the face of expected errors. On actual failed expectations, I recall I had a fork of it ditching line numbers from output so diff logs wouldn't get noise from line number changes, might have use for that here too. Guess I specialize in libraries that error.

I hated having to give every test line a name btw 😅, fortunately that's separate.

Seems unlike me you're also using value level expressions in your tests. That's interesting to me; I'd kept it type-level only. I don't even have any real considerations there, just sorta happened.

@tycho01 When you say

keyof: create a union of string literals from a type's keys. warts:

indices (whether number or string) get ignored

What do you mean by "ignored"? Note that keyof { foo: number; [k: string]: any } returns string, not "foo". Is that what you mean (I would call this the opposite of being ignored, myself) or did this behavior change? I do wish there were a way to get just the non-index keys from a type... is that a type operator I missed from your list?

Joe Calzaretta (@jcalz)

Joe Calzaretta (@jcalz): sorry, lemme fix that, looks like I was mistaken there!
That actually seems a bit unfortunate though, guess that means it's hard to operate on constructs like that in such a way as to retain the key-specific info...

or did this behavior change?

Could be, but for all I know I just messed up there somehow. :)

I do wish there were a way to get just the non-index keys from a type... is that a type operator I missed from your list?

Hm.... before I thought that e.g. Omit would lose the indices while retaining the keys. In that case that might have been a way. Otherwise, it's gonna be tough.

This did just helped me think of an implementation for ObjectHasStringIndex though!

Marking as closed since a discussion doesn't require moderator attention.

Joe Calzaretta (@jcalz)

Joe Calzaretta (@jcalz) Martin Johns (@MartinJohns) here is fine to me.
I tried for a bit to see if I could strip the index off an object type, but haven't managed yet.
on a related note, ObjectHasStringIndex works, but isn't helping here.

I guess if we had a keyof equivalent not screwed up by the string index, that should get us there. It seems pretty tough though. So the real keyof would yield e.g. "a" | string, which just simplifies to string, removing all the info we were actually interested in.

So the more realistic approach seems to be to use a filtered map instead. My attempt has been among the following lines:

type T = { a: 1, [k: string]: number };
type stripped = { [P in keyof T]: string extends P ? never : T[P] }; // want { a: 1 }, got { [x: string]: string }

Not sure why it fails. :(

Yeah that's about as far as I got too.

Joe Calzaretta (@jcalz)

Joe Calzaretta (@jcalz) Martin Johns (@MartinJohns) in retrospect, guess it fails because it still relies on keyof... which means back to square 1. :(

Looks like IsUnionType<T> can now be implemented using distributive conditional types, even for T that do not extend string:

type IsUnionType<T, Y=true, N=false> =
  [T] extends [infer U] ? U extends any ? [T] extends [U] ? N : Y : never : never

This exposes some fun details of what the compiler considers a union:

const literalsGetAbsorbed : IsUnionType<string | 'a'> = false;
const booleansGetDistributed: IsUnionType<boolean> = true;
const intersectionsOfUnionsAreReduced: IsUnionType<{a: 0} & ({b: 1} | {c: 2})> = true;

@tycho01 Are you still looking for a way to strip indexes? I have a way to do it

Actually, my way of doing it corresponds to your last attempt up above, which now seems to work, so you should be golden.

Doesn't that still give you type stripped = { [x: string]: never; a: 1 } instead of the desired { a: 1 }? How do you use that to strip the index?

Yeah, totally my bad. I thought I had discovered some new trick, when I didn't. I figured out most of the issues people were having as I bashed my head against it for an hour yesterday.

Navigation Menu

Repository navigation

fleshing out type operators (discussion) #16392

Operations:

Built-in operators:

Boolean operations:

Array (tuple) operations

Unary:

Binary:

Advanced:

object operations

Unary:

Binary:

Advanced:

Type operations

Type checks (binary):

Type casts (unary):

Union operations

Unary:

Binary:

Advanced:

intersection operations

function/parameter operations

operations on primitives (string/number/boolean literals)

Progress:

Top features needed:

27 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

fleshing out type operators (discussion) #16392

Description

Operations:

Built-in operators:

Boolean operations:

Array (tuple) operations

Unary:

Binary:

Advanced:

object operations

Unary:

Binary:

Advanced:

Type operations

Type checks (binary):

Type casts (unary):

Union operations

Unary:

Binary:

Advanced:

intersection operations

function/parameter operations

operations on primitives (string/number/boolean literals)

Progress:

Top features needed:

Activity

ikatyang commented on Jun 9, 2017

KiaraGrouwstra commented on Jun 9, 2017

KiaraGrouwstra commented on Jun 30, 2017

KiaraGrouwstra commented on Aug 2, 2017

SimonMeskens commented on Aug 3, 2017

KiaraGrouwstra commented on Aug 3, 2017

SimonMeskens commented on Aug 4, 2017

KiaraGrouwstra commented on Aug 4, 2017

SimonMeskens commented on Aug 4, 2017

KiaraGrouwstra commented on Aug 4, 2017

SimonMeskens commented on Aug 4, 2017

KiaraGrouwstra commented on Aug 5, 2017

SimonMeskens commented on Aug 5, 2017

KiaraGrouwstra commented on Aug 5, 2017

27 remaining items

SamPruden commented on Aug 7, 2017

KiaraGrouwstra commented on Aug 7, 2017

jcalz commented on Oct 6, 2017

KiaraGrouwstra commented on Oct 6, 2017

KiaraGrouwstra commented on Oct 25, 2017

KiaraGrouwstra commented on Feb 15, 2018

jcalz commented on Feb 15, 2018

KiaraGrouwstra commented on Feb 17, 2018

jcalz commented on Apr 23, 2018

SimonMeskens commented on Apr 23, 2018

SimonMeskens commented on Apr 23, 2018

jcalz commented on Apr 24, 2018

SimonMeskens commented on Apr 24, 2018

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions