타입스크립트로 순열 만들기

동기

알고리즘 문제를 풀다보면 순열을 만들어야 할 때가 있다.

자바스크립트로 순열을 만드는 코드는 다음과 같다

const getPermutaion = (arr, n) => {
  if(n === 1) return arr.map(el => [el]);
  const result = [];
  
  arr.forEach((fixed, idx, origin) => {
    const rest = [ ...origin.slice(0, idx), ...origin.slice(idx+1) ];
    const perms = getPermutation(rest, n-1);
    const attached = perms.map(perm => [fixed, ...perm]);
    result.push(...attached);
  });
  
  return result;
}

타입스크립트로도 원소들이 주어질 때에 만들어지는 순열을 타입으로 표현할 수 있을까??

문제를 직접 첨부한다.

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

유니온 타입으로 주어지는 원소들을 순열로 표현해주는 것이 문제이다.

타입스크립트가 익숙하지 않다면 풀이를 떠올리기 쉽지않다.

한참 고민하다가 솔루션을 참고하여 접근법을 알게되었고, 풀이 내에 알아두면 좋은 지식들이 있어 공유하려고 한다.

• 정답

  type Permutation<Elem, P = Elem> = 
          [Elem] extends [never]
              ? []
              : Elem extends Elem
                  ? [Elem, ...Permutation<Exclude<P, Elem>>]
                  : never

이 문제를 풀기 위해 알아야할 개념은 2가지가 있다.

• 조건부 타입과 분산 조건부 타입
• never 타입이 분산 조건부 타입에서 작동하는 방식.

조건부 타입

타입스크립트의 조건부 타입은 삼항 연산자의 동작과 비슷하다.

T extends U ? X : Y

와 같은 형식으로 사용한다.

T가 U에 포함되는 관계라면 타입이 X로 결정되고 그렇지 않다면 타입은 Y로 결정된다.

일반적으로 요렇게 쓸 수 있다.

type Test<T> =  T extends string ? "string" : "number"

바로 분산 조건부타입(Distributive conditional type)으로 넘어가보자.

T extends U ? X : Y

여기서 T가 유니온타입이라면 어떻게 계산될까?

type T = 1 | 2 | null
type Test<T> = T extends number ? T : "not a number"

위와 같은 식의 계산결과를 직접 돌려보면 다음과 같다.

집합에서 분배법칙이 적용되듯이 유니온에서 각각의 타입에 조건부타입이 적용되는 것을 볼 수 있다.

실제로 우리가 이미 사용하고 있는 유틸리티 타입에는 이런 분산 조건부타입이 활용되고 있다

해당 유틸리티 타입은 직접 작성한 것이 아니라 타입스크립트에 이미 정의된 것을 가져온 것이다.

순열 문제를 푸는데 필요한 Exclude 타입만 대표로 살펴보자.

타입 T 중에 제외하고 싶은 타입 U가 있는 경우에 사용한다.

T가 유니온 타입으로 쓰인다면 각 타입이 U에 포함되는 관계인지 검사하고 포함관계에 있다면 never를 리턴한다.

type T = 1 | 2 | null
type Test = Exclude<T, null> // 1 | 2

분산 조건부 타입 내에서의 never의 동작

이제 조금 더 나아가서 분산 조건부 타입 내에서 never가 어떻게 동작하는지 알아보자.

방금 전에 사용한 예시를 살짝 변형해보았다.

type T = 1 | 2 | never
type Test<T> = T extends T ? T : never
type Result = Test<T> // 1 | 2

이제 유니온 타입에 null이 아닌 never가 포함되도록 만들었다.

이후 2번째라인에서는 T extends T를 검사한다.

이걸 굳이 왜 검사하나 싶을수도 있는데 조건부타입을 만들어주기 위한 트릭 정도로 생각할 수 있다.

이를 통해 유니온에 속한 각 원소가 유니온타입 내에 포함되는지 검사한다.

당연히 집합내의 원소는 집합에 포함되기 때문에 type Result = 1 | 2 | never 를 기대한다.

하지만 결과는 type Result = 1 | 2 이다.

이걸로 알 수 있는 타입스크립트의 중요한 동작방식이 있다.

유니온 타입 내에서 never가 조건부타입을 통해 검사될 때, never를 없는 것으로 판단한다.

공집합 정도의 개념으로 생각할 수 있을 것 같다.

검사단계에서 스킵되기 때문에 결과에도 반영되지 않는 것이다.

순열만들기

이제 필요한 개념들을 다 알아보았으니 순열을 만들어보자.

type Permutation<Elem, P = Elem> = 
        [Elem] extends [never]
            ? []
            : Elem extends Elem
                ? [Elem, ...Permutation<Exclude<P, Elem>>]
                : never

위에 있던 정답을 가지고 왔다.

Elem = 1 | 2 |3 으로 생각하고,

Elem extends Elem으로 진행되는 부분부터 살펴보자.

→ 각 타입(1, 2, 3)은 조건부타입에 걸린다.

→ 1을 예시로 들 경우, [1, ...Permutation<Exclude<P, 1>>] 이 된다.

→ 이후 Permutation<2 | 3, P>가 진행될 것이다.

한 식이 어디까지 재귀적으로 진행될까?

Elem의 타입이 never가 될 때까지 진행될 것이다. ( 1 | 2 | 3
→ [1] + ...Permutation<2 | 3>
→ [1, 2] + ...Permutation<3>
→ [1, 2, 3] + ...Permutation<never>와 같은 순서로 진행)

그러면 Elem이 never 타입인지 검사하여 재귀를 종료해줘야한다.

그런데 Elem extends never 와 같은 방식으로는 검사할 수 없다.

위에서 살펴본 바와 같이 Elem이 never 타입이라면 애초에 조건부 타입에 걸리지 않는다.

타입이 never인지 검사하려면 어떻게 해줘야할까?

가장 쉽게 사용할 수 있는 방법은 타입을 튜플에 넣어 검사하는 방법이다.

[T] extends [never] 와 같은 방식으로 타입이 무시당하지 않고 조건부타입에 걸리도록 할 수 있다.

위의 방식을 종합하여 순열을 구할 수 있다.

정리

타입스크립트를 실전에서 사용하면서 순열만들기처럼 복잡하게 타입을 구현해본 경험은 아직 없다.
그래도 조건부 타입에 대해 자세히 알 수 있어서 좋은 기회였다. 실제 유틸리티 타입에서도 사용되고 있는 개념인만큼 잘 알아두고 사용하면 이후 복잡한 구현에 유용하게 사용할 수 있을 것 같다.

레퍼런스

296 - Permutation (with explanations) · Issue #614 · type-challenges/type-challenges

TypeScript: Conditional type array of union type distribution

타입스크립트 핸드북