296 - Permutation (with explanations)

[eXamadeus]

Answer Playground Link (TypeScript 4.1+ only)

type Permutation<T, K=T> =
    [T] extends [never]
      ? []
      : K extends K
        ? [K, ...Permutation<Exclude<T, K>>]
        : never

type Permuted = Permutation<'a' | 'b'>  // ['a', 'b'] | ['b' | 'a']

Whoa...that is weird looking. Don't worry I'll break it all down; weird piece, by weird piece 😆

TLDR by @mistlog (Click me)

https://github.com/type-challenges/type-challenges/issues/614#issuecomment-790210311

Excellent Chinese translation by @zhaoyao91 (Click me)

https://github.com/type-challenges/type-challenges/issues/614#issuecomment-1312632631

Explanation

[T] extends [never]

What in the bowels of 16-bit hell is that? Glad you asked. That my friends is a "feature" of TypeScript. It makes sense eventually, so just bear with me.

Imagine you want to make a function called: assertNever. This function would be used for checking to make sure a type is...well...never. Pretty simple concept. You might want to use it to check some weird types you are building or something. Just roll with it, OK?

Wanna know a juicy secret? (Click me)

I totally stole the idea of the example I'm explaining here

Anywho, here is what we might create on our first pass:

function assertNever<T>(value: T extends never ? true : false) {}

Cool, we've got something. Let's give it a whirl:

assertNever<string>(true)
//                  ^^^^ TS Error (2345)
// Argument of type 'true' is not assignable to parameter of type 'false'.

Nice, just what we wanted. This should throw an error because string isn't assignable to never. Why does "string not being assignable to never" mean we get an error? Because the expected type of the value param in assertNever will be false when T extends never is false and string extends never is false. Since we always pass true to the function, we get an error just like we wanted.

assertNever<never>(true)  // this should compile fine. never should extend never, right?

Uh oh, it doesn't work right. We are getting an error here too...weird. But this error is kinda funky...

assertNever<never>(true)
//                 ^^^^ TS Error (2345)
// Argument of type 'boolean' is not assignable to parameter of type 'never'.

"boolean is not assignable to parameter of type never"? But...the parameter should only be true | false right? If T extends never it should be true and if T extends never is not the case, it should be false, right?

Well, it turns out T extends never doesn't work when T = never but not because of anything to do with the conditional. TypeScript does an interesting thing when unpacking generics into conditionals: it distributes them.

Minor Primer on Distributive Conditional Types (Click me)

Basically, TypeScript sees this: T extends U ? X : Y and when provided with a type argument where T = 'A' | 'B' it gets "distributed" and resolved as (A extends U ? X : Y) | (B extends U ? X : Y).

So let's tie this back into distributing over never. TypeScript does recursive distribution over type unions. Also note that there is no such thing as a union of unions, a union of unions is just a bigger union with all the elements of all unions in it...

Anyway, the meat of this is: TypeScript treats never as an empty union when distributing over conditionals. This means that 'a' | never when getting distributed just gets shortened to 'a' when distributing. This also means 'a' | (never | 'b') | (never | never) just becomes 'a' | 'b' when distributing, because the never part is equivalent to an empty union and we can just combine all the unions.

So bringing it all in, TypeScript simply ignores empty unions when distributing over a conditional. Makes sense right? Why distribute over a conditional when there is nothing to distribute over?

Now that we know that, we know T extends never as a conditional is NEVER going to work (pun intended). So how do we tell TypeScript NOT to look at never as an empty union? Well, we can force TypeScript to evaluate T before trying to distribute it. This means we need to mutate the T type in the conditional so the never value of T gets captured and isn't lost. We do this because we can't distribute over an empty union (read never) type for T.

There are a few easy ways to do this, fortunately! One of them is to just slap T into a tuple: [T]. That's probably the easiest. Another one is to make an array of T: T[]. Both examples work and will "evaluate" T into something other than never before it tries to distribute over the conditional. Here are working examples of both methods (playground link):

function assertNeverArray<T>(value: T[] extends never[] ? true : false) {}
function assertNeverTuple<T>(value: [T] extends [never] ? true : false) {}

// both of these fail, as expected
assertNeverArray<string>(true)
assertNeverTuple<string>(true)

// both of these pass, as expected
assertNeverArray<never>(true)
assertNeverTuple<never>(true)

Phew, finally done with the first line...

Now that you're back from crying in the bathroom...

K extends K

Oh, boy...what the heck is this? This is even WEIRDER than the other one.

Alas! We are now armed with knowledge. Think about it...let's see if you can guess why this is here...I'll give you a hint: what happens to unions in a conditional type?

The answer... (Click me)

K extends K is obviously always going to be true right? So why even have it in a conditional in the first place? I mean, sure, type unions get distributed over conditionals, but we also know that...wait!?!? "Type unions get distributed over conditionals", that's it!

This is a cheeky hack to make 'a' | 'b' | 'c' result parse over a then b then c in the conditional. It makes each one trigger the conditional then unions the results together. Pretty awesome huh? It's kinda like a for-each loop for type unions.

For our example K extends K will be evaluated for 'a' | 'b' | 'c' three times. Then there will be N! tuples built per iteration (because we recurse with N-1). The way TypeScript works is that unions are flat, so all the unions of the inner recursions will be lifted to the final level.

OK, so let's break down the "loops" in the distribution, so we can see what's happening. Here is a small cheat sheet for the chart:

type P = Permutation;
type X = Exclude
// Remember Permutation<never> => [] so P<never> => []

The final result of Permutation<1 | 2 | 3> will be the values in the "Result" column union-ed together. (unified?)

If you want to see the definition for Permutation, click me

type Permutation<T, K=T> =
    [T] extends [never]
      ? []
      : K extends K
        ? [K, ...Permutation<Exclude<T, K>>]
        : never

Iteration	T	K in K extends K	X<T, K>	[K, ...P<X<T, K>>]	Result
1	1 | 2 | 3	1	2 | 3	[1, ...P<2 | 3>]
1.1	2 | 3	2	3	[1, 2, ...P<3>]
1.1.1	3	3	never	[1, 2, 3, ...[]]	[1, 2, 3]
1.2	2 | 3	3	2	[1, 3, ...P<2>]
1.2.1	2	2	never	[1, 3, 2, ...[]]	[1, 3, 2]
2	1 | 2 | 3	2	1 | 3	[2, ...P<1 | 3>]
2.1	1 | 3	1	3	[2, 1, ...P<3>]
2.1.1	3	3	never	[2, 1, 3, ...[]]	[2, 1, 3]
2.2	1 | 3	3	1	[2, 3, ...P<1>]
2.2.1	1	1	never	[2, 3, 1, ...[]]	[2, 3, 1]
3	1 | 2 | 3	3	1 | 2	[3, ...P<1 | 2>]
3.1	1 | 2	1	2	[3, 1, ...P<2>]
3.1.1	2	2	never	[3, 1, 2, ...[]]	[3, 1, 2]
3.2	1 | 2	2	1	[3, 2, ...P<1>]
3.2.1	1	1	never	[3, 2, 1, ...[]]	[3, 2, 1]

As mentioned earlier, TypeScript lifts all of the inner recursive unions and flattens them. More easily understood, the final type of Permutation<1 | 2 | 3> will be the union of the "result" types in the right-hand column. So we will find Permutation<1 | 2 | 3> is equivalent to:

[1,2,3] | [1,3,2] | [2,1,3] | [2,3,1] | [3,1,2] | [3,2,1]

---

And that concludes my long-winded explanation. I hope you enjoyed it!

[sorokin-evgeni]

Great explanation, thank you. But I have an error when try to run this code: Type 'Permutation' is not generic. It doesn't allow circular dependencies.

[eXamadeus]

@sorokin-evgeni What version of TypeScript are you running this with? I think 4.1 is the one that supports recursive conditional types.

This playground link should show that it works.

[mistlog]

summary:

how to loop union:

type loopUnion<Union extends string, Item extends string = Union> = Item extends Item ? `loop ${Item}` : never;
type result = loopUnion<"A" | "B" | "C">; // "loop A" | "loop B" | "loop C" 

how to check "T is never"

type IsNever<T> = [T] extends [never] ? true : false;

the answer:

type Permutation<Union, Item = Union> = Item extends Item ? PermuteItem<Union, Item> : never;
type PermuteItem<Union, Item, Rest = Exclude<Union, Item>> = IsNever<Rest> extends true ? [Item] : [Item, ...Permutation<Rest>];

[ginobilee]

K extends K
        ? [K, ...Permutation<Exclude<T, K>>]
        : never

Great explanation. Now I know the K in [K, ...Permutation<Exclude<T, K>>] is the distributed one, but at the first how do you know that theoretically?

[Dsan10s]

This is one of the best explanations I've seen on the subtleties of TypeScript, period. Thank you @eXamadeus !

[eXamadeus]

@Dsan10s:

This is one of the best explanations I've seen on the subtleties of TypeScript, period. Thank you @eXamadeus !

Thanks! I am really glad people are finding it useful.

@ginobilee:

K extends K
        ? [K, ...Permutation<Exclude<T, K>>]
        : never

Great explanation. Now I know the K in [K, ...Permutation<Exclude<T, K>>] is the distributed one, but at the first how do you know that theoretically?

Just making sure I understand the question, are you asking "how did I learn about the distribution of union types in a type conditional"?

[ginobilee]

@Dsan10s:

This is one of the best explanations I've seen on the subtleties of TypeScript, period. Thank you @eXamadeus !

Thanks! I am really glad people are finding it useful.

@ginobilee:

K extends K
        ? [K, ...Permutation<Exclude<T, K>>]
        : never

Great explanation. Now I know the K in [K, ...Permutation<Exclude<T, K>>] is the distributed one, but at the first how do you know that theoretically?

Just making sure I understand the question, are you asking "how did I learn about the distribution of union types in a type conditional"?

no, I mean there are tow 'K' in [K, ...Permutation<Exclude<T, K>>], but they represent two different type variable; so it seems the first K means the distributed one, the second K is the original type variable, but how do you know it at the first, instinctively?

[cchudant]

That helped me a lot. Thank you!

[patrick100]

I think there is a mistake in the table. In iteration 3.1.1, 'T' should be 2, and 'K in K extends K' also.

[eXamadeus]

I think there is a mistake in the table. In iteration 3.1.1, 'T' should be 2, and 'K in K extends K' also.

Whoa, good catch! Thanks. I'm just glad someone read the whole thing, haha. I'll update it immediately.

[callqh]

nb

[eXamadeus]

@Dsan10s:

This is one of the best explanations I've seen on the subtleties of TypeScript, period. Thank you @eXamadeus !

Thanks! I am really glad people are finding it useful. @ginobilee:

K extends K
        ? [K, ...Permutation<Exclude<T, K>>]
        : never

Great explanation. Now I know the K in [K, ...Permutation<Exclude<T, K>>] is the distributed one, but at the first how do you know that theoretically?

Just making sure I understand the question, are you asking "how did I learn about the distribution of union types in a type conditional"?

no, I mean there are tow 'K' in [K, ...Permutation<Exclude<T, K>>], but they represent two different type variable; so it seems the first K means the distributed one, the second K is the original type variable, but how do you know it at the first, instinctively?

Sorry I was slow to answer. Actually, both of the K's in [K, ...Permutation<Exclude<T, K>>] are the same K. Both are the distributed type. The Exclude<T, K> bit is removing the distributed type K from the union T.

[Lionad-Morotar]

awesome

[Finesse]

K extends K

The right part can be any type that K can be assigned to, TypeScript will iterate over every possible K subtype anyway. For example:

K extends unknown
	? [K, ...Permutation<Exclude<T, K>>]
    : ThisTypeDoesntMatterAtAll

[yiheinchai]

Thank you for this explanation! I was confused as to WHY you were checking [T] = [never] until I realised it was the base case for recursion.

[wangi4myself]

know a lot from this article,thanks!! [T] extends [never] is the essential not only for Expect<Equal<Permutation, []>> but also the base case for recursion.

[zhaoyao91]

Learned a lot from this article,thanks! I wrote a Chinese detailed expanlatation for anyone need it: https://juejin.cn/post/7165170011282079751

[eXamadeus]

Learned a lot from this article,thanks! I wrote a Chinese detailed expanlatation for anyone need it: https://juejin.cn/post/7165170011282079751

Whoa, those charts are amazing! I don't read or speak Chinese, but that article looks like a good breakdown and is likely even more detailed than my post. Great work!

[yiheinchai]

Learned a lot from this article,thanks! I wrote a Chinese detailed expanlatation for anyone need it: https://juejin.cn/post/7165170011282079751

你解释的很清楚，谢谢！

[idebbarh]

Thank youuu

[jaxkashif34]

@eXamadeus Thanks for this great explanation❤ got to learn about distributive conditionals. can you help me understand At the end of iteration 1.1.1 Exclude return never and I belive that never will pass in Permutation in 1.2 iteration and value of T will be never and when [T] excludes [never] ? [] : ..... returns []. I know I'm misunderstanding something can you help me to understand how iteration 1.2 will start with 2 | 3 . thanks

[NameWjp]

awesome！

[Regestrac]

Great explanation...!

[rxMATTEO]

Lovely language. Enjoying every second, when i'm solving challenges in this repo.

[eXamadeus]

@eXamadeus Thanks for this great explanation❤ got to learn about distributive conditionals. can you help me understand At the end of iteration 1.1.1 Exclude return never and I belive that never will pass in Permutation in 1.2 iteration and value of T will be never and when [T] excludes [never] ? [] : ..... returns []. I know I'm misunderstanding something can you help me to understand how iteration 1.2 will start with 2 | 3 . thanks

Glad you liked it!

It's a complicated chart, but essentially 1.1.1 is a "terminal" iteration. It would probably be better represented in a graph format, but a table was what I had. If you look at the value of T in 1.1 and 1.2, you will see that they're the same value. The K in K extends K value is the next iteration of distribution over the union K.

Iteration 1.2 is a follow up to 1.1 (where 1.1.1 is a termination of 1.1). Looking back, I wish I chose a better numbering system. It's kind of confusing.

[nomoreyou]

不会英语只能说声卧槽牛逼

[oliverfunk]

@eXamadeus how would one do something like the following in a single type?

type FullyPermuted =
  | Permutation<"a" | "b" | "c">
  | Permutation<"a" | "b">
  | Permutation<"b" | "c">

Where you would use it like:

type FullyPermuted = FullPermutation<"a" | "b" | "c">

Would also be interesting to see one with each distinct value too:

type PermutedDistinct =
  | Permutation<"a" | "b" | "c">
  | Permutation<"a" | "b">
  | Permutation<"b" | "c">
  | "a"
  | "b"
  | "c";