타입챌린지 : 296-Permutation (medium)

 
이 글은 제가 타입챌린지를 하면서 해석한 내용을 적는 글입니다. 틀린 내용이 있으면 댓글 달아주시면 감사하겠습니다.
 
https://github.com/type-challenges/type-challenges/blob/main/questions/00296-medium-permutation/README.md

GitHub - type-challenges/type-challenges: Collection of TypeScript type challenges with online judge

 
순열 타입을 만드는 문제이다.
 
처음에는 Union을 Tuple로 바꾸고 풀어보고자 했다.

// 오답
type UnionToIntersection<U> =
  (U extends any ? (k: U) => void : never) extends ((k: infer I) => void) ? I : never
type LastOf<T> =
  UnionToIntersection<T extends any ? () => T : never> extends () => (infer R) ? R : never

type Push<T extends any[], V> = [...T, V];

type TuplifyUnion<T, L = LastOf<T>, N = [T] extends [never] ? true : false> =
  true extends N ? [] : Push<TuplifyUnion<Exclude<T, L>>, L>

type TupleToUnion<T> = T extends [infer F, ...infer O] ? F | TupleToUnion<O> : never;

type Permutation<T> = TuplifyUnion<T> extends [infer F, ...infer O] ? TupleToUnion<[F, ...TuplifyUnion<Permutation<TupleToUnion<O>>>]> : never;

스택오버플로우의 코드를 가지고와서 풀려고 하였으나... Tuple에서 원소를 하나하나 순서를 바꿔가면서 순회하는게 불가능했다... (혹시나 방법을 아시면 댓글 부탁드립니다)
참고로, TuplifyUnion 타입은 스택오버플로우에서 사용하지 말라고 했다 ㅋㅋㅋ
 

결론적으로, 이 문제는 분산 조건부 타입을 이용해서 풀어야한다.

그리고 이 문제를 풀기 전에, 분산 조건부 타입의 특징 중 하나를 알아야한다.
 

분산 조건부 타입의 특징 : Naked Type

Naked Type Parameter는 우리가 흔히 사용하는 제네릭 T와 같이 의미가 없는 타입 파라미터를 말한다.
분산 조건부 타입은 이러한 Naked Type Parameter에 대해서'만' 유니온을 분산시켜서 계산한다.
아래의 코드를 봐보자.

type P<T> = T extends string ? 'yes' : 'no';

type P2 = 'A'|'B'| 1 extends string ? 'yes' : 'no';

type T = P<'A'|'B'| 1>; // "no" | "yes"

type T2 = P2;  // "no"

T의 결과는 "no" | "yes" 이고, T2의 결과는 "no"이다.
P<'A'|'B'|'C'>도 T에 해당 값이 들어가면 'A' | 'B' | 'C' extends string ? 'yes' : 'no'; 로 P2와 같은데 왜 다를까?
그건 바로 T라는 Naked Type Parameter가 쓰였기 때문이다. 이건 타입스크립트의 하나의 법칙이라고 이해하면 된다.
 
만약에 T를 Naked Type Parameter가 아니게 만들고 싶다면, T에 무언가 붙여주면 된다.

// ex1
type P<T> = [T] extends [string] ? 'yes' : 'no';

type T = P<'A'|'B'| 1>; // "no"

// ex2
type P<T> = T[] extends any ? 'yes' : 'no';

type T = P<'A'|'B'| 1>; // "yes"

위의 두 예 모두 다 T가 제네릭이지만, 변형된 타입이라서 분산이 되지 않는다.
 
그래서 Permutation의 결과 값이 A나 B 또는 C가 오게 하려면, 제네릭 T를 그대로 분산하면 A[] | B[] | C[] 인 타입이 되기 때문에, 제네릭 T를 다음과 같이 변형해주어야한다.

type Permutation<T> = [T] extends [any] ? T[] : never;

type A = Permutation<'A'|'B'|'C'>; // ("A" | "B" | "C")[]

// 오답
type Permutation<T> = T extends any ? T[] : never;

type A = Permutation<'A'|'B'|'C'>; // "A"[] | "B"[] | "C"[]

이렇게 되면 1단계는 끝났다. 이제 2단계를 해결해야할 차례이다.
그 문제는 바로, 원소들을 순서를 바꿔가며 Tuple로 만들어야 한다는 것이다. 하지만, 위에서 내가 Tuple을 이용해서 원소들을 순서를 바꿔가며 순회하려고 했을 때, 잘 되지 않았다. 그렇기에 우리는 Union의 분산이라는 특징을 이용해야 한다.
 
그래서 다음과 같이 코드를 작성해보았다.

type Permutation<T, K = T> = [T] extends [any] ? 
	(K extends any ? [K, ...Permutation<Exclude<T, K>>] : []) : 
	[];

여기서 문제가 발생했다. 그것은 바로 Exclude<[], []>는 never를 리턴한다는 점과 T extends never는 뒤에 조건을 따지지 않고 바로 never를 리턴한다는 점이다.
그래서 결론적으로 위의 Permutation 타입은 never를 리턴한다. (T가 never이기 때문에)
 
그래서 미리 T가 never인 경우에는 빈 배열을 리턴해주어야 한다.
따라서 다음과 같이 코드를 작성할 수 있다.

// 정답
type MyExclude<T, K> = T extends K ? never : T;

type Permutation<T, K = T> = [T] extends [never] ?
	[] : K extends any ? 
    [K, ...Permutation<MyExclude<T, K>>] : 
    [];


/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '@type-challenges/utils'

type A = Permutation<'A'|'B'|'C'>;

type B = Exclude<[], []>

type cases = [
  Expect<Equal<Permutation<'A'>, ['A']>>,
  Expect<Equal<Permutation<'A' | 'B' | 'C'>, ['A', 'B', 'C'] | ['A', 'C', 'B'] | ['B', 'A', 'C'] | ['B', 'C', 'A'] | ['C', 'A', 'B'] | ['C', 'B', 'A']>>,
  Expect<Equal<Permutation<'B' | 'A' | 'C'>, ['A', 'B', 'C'] | ['A', 'C', 'B'] | ['B', 'A', 'C'] | ['B', 'C', 'A'] | ['C', 'A', 'B'] | ['C', 'B', 'A']>>,
  Expect<Equal<Permutation<boolean>, [false, true] | [true, false]>>,
  Expect<Equal<Permutation<never>, []>>,
]

아, 그리고 위의 코드에서 T extends never하면 바로 never를 리턴해버리기 때문에, [T] extends [never]로 코드를 변경해서 never를 리턴하지 않도록 해주어야 한다.
 
 
 
아니면 MyExclude의 리턴 값이 never가 안나오게 하는 방법도 있을거 같은데... 그렇게 해도 Permutation에서 never가 리턴이 되어버려서 값이 제대로 출력이 되지 않는다. (방법이 없는 것 같다)