Permutation, 타입으로 순열 구현하기

타입 챌린지의 문제인데, 미디움에 있었다.

끔찍한 수준의 난이도인데 이게 왜 medium인지 모르겠다.

아래에 문제를 이해하기 위해 필요한 지식과 해석 순서를 모두 기재하였으니 참고하도록 하자.

 

문제, 그리고 필요로 하는 결과

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>, []>>,
]

분산적 조건 타입

type Singular<T> = T extends never ? true : false;
type IfAnySingular = Singular<any>; // boolean

타입스크립트 핸드북 - 분산적 조건 타입

Documentation - Conditional Types

 

분산적 조건 타입 원칙에 따라 어떤 타입이 유니온으로 정의된 경우, 각각의 유니온이 타입이 적용된 이후 결과 값의 유니온 타입으로 정의된다.
만약 어떠한 타입 A를 타입 파라미터로 할당할 때 A[]를 제공하는 타입이 있다고 가정해보자.
이 때 타입 A가 number | string 타입인 경우 number[] | string[]으로 바뀌지, (number | string)[] 타입이 되지 않는다는 것을 의미한다.
이 말은 즉슨, number | string과 (number | string)의 의미가 서로 다르다는 것으로 이해할 수 있다.

 

제너릭 T에 대한 분산적 조건 타입

아직 타입을 알 수 없는 제너릭 T에 대해서도 분산적 조건 타입 원칙은 성립한다.
따라서 T는 경우에 따라 ( 즉, 유니온일 경우 ) 양측 true와 false가 모두 성립할 수 있어 보편적인 경우 true | false가 되고, 이는 다시 boolean으로 추론된다.

 

never에 대한 조건 타입, never extends never ?

type isA =  'a' | never extends 'a' ? true : false; // true

다만 조건문에 선언된 never의 경우에는 어떠한 분기도 수행되지 않는다.
isA 타입을 보면 'a'는 extends 'a'가 성립하기 때문에 true가 나와야 하고, never의 경우에는 false가 나와서 결과적으로 true | false가 되야 할 것 같아 보인다.
이는 앞서 말한 것과 합쳐 생각해보면 boolean으로 추론되는 것이 타당해 보일 것이다.
하지만 isA의 결과는 그저 true인데, 이는 never의 조건문이 아예 수행되지도 않는다는 것을 의미한다.

이는 자바스크립트로 치면 빈 배열의 Array.prototype.map의 연산이 실행되지 않는 것과 유사하다.

 

type Singular<T> = T extends never ? true : false;
type IfAnySingular = Singular<any>; // boolean

type IfNeverSingular = Singular<never>; // never

Singular<never>는 어떠한 연산도 수행되지 않기 때문에 타입이 정의되지 않은 것이나 마찬가지기에 이는 never와 같다.
제대로 "실행"되기만 하면 우리가 원하는대로 나올 법도 한데, 어떻게 해야 이 타입 분기문을 실행시킬 수 있는가?

 

never에 대한 조건 타입 실행시키기

이를 간단하게 해결하는 방법은 튜플을 이용해서 타입을 감싸주는 것이다.
우리가 원하는 동작은 never 일 경우에는 false가 나오게 하는 것이고, 그렇지 않은 경우에는 true가 나오게 하는 것인데,
이 방법을 쓰면 IfAnyPackaging 타입은 true로, IfNeverPackaging 타입은 false가 되게끔 해줄 수 있다.
튜플이 존재하기 때문에 [never] 에 대해서도 conditionals 에 대해서도 타입을 검사하는 로직이 "실행"되어 true 아니면 false, 둘 중 하나로 추론될 수 있게 된다.

 

type Packaging <T> = [T] extends [never] ? true : false;
type IfAnyPackaging = Packaging<any>; // false
type IfNeverPackaging = Packaging<never>; // true

여기까지 왔으면 이제 값이 never인 경우를 처리할 수 있게 된 것이다.

 

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

남은 것은 SOME_TYPE을 정의하는 일이다.

 

유니온을 배열로 바꾸는 타입

이를 위해서는 일단 T가 유니온이기 때문에, 유니온을 각각의 타입으로 분리해줄 필요가 있다.
여기서는 유니온 T를 각각의 타입으로 분리한 후 튜플로 감쌀 것이다.

아래에 있는 K = T와 K extends K는 매우 당혹스러울 테지만, 일단 아래의 설명을 차근차근 따라가보자.

 

type UnionToArray<T, K = T> = K extends K ? [K] : [Exclude<T, K>];

뒷 부분 이 역시 분산성 원칙을 이용해서 정의할 수 있다.
유니온 타입과 extends 키워드를 이용한 conditions는 각각의 타입들에 대한 결과를 다시 유니온으로 결합한 타입이라고 앞서 말한 적 있다.
따라서 1개를 고른 후 "나머지" 라는 말은, "1개를 고른" 즉, 각각의 타입들을 실행시켜본다는 것을 의미한다.
이 원칙에 따라 유니온은, 유니온 만큼의 실행 결과에 따라 아래 UnionToArray 타입은 유니온 숫자만큼의 튜플을 만들어낸다.

T는 처음에 입력받은 유니온이며,
K는 extends로 인한, 분산성 원칙에 따라 그 유니온 타입이 분리된 하나 하나의 타입을 의미한다고 해석하면 된다.

K=T 이기 때문에 타입 파라미터까지만 봤을 때는 K는 유니온이지만, 그 이후의 분기문으로 인해 앞과 뒤의 K는 문맥 상 의미가 다르다.

 

type Result1 = UnionToArray<1>;                    // [1]
type Result2 = UnionToArray<true|false>;           // [true] | [false]
type Result3 = UnionToArray<1|2|3>;                // [1] | [2] | [3]

각 타입의 우측 주석은 해당 타입의 연산 결과이다.

 

여기까지를 순열 (Permutation) type에 적용하기

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

이걸 Permutation type에 대입하면, 이제 이 시점에서 Permutation은 유니온 중 1개를 선택하여 그 타입과, 나머지 유니온으로 구성된 타입을 의미하게 된다.
즉, Permutation<1 | 2 | 3>의 결과는 [1, 2 | 3], [2, 1 | 3], [3, 1 | 2]이 된다.

풀어 쓴 한 타입과, 그리고 그 타입을 제외하면 나머지 유니온 타입이라면 그 유니온 타입에 대해서 동일한 일을 반복하면 되지 않을까?

 

마지막, 재귀적으로 풀기

이제 그 뒷 부분인데, 순열은 1개를 고른 후 "그 나머지의 순열"로 같이 정의될 수 있으니 일단 재귀적인 타입인 것을 알 수 있다.
한 개를 고른 후, 나머지를 다시 순열로 만드는 것은 어떻게 해야 할까?
답은 간단하다.
다시 Permutation으로 감싸면 된다.

 

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

설명을 따라오면 쉽게 이해할 수 있지만 그냥 도전하면 탈모가 올 정도의 난이도다.

이는 이 타입의 구현이 복잡한 것이 아니라 아직 타입스크립트의 문법이 익숙하지 않아서니 낙담하지 말자. :)