함수형으로 Map 의 Map 뒤집기

이 글은 임의의 서로다른 키 값을 가진 Map 의 Map 을 뒤집는 함수를 함수형으로 구현하는것에 관한 글이에요.

Map<A, Map<B, T>>
// to
Map<B, Map<A, T>>

하스켈과 타입스크립트를 사용 할것이며 구현한 코드는 마지막에 첨부할게요.

동기

최근에 굉장히 많은 수의 타입 T 의 인스턴스를 다룰 일이 있었어요. 워낙 많다보니 퍼포먼스향상의 목적으로 어떤 기준으로 그룹화를 해야 했죠. 예를하나 들어보면 T 는 리소스 A 를 사용하는데, T 인스턴스들을 같은 리소스를 공유하는 것들끼리 그룹화를 함으로써 어떤 리소스 A가 할당되었을때 그 리소스를 사용하는 모든 T들을 한번에 처리할 수 있게끔 하는것이죠.

제 경우 동시에 고려해야하는 A와 B 두가지 기준이 있었어요. 그래서 다음과같은 자료구조를 만들게 되었어요.

(typescript)

Map<A, Map<B, T[]>>

(haskell)

Map A (Map B [T])

문제는 어떤 경우에는 이 자료가 내부의 Map 과 외부의 Map이 뒤바뀐 Map<B, Map<A, T[]>> 로 표현이 되어야 한다는 점이었어요.

물론 다음과같이 imperative 한 스타일로 구현할 수 있었지만

(pseudo imperative code)

// boring imperative code …
func invertMap(ABTs: Map<A, Map<B, T[]>>):
  BATs = new Map<B, Map<A, T[]>>
  for (a, BTs) of ABTs:
    for (b, Ts) of BTs:
      if BATs has no key b then
        BATs[b] = new Map<A, T[]>
        BATs[b][a] = Ts
      else
        if BATs[b] has no key a then
          BATs[b][a] = Ts
        else
          BATs[b][a].add Ts
  return BATs

하지만 최선의 방법이 아니라는것을 알았죠. 왜냐하면 두 자료구조는 분명 Algebra 적으로 같은 타입이므로 서로의 타입으로 변환할 수 있는 더 (수학적으로)자연스러운 방법이 있을것만 같았어요.

Applicative Map?

처음에는 Map<B, _> 이 Applicative 를 만족할 수 만 있다면 그냥 sequence로 처리할 수 있을것만 같았어요. 왜냐면 Map은 이미 Traversable 을 만족하기 때문이었죠. 하지만 금방 Map 으로는 pure (혹은 of), 그리고 ap (혹은 <*>, liftA) 을 구현이 불가능하다는 점을 깨달았죠. 간단히 생각해봐도 Identity 법칙을 만족하는 함수의 Map 이 존재할 리가 없잖아요?

그래서 Applicative Map 을 만드는건 포기했습니다.

Monoidal 연산의 조합

그다음 초점을 맞춘건 위 Imperative 한 구현을 보면 모든 프로세스는 단순히 하위 타입들의 Monoidal 연산의 조합이라는 점이 분명히 드러난 다는 점이었어요. 보면 텅빈 Map을 만들고, T 의 리스트를 이어붙이고, 궁극적으로 이 모두를 사용해서 Map<B, Map<A, T>>의 Monoidal 연산을 구현하고 있었죠.

이 점을 관찰하고 다음과같은 함수형 구현을 하게 되었습니다.

구현

(Haskell)

invertMap :: (Monoid t, Ord a, Ord b) => Map a (Map b t) -> Map b (Map a t)
invertMap = foldr (unionWith mappend) empty . mapWithKey (fmap . singleton)

(Typescript, fp-ts)

export function invertMap<KA, KB, T>(
  kaOrd: Eq<KA>,
  kbOrd: Eq<KB>,
  monT: Monoid<T>
) {
  const monAT = map.getMonoid(kaOrd, monT);
  const monBAT = map.getMonoid(kbOrd, monAT);
  return (mm: Map<KA, Map<KB, T>>) =>
    getFoldableWithIndex(kaOrd).foldMapWithIndex(monBAT)(mm, (a, bt) =>
      pipe(
        bt,
        map.map((t) => new Map<KA, T>().set(a, t))
      )
    );
}