Skip to content
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

Add a generic way to specify length of a tuple type #26223

Closed
4 tasks done
AlCalzone opened this issue Aug 6, 2018 · 35 comments · Fixed by #40002
Closed
4 tasks done

Add a generic way to specify length of a tuple type #26223

AlCalzone opened this issue Aug 6, 2018 · 35 comments · Fixed by #40002
Labels
Awaiting More Feedback This means we'd like to hear from more people who would be helped by this feature Fix Available A PR has been opened for this issue Suggestion An idea for TypeScript

Comments

@AlCalzone
Copy link
Contributor

AlCalzone commented Aug 6, 2018

Search Terms

tuple, type, length

Suggestion

I'd like to see a way to specify the length of a tuple or array type when declaring it. For short tuples, it may be viable to write them out by hand like [number, number], but whenever the length is longer (say 10+), it becomes a chore.

Using the following approach to define a fixed-length tuple

// @ts-ignore interface can only extend interface or class
interface FixedLengthArray<T extends any[], L extends number> extends T {
	length: L;
}

has a few drawbacks:
1.: we cannot extend T because its not an interface or class.
2.: when ignoring that error, tuple literals are not inferred as tuples but as arrays when assigning them:

type Foo = FixedLengthArray<number[], 5>;
const foo1: Foo = [1, 2, 3, 4, 5]; // error: length is not compatible, number not assignable to 5
const foo2: Foo = [1, 2, 3, 4, 5] as [1, 2, 3, 4, 5]; // works, but defeats the purpose of that fixed-length

On the other hand, when using manually-written tuples, this works:

type Bar = [number, number, number, number, number];
const bar1: Bar = [1, 2, 3, 4, 5]; // no error

Use Cases

Examples

I'll leave the syntax up for discussion, and provide the length in the square brackets for now:

type T1 = number[3]; // equals [number, number, number]
type K1 = keyof T1; // 0 | 1 | 2
type T2 = number[100]; // equals [number, number, ..., number] (100 items total)
type K2 = keyof T2; // 0 | 1 | ... | 99
type T3 = any[0]; // equals [ ], type annotation is somewhat obsolete here
type K3 = keyof T3; // never

The basic rules for tuple assignability should apply, as if the types were written out by hand.

Related:

#24350
#18471

Checklist

My suggestion meets these guidelines:

  • This wouldn't be a breaking change in existing TypeScript / JavaScript code
  • This wouldn't change the runtime behavior of existing JavaScript code
  • This could be implemented without emitting different JS based on the types of the expressions
  • This isn't a runtime feature (e.g. new expression-level syntax)
@j-oliveras
Copy link
Contributor

j-oliveras commented Aug 6, 2018

You can already do it:

interface FixedLengthArray<T extends any, L extends number> extends Array<T> {
    0: T;
	length: L;
}

type Foo = FixedLengthArray<number, 5>;
const foo1: Foo = [1, 2, 3, 4, 5];

At playground.

@AlCalzone
Copy link
Contributor Author

AlCalzone commented Aug 6, 2018

Oh I must have missed the trick with the 0 index. However it's not quite there, as keyof does not work like it does with tuples:

interface FixedLengthArray<T extends any, L extends number> extends Array<T> {
    "0": T;
    length: L;
}

type Foo = FixedLengthArray<number, 5>;
type Bar = [number, number, number, number, number];
type FooKey = Exclude<keyof Foo, keyof []>; // "0"
type BarKey = Exclude<keyof Bar, keyof []>; // "0" | "1" | "2" | "3" | "4"

@jcready
Copy link

jcready commented Aug 6, 2018

@AlCalzone arrays can be sparse, tuples cannot:

const array = new Array(5)
const tuple = [1, 2, 3, 4, 5]

array.length === tuple.length // true

Object.keys(array) // []
Object.keys(tuple) // ["0", "1", "2", "3", "4"]

let arrayCount = 0
let tupleCount = 0

for (let i in array) { arrayCount++ }
for (let i in tuple) { tupleCount++ }

console.log(arrayCount, tupleCount); // 0 5

@AlCalzone AlCalzone changed the title Add a way to specify length of a tuple or array type Add a way to specify length of a tuple type Aug 6, 2018
@AlCalzone AlCalzone changed the title Add a way to specify length of a tuple type Add a generic way to specify length of a tuple type Aug 6, 2018
@AlCalzone
Copy link
Contributor Author

AlCalzone commented Aug 6, 2018

@jcready I know, but I think you missed my point. I'm asking for a way to define a large tuple type for a generic length that behaves just like the ones we can write out by hand - except without writing them out by hand. See my OP:

type T1 = number[3]; // equals [number, number, number]
type K1 = keyof T1; // 0 | 1 | 2

or maybe

type T1 = Tuple<number, 3>; // equals [number, number, number]
type K1 = keyof T1; // 0 | 1 | 2

type T2 = Tuple<number, 100>; // equals [number, number, ..., number] (100 items total)
type K2 = keyof T2; // 0 | 1 | ... | 99

in case this makes the intent clearer.

I edited the issue title to reflect this intent, as sparse arrays do actually work.

@AlCalzone
Copy link
Contributor Author

Some more context: It is currently possible to create a tuple of the type [N, N-1, ..., 0] using this code:

/**
 * Creates a union from the types of an Array or tuple
 */
type UnionOf<T extends any[]> = T[number];

/**
 * Returns the length of an array or tuple
 */
type LengthOf<T extends any[]> = T["length"];

/**
 * Returns all but the first item's type in a tuple/array
 */
export type Tail<T extends any[]> =
	((...args: T) => any) extends ((head: any, ...tail: infer R) => any) ? R : never;

/**
 * Returns the given tuple/array with the item type prepended to it
 */
type Unshift<List extends any[], Item> =
	((first: Item, ...rest: List) => any) extends ((...list: infer R) => any) ? R : never;

/**
 * Tests if two types are equal
 */
type Equals<T, S> =
	[T] extends [S] ? (
		[S] extends [T] ? true : false
	) : false;

type Range<N, T extends number[] = []> = {
	0: T,
	1: Range<N, Unshift<T, LengthOf<T>>>,
}[Equals<LengthOf<Tail<T>>, N> extends true ? 0 : 1];

For example:

type T1 = Range<3>; // [3, 2, 1, 0]
type K1 = UnionOf<T1>; // 0 | 1 | 2 | 3

but this stops working for N > 98 and often freezes TypeScript while editing (#26155)

@RyanCavanaugh RyanCavanaugh added Suggestion An idea for TypeScript Awaiting More Feedback This means we'd like to hear from more people who would be helped by this feature labels Aug 6, 2018
@jcalz
Copy link
Contributor

jcalz commented Aug 6, 2018

Those of us who want full-blown dependent types for tuples (for things like type-safe immutable tuple push/pop/concat/split/etc) should give this a big 👍 .

Is there a canonical issue for dependent types for tuples? Probably needs something like one or more of:

  • compile-time number arithmetic (e.g., Add<2,2> ~ 4)
  • compile-time number comparison (e.g., LessThan<0,3> ~ true)
  • compile-time conversion between numeric string literals and number literals, (e.g., StrToNum<"0"> ~ 0)
  • compile-time specification of strict tuples of a given length (e.g., TupleLen<3, string> ~ [string, string, string]) ← we are here
  • compile-time specification of open-ended tuples of a given prefix length (e.g., OpenTupleLen<1, string> ~ [string, ...string[]])
  • compile-time specification of (strict or open) tuples with optional elements starting at some index (e.g., TupleLenOptional<3, string, 1> ~ [string, string?, string?])

Most of the above can be faked up, at least for nonnegative integers less than some bound, via a bunch of hardcoded lookup types (or via the "scary" recursion of the form type R<T> = {0: B, 1: R<F<T>>}[T extends U ? 0 : 1]), but it would be amazing if it were officially supported by the language.

@AlCalzone
Copy link
Contributor Author

AlCalzone commented Aug 7, 2018

Assume for my answers that:

  • Tuple<T, 3> is equal to [T, T, T],
  • Concat<A, B> is equal to [...A, ...B]. Does not work yet, but can be done using two recursive types (very prone to breaking).
  • Range<N> returns a union 0 | 1 | ... | N

compile-time number arithmetic (e.g., Add<2,2> ~ 4)

LengthOf<Concat< Tuple<any, 2>, Tuple<any, 2> >>
Subtraction can probably done if mapped tuples support dropping values (#26190)

compile-time number comparison (e.g., LessThan<0,3> ~ true)

Works but suffers from the neccesity for recursive definition of Range<N>:

/** Tests if N > M */
type IsGreaterThan<N, M> = N extends Exclude<Range<N>, Range<M>> ? true : false;
/** Tests if N <= M */
type IsLessThanOrEqual<N, M> = Not<IsGreaterThan<N, M>>;
/** Tests if N < M */
type IsLessThan<N, M> = M extends Exclude<Range<M>, Range<N>> ? true : false;
/** Tests if N >= M */
type IsGreaterThanOrEqual<N, M> = Not<IsLessThan<N, M>>;

compile-time conversion between numeric string literals and number literals

Yes, please!

compile-time specification of open-ended tuples of a given prefix length
and: compile-time specification of (strict or open) tuples with optional elements starting at some index

Could be done by concatenation of a fixed-length tuple and an array (when that works): [...fixed, ...array] or [...fixed, ...optional]

@KiaraGrouwstra
Copy link
Contributor

well, here's my scary recursive tuple generator @AlCalzone: Vector.
It predated features like conditional types, so shinier (and more importantly, more robust) versions may be doable now.

Add<2,2> ~ 4 - LengthOf<Concat<Tuple<any, 2>, Tuple<any, 2>>>

That's pretty creative 😄, if we had recursion-free Concat ([...T]) and Tuple then we'd have a recursion-free Add too!

others mentioned by @jcalz I recall hacky / legit implementations for:

@spat-ne-hochu
Copy link

spat-ne-hochu commented Dec 6, 2018

if we can make such generetics, then we will not be able to use

type Vec<T extends number> = T extends 1 ? [ number ] : T extends 2 ? [ number, number ] : number[];

const sum = <TLen>(a: Vec<TLen>, b: Vec<TLen>): Vec<TLen> => a.map((v, i) => v + b[i]);

const a: Vec<2> = [ 1, 2 ];
const b: Vec<2> = [ 1, 2 ];
const c = sum(a, b); // i expect c is Vec<2>... but ts think is Vec<number> // any number
const testZ =c[2]; // WTF!

@jcalz
Copy link
Contributor

jcalz commented Dec 6, 2018

You can already get the length of a tuple type T by querying T['length'], so I wouldn't recommend trying to infer it through a conditional type. So instead of

// try to infer L from Vec<L>, doesn't work 🙁
declare const sum: <L extends number>(a: Vec<L>, b: Vec<L>) => Vec<L>;

I'd do something like

// instead infer V from a vector of type V and query its length to use instead of L
declare const sum: <V extends Vec<any>>(a: V, b: Vec<V['length']>) => Vec<V['length']>;

or in this particular case just

// All the lengths are the same so just use V
declare const sum: <V extends Vec<any>>(a: V, b: V) => V;

Of course we don't know how an "official" implementation of Vec or the like would behave; hopefully you'd be able to infer L from Vec<L> without any hoop-jumping.

@AlCalzone
Copy link
Contributor Author

AlCalzone commented Dec 6, 2018

The issue is not about inferring the tuple length but about specifying it

@spat-ne-hochu
Copy link

spat-ne-hochu commented Dec 14, 2018

This tricks is dangerous bugable, ts is not support tuples in core, all tricks is bullshit.

export interface FixedLengthArray<T extends any, L extends number> extends Array<T> {
  '0': T;
  length: L;
}

export interface Vec<L extends number> extends FixedLengthArray<number, L>

const a: Vec<3> = [ 1, 2, 3 ];
const dd = b[999]; // bullshit!
b[1024]++; // bullshit!

a.push(2, 3, 4);
a.length === 6; // fuckup ha-ha is always false, no it is no solution

@spat-ne-hochu
Copy link

spat-ne-hochu commented Dec 17, 2018

And one more problem

export interface FixedLengthArray<T extends any, L extends number> extends Array<T> {
  0: T;
  length: L;
}

let a: FixedLengthArray<number, 3> = [1, 2, 3];
const [x, y, z] = a; // Type 'FixedLengthArray<number, 3>' has no property '1'.

@calidion
Copy link

calidion commented Feb 2, 2019

It is ironic for TypeScript to take so seriously for types and even template is created while length limited array types are still not supported:)

@fightingcat
Copy link

@AlCalzone In fact, if we have Tuple<T, Length>, we have Range<N>, Partial<Tuple<any, N>>['length'] will do the trick.

@AlCalzone
Copy link
Contributor Author

😳 that's some next level shit.

@AnyhowStep
Copy link
Contributor

AnyhowStep commented Jul 19, 2019

I'm sure you all know how to implement the Tuple<T, Length> type but I thought I'd put it here for completeness sake

type PushFront<TailT extends any[], FrontT> = (
    ((front : FrontT, ...rest : TailT) => any) extends ((...tuple : infer TupleT) => any) ?
    TupleT :
    never
);

type Tuple<ElementT, LengthT extends number, OutputT extends any[] = []> = {
    0 : OutputT,
    1 : Tuple<ElementT, LengthT, PushFront<OutputT, ElementT>>
}[
    OutputT["length"] extends LengthT ?
    0 :
    1
];

//type t3 = [string, string, string]
type t3 = Tuple<string, 3>;
//type length = 0 | 3 | 1 | 2
type length = Partial<Tuple<any, 3>>['length'];

Playground


With the max instantiation depth, you can't get it to be too long, though.

type TupleImpl<ElementT, LengthT extends number, OutputT extends any[]> = {
    0 : OutputT,
    1 : TupleImpl<ElementT, LengthT, PushFront<OutputT, ElementT>>
}[
    number extends OutputT["length"] ?
    0 :
    OutputT["length"] extends LengthT ?
    0 :
    1
];
type Tuple<ElementT, LengthT extends number> = (
    TupleImpl<
        ElementT,
        LengthT,
        []
    > extends infer X ?
    (
        X extends any[] ?
        X :
        never
    ) :
    never
);

//type t41 = [string, ...39 more, string]
type t41 = Tuple<string, 41>;
/**
 * Expected : type t42 = [string, ...40 more, string]
 * Actual   : Type instantiation is excessively deep and possibly infinite.
 */
type t42 = Tuple<string, 42>;
/**
 * Expected : type t42impl = [string, ...40 more, string]
 * Actual   : type t42impl = [string, ...40 more, string]
 */
type t42impl = TupleImpl<string, 42, []>;

@AnyhowStep
Copy link
Contributor

That pesky max instantiation depth rears its head again,

type PopFront<TupleT extends any[]> = (
    ((...tuple : TupleT) => void) extends ((head : any, ...tail : infer TailT) => void) ?
    TailT :
    never
);
type PushFront<TailT extends any[], FrontT> = (
    ((front : FrontT, ...tail : TailT) => void) extends ((...tuple : infer TupleT) => void) ?
    TupleT :
    never
);

/////////////////////////////////////////////////

type TupleImpl<ElementT, LengthT extends number, OutputT extends any[]> = {
    0 : OutputT,
    1 : TupleImpl<ElementT, LengthT, PushFront<OutputT, ElementT>>
}[
    number extends OutputT["length"] ?
    0 :
    OutputT["length"] extends LengthT ?
    0 :
    1
];
type Tuple<ElementT, LengthT extends number> = (
    TupleImpl<ElementT, LengthT, []> extends infer X ?
    (
        X extends any[] ?
        X :
        never
    ) :
    never
);

//type t3 = [string, string, string]
type t3 = Tuple<string, 3>;
//type length = 0 | 3 | 1 | 2
type length = Partial<Tuple<any, 3>>['length'];

type AddOne<N extends number> = (
    PushFront<Tuple<any, N>, any>["length"]
);
//type t41 = [string, ...39 more, string]
type t41 = Tuple<string, 41>;
/**
 * Expected : type t42 = [string, ...40 more, string]
 * Actual   : Type instantiation is excessively deep and possibly infinite.
 */
type t42 = Tuple<string, 42>;
/**
 * Expected : type t42impl = [string, ...40 more, string]
 * Actual   : type t42impl = [string, ...40 more, string]
 */
type t42impl = TupleImpl<string, 42, []>;
/**
 * Expected : type t42impl = [string, ...40 more, string]
 * Actual   : Type instantiation is excessively deep and possibly infinite.
 */
type t43impl = TupleImpl<string, 43, []>;


//4
type _3_plus_1 = AddOne<3>;
//5
type _4_plus_1 = AddOne<4>;
//10
type _9_plus_1 = AddOne<9>;

type SubOne<N extends number> = (
    PopFront<Tuple<any, N>>["length"]
);

//2
type _3_sub_1 = SubOne<3>;
//3
type _4_sub_1 = SubOne<4>;
//8
type _9_sub_1 = SubOne<9>;
/**
 * Expected: -1
 * Actual: 0
 * 
 * Because tuples cannot have length -1.
 * 
 * @todo Add signed-ness checks
 */
type _0_sub_1 = SubOne<0>;

type AddImpl<A extends number, B extends number> = {
    0 : B,
    1 : AddImpl<SubOne<A>, AddOne<B>>
}[
    A extends 0 ?
    0 :
    1
];
type Add<A extends number, B extends number> = (
    AddImpl<A, B> extends infer X ?
    (
        X extends number ?
        X :
        never
    ) :
    never
);
//15
type _7_plus_8 = AddImpl<7, 8>
/**
 * Excessively deep instantiation because we do not check for negative
 * 
 * @todo Add signed-ness checks
 */
type _neg1_plus_8 = AddImpl<-1, 8>
//21
type _19_plus_2 = Add<19, 2>
/**
 * Expected : 22
 * Actual   : Type instantiation is excessively deep and possibly infinite.
 */
type _20_plus_2 = Add<20, 2>

/**
 * Expected : 22
 * Actual   : number
 */
type _20_plus_2impl = AddImpl<20, 2>

Playground

@jcalz
Copy link
Contributor

jcalz commented Jul 19, 2019

🚔🚨👮‍♀️ UH OH, IT'S THE SELF-APPOINTED CIRCULAR CONDITIONAL TYPE POLICE 👮‍♂️🚨🚔

This style of construct: type A<T> = { 0: X, 1: A<B<T>>}[T extends Y ? 0 : 1] is not supported; if you use it in production code, do not be surprised if it gives unexpected or broken results in some environments... and any such code should probably feature prominent warnings to that effect.

The only official word I've seen on this is "don't do it" and "we're not ready for this". If recursive conditional types are ever officially supported in some form, I'd expect to see them included in the baseline tests for the language, so that future releases won't break them. Right now there are no such tests. Use recursive conditional types at your own risk, and inform downstream dependencies of said risk.

#26980 seems to be the canonical place to talk about this.

🚓👮‍♀️ THAT IS ALL 👮‍♂️🚓

@Semigradsky
Copy link

@colxi Your first approach with Array length parameter:

type ArrayLengthMutationKeys = 'splice' | 'push' | 'pop' | 'shift' | 'unshift' | number
type ArrayItems<T extends Array<any>> = T extends Array<infer TItems> ? TItems : never
type Tuple<T extends any[]> =
  Pick<T, Exclude<keyof T, ArrayLengthMutationKeys>>
  & { [Symbol.iterator]: () => IterableIterator< ArrayItems<T> > }

type FixedLengthArray<Type, Count extends number> =
  Count extends 1 ? Tuple<[Type]> :
  Count extends 2 ? Tuple<[Type, Type]> :
  Count extends 3 ? Tuple<[Type, Type, Type]> :
  // ...
  never;

Tests:

  var myFixedLengthArray: FixedLengthArray<string, 3>

  // Array declaration tests
  myFixedLengthArray = [ 'a', 'b', 'c' ]  // ✅ OK
  myFixedLengthArray = [ 'a', 'b', 123 ]  // ✅ TYPE ERROR
  myFixedLengthArray = [ 'a' ]            // ✅ LENGTH ERROR
  myFixedLengthArray = [ 'a', 'b' ]       // ✅ LENGTH ERROR
  
  // Index assignment tests 
  myFixedLengthArray[1] = 'foo'           // ✅ OK
  myFixedLengthArray[1000] = 'foo'        // ✅ INVALID INDEX ERROR
  
  // Methods that mutate array length
  myFixedLengthArray.push('foo')          // ✅ MISSING METHOD ERROR
  myFixedLengthArray.pop()                // ✅ MISSING METHOD ERROR
  
  // Direct length manipulation
  myFixedLengthArray.length = 123         // ✅ READ-ONLY ERROR
  
  // Destructuring
  var [ a ] = myFixedLengthArray          // ✅ OK
  var [ a, b ] = myFixedLengthArray       // ✅ OK
  var [ a, b, c ] = myFixedLengthArray    // ✅ OK
  var [ a, b, c, d ] = myFixedLengthArray // ✅ INVALID INDEX ERROR

@kernel-dev
Copy link

What's the current status on this issue?
It would be pretty convenient to be able to specify a tuple's length just by doing,

const x: T[5] // -> [T, T, T, T, T]

or,

const x: Array<T, 5> // -> [T, T, T, T, T]

@typescript-bot typescript-bot added the Fix Available A PR has been opened for this issue label Aug 16, 2020
@Semigradsky
Copy link

From PR ^

// Repeating tuples

type TupleOf<T, N extends number> = N extends N ? number extends N ? T[] : _TupleOf<T, N, []> : never;
type _TupleOf<T, N extends number, R extends unknown[]> = R['length'] extends N ? R : _TupleOf<T, N, [T, ...R]>;

type T1 = TupleOf<string, 3>;  // [string, string, string]
type T2 = TupleOf<number, 0 | 2 | 4>;  // [] | [number, number] | [number, number, number, number]
type T3 = TupleOf<number, number>;  // number[]
type T4 = TupleOf<number, 100>;  // Depth error

Looks nice! Will wait [email protected] 🤞

@lazytype
Copy link

lazytype commented Aug 16, 2020

If anyone is morbidly curious for a way to achieve a greater depth limit, here's one that constructs tuples using a logarithmic approach instead of linear:

type BuildPowersOf2LengthArrays<N extends number, R extends never[][]> =
  R[0][N] extends never ? R : BuildPowersOf2LengthArrays<N, [[...R[0], ...R[0]], ...R]>;

type ConcatLargestUntilDone<N extends number, R extends never[][], B extends never[]> =
  B["length"] extends N ? B : [...R[0], ...B][N] extends never
    ? ConcatLargestUntilDone<N, R extends [R[0], ...infer U] ? U extends never[][] ? U : never : never, B>
    : ConcatLargestUntilDone<N, R extends [R[0], ...infer U] ? U extends never[][] ? U : never : never, [...R[0], ...B]>;

type Replace<R extends any[], T> = { [K in keyof R]: T }

type TupleOf<T, N extends number> = number extends N ? T[] : {
  [K in N]: 
  BuildPowersOf2LengthArrays<K, [[never]]> extends infer U ? U extends never[][]
  ? Replace<ConcatLargestUntilDone<K, U, []>, T> : never : never;
}[N]

It has no problems with tuples with lengths of thousands. It took a pretty long while to typecheck one of length 50,000. I didn't have the patience to see how long 100K would take. Edit: It was able to eventually typecheck 100K without getting a depth error.

@dmisdm
Copy link

dmisdm commented Nov 12, 2020

This PR is friggin neat.
Here's another good use-case, typed dimensions for vectors and matrices:

type Vector<Length extends number> = TupleOf<number, Length>
type Matrix<Rows extends number, Columns extends number> = TupleOf<TupleOf<number, Columns>, Rows>

const v: Vector<2> = [1, 2]
const m: Matrix<2, 3> = [
  [1, 2, 3],
  [1, 2, 3],
]

@aigoncharov
Copy link

Guys, could anyone help me understand this line?

type TupleOf<T, N extends number> = N extends N ? number extends N ? T[] : _TupleOf<T, N, []> : never;

Specifically, N extends N. What could be the case when N does not extend N?
I changed it to simpler

type TupleOf<T, N extends number> = number extends N ? T[] : _TupleOf<T, N, []>;

and it works just as well on the provided test cases. Here is the playground link.

@ahejlsberg
Copy link
Member

@aigoncharov The N extends N ? xxx : never conditional ensures that xxx is distributed over N when N is a union type. Specifically, instead of evaluating xxx once when N is a union type, xxx is evaluated for each individual constituent of N and those evaluations are then unioned together. For more on distributive conditional types, see #21316.

Your modified type doesn't work for the following test case:

type T2 = TupleOf<number, 0 | 2 | 4>;  // Expected [] | [number, number] | [number, number, number, number]

The result of this test case changes to [] if you remove the distributive conditional.

@aigoncharov
Copy link

@ahejlsberg thank you! TS is wild. Cool, but still wild :)

@moccaplusplus
Copy link

@lazytype
I came across the same idea but my implementation looks totally different.
Although logically it makes almost the same -> it grows array exponenentialy (but stores temporary steps in P array, then it takes items from P array as from stack and appends them to generated array, - this of course if N was not exact power of 2).
Performance is also similar, it gets slow above 2^15.

type Shift<A extends Array<any>> = ((...args: A) => void) extends ((...args: [A[0], ...infer R]) => void) ? R : never;

type GrowExpRev<A extends Array<any>, N extends number, P extends Array<Array<any>>> = 
  A['length'] extends N ? A : GrowExpRev<[...A, ...P[0]][N] extends undefined ? [...A, ...P[0]] : A, N, Shift<P>>;

type GrowExp<A extends Array<any>, N extends number, P extends Array<Array<any>>> = 
  [...A, ...A][N] extends undefined ? GrowExp<[...A, ...A], N, [A, ...P]> : GrowExpRev<A, N, P>;

export type Tuple<T, N extends number> = number extends N ? Array<T> : N extends 0 ? [] : N extends 1 ? [T] : GrowExp<[T], N, [[]]>;

@sno2
Copy link
Contributor

sno2 commented Mar 8, 2021

Hello everyone, sorry for another notification, but I think that this information will be very good for newcomers and subscribers as some of the code examples above weren't working for me. There are some implementations in this thread that take the recursive approach and also the object method of setting length and 0 to create a type for a tuple of a given type with a fixed length. However, there are limitations with both of these approaches. The recursive implementation will overload if you try to create a fixed tuple of length above 45, but for the smaller sizes it allows for nice type previews that actually look like arrays ([T, T, T, ... 16 more ... T, T]). In contrast, the object approach just shows T[] & { 0: T, length: 21 } when you hover over the type and in error messages. Thus, I have created a type (List.Locked) that can take any length L and any type T to create a sized array type with items of type T of length L (Scroll to the bottom for examples) using the method that would best suite the size. For sized arrays under 45 elements (inclusive) large, it uses the object approach as it does not hit the maximum type computation size that happens with the recursive approach. Here is the code:

declare namespace Comparator {
  /** Gives back a boolean type that represents whether `T` extends `F` (similar). */
  export type StrictSimilar<T, F> = T extends F ? true : false;

  /** Gives back a boolean type that represents whether `T` and `F` are equal. */
  export type Equal<T, F> = StrictSimilar<T, F> extends true
    ? StrictSimilar<F, T>
    : false;
}

/** These types help you manipulate both tuples and arrays. */
declare namespace List {
  /** An array of `T` that can be readonly or not. */
  export type LooseList<T = unknown> = T[] | readonly T[];

  /** Recursive types that have tuple incrementors will overflow if they have more than 44 elements. */
  export type RecTupleOverflowMax = 44;

  /** Gets the length of an array. */
  export type Length<T extends LooseList> = T["length"];

  /** Makes a tuple of length `L` with each of the elements of type `T`. */
  export type Locked<L extends number, T, $Draft extends LooseList<T> = []> =
    //
    Comparator.Equal<Length<$Draft>, L> extends true
      ? $Draft // ship it
      : Comparator.Equal<Length<$Draft>, RecTupleOverflowMax> extends true // it will overflow if it's large so we need to do the hacky way
      ? T[] & { 0: T; length: L }
      : Locked<L, T, [...$Draft, T]>;

  /** Forms a union of all types within the array/tuple type. */
  export type Squash<T extends LooseList> = T[number];
}

// no error
const a: List.Locked<2, true> = [true, true];

// no error
const b: List.Locked<5, "hello" | "world" | 23> = [
  "hello",
  23,
  "world",
  "hello",
  23,
];

// no error
const c: List.Locked<0, true> = []; // []

// no errors
const names = ["Jeff", "Joe", "James"] as const;
type NonUniqueNames = List.Locked<3, List.Squash<typeof names>>; // ["Jeff" | "Joe" | "James", "Jeff" | "Joe" | "James"]
const stragglers: NonUniqueNames = ["James", "Jeff", "James"];

// no overflow errors 🎉
type BigData = List.Locked<100, number>; // number[] & { 0: number; length: 100; }
const d: BigData = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];

I will include a link here when I add this code to my Deno module (type_toolkit) that has a bunch of types for everyone to use. Hopefully this code helps you out when trying to understand how this works as I tried to document it as well as I could.

@unional
Copy link
Contributor

unional commented Mar 30, 2022

I have an implementation that utilize some tricks and template literal. Performance-wise seems to be even better. I'm using it for the math operations like Add and Subtract.

Just updated the CreateTuple<L, T> based on the implementation of @lazytype.

(updated to use the Digit implementation)

Have not get time to try implement it using the Digit. :)
https://github.com/unional/type-plus/blob/main/ts/math/Add.ts
https://github.com/unional/type-plus/blob/main/ts/math/Digit.ts

But currently all implementations are limited by the resulting Tuple size at 10000:

Type produces a tuple type that is too large to represent.

@jcalz
Copy link
Contributor

jcalz commented Aug 10, 2023

Yeah, #42448 capped tuple lengths at 10,000 which is a shame because the performance of some of these techniques was quite good even with huge tuples. Oh well.

@sno2
Copy link
Contributor

sno2 commented Aug 10, 2023

But currently all implementations are limited by the resulting Tuple size at 10000:

Type produces a tuple type that is too large to represent.

FWIW you should be able to still use this to scale to larger numbers. I initially created a math-in-TS solution via using only string literals before there were string-to-number conversions available.

type Foo = Int.Add<25913452093485, 3000053490953045>;
//   ^? 3025966943046530

However, with the ${23}` extends `${N extends infer Number} updates I converted it to use number literals. Here's a playground link for the technique: https://tsplay.dev/mb3kPW (Although the repo is a far better reference)

Also note my multiplication/exponent/division impls were WIP and buggy.

@unional
Copy link
Contributor

unional commented Aug 10, 2023

Also update that type-plus now also uses a literal-based conversion. Supporting positive, negative, bigint, and floating points.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Awaiting More Feedback This means we'd like to hear from more people who would be helped by this feature Fix Available A PR has been opened for this issue Suggestion An idea for TypeScript
Projects
None yet
Development

Successfully merging a pull request may close this issue.