-
-
Notifications
You must be signed in to change notification settings - Fork 4.5k
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
296 - Permutation (with explanations) #614
Comments
Great explanation, thank you. |
@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. |
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>]; |
Great explanation. Now I know the |
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.
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 |
That helped me a lot. Thank you! |
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. |
nb |
Sorry I was slow to answer. Actually, both of the |
awesome |
The right part can be any type that K extends unknown
? [K, ...Permutation<Exclude<T, K>>]
: ThisTypeDoesntMatterAtAll |
Thank you for this explanation! |
know a lot from this article,thanks!! |
Learned a lot from this article,thanks! |
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! |
你解释的很清楚,谢谢! |
Thank youuu |
@eXamadeus Thanks for this great explanation❤ got to learn about distributive conditionals. can you help me understand |
awesome! |
Great explanation...! |
Lovely language. Enjoying every second, when i'm solving challenges in this repo. |
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 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. |
不会英语只能说声卧槽牛逼 |
@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"; |
Answer Playground Link (TypeScript 4.1+ only)
Whoa...that is weird looking. Don't worry I'll break it all down; weird piece, by weird piece 😆
TLDR by @mistlog (Click me)
Excellent Chinese translation by @zhaoyao91 (Click me)
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)
Anywho, here is what we might create on our first pass:
Cool, we've got something. Let's give it a whirl:
Nice, just what we wanted. This should throw an error because
string
isn't assignable tonever
. Why does "string
not being assignable tonever
" mean we get an error? Because the expected type of thevalue
param inassertNever
will befalse
whenT extends never
is false andstring extends never
is false. Since we always passtrue
to the function, we get an error just like we wanted.Uh oh, it doesn't work right. We are getting an error here too...weird. But this error is kinda funky...
"
boolean
is not assignable to parameter of typenever
"? But...the parameter should only betrue | false
right? IfT extends never
it should betrue
and ifT extends never
is not the case, it should befalse
, right?Well, it turns out
T extends never
doesn't work whenT = 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)
So let's tie this back into distributing over
never
. TypeScript does recursive distribution over type unions. This is because, in reality, there is no such thing as a recursive union, 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 thenever
part is equivalent to an empty union and we can just combine all the unions.So bringing it all in, TypeScript just 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 atnever
as an empty union? Well, we can force TypeScript to evaluateT
before trying to distribute it. This means we need to mutate theT
type in the conditional so thenever
value ofT
gets captured and isn't lost. We do this because we can't distribute over an empty union (readnever
) type forT
.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 ofT
:T[]
. Both examples work and will "evaluate"T
into something other thannever
before it tries to distribute over the conditional. Here are working examples of both methods (playground link):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)
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:
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 meT
K
inK extends K
X<T, K>
[K, ...P<X<T, K>>]
1 | 2 | 3
1
2 | 3
[1, ...P<2 | 3>]
2 | 3
2
3
[1, 2, ...P<3>]
3
3
never
[1, 2, 3, ...[]]
[1, 2, 3]
2 | 3
3
2
[1, 3, ...P<2>]
2
2
never
[1, 3, 2, ...[]]
[1, 3, 2]
1 | 2 | 3
2
1 | 3
[2, ...P<1 | 3>]
1 | 3
1
3
[2, 1, ...P<3>]
3
3
never
[2, 1, 3, ...[]]
[2, 1, 3]
1 | 3
3
1
[2, 3, ...P<1>]
1
1
never
[2, 3, 1, ...[]]
[2, 3, 1]
1 | 2 | 3
3
1 | 2
[3, ...P<1 | 2>]
1 | 2
1
2
[3, 1, ...P<2>]
2
2
never
[3, 1, 2, ...[]]
[3, 1, 2]
1 | 2
2
1
[3, 2, ...P<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 findPermutation<1 | 2 | 3>
is equivalent to:And that concludes my long-winded explanation. I hope you enjoyed it!
The text was updated successfully, but these errors were encountered: