DEV Community

Ingun 전인건
Ingun 전인건

Posted on

2 2

함수형으로 Map 의 Map 뒤집기

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

Map<A, Map<B, T>>
// to
Map<B, Map<A, T>>
Enter fullscreen mode Exit fullscreen mode

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

목차

동기

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

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

(typescript)

Map<A, Map<B, T[]>>
Enter fullscreen mode Exit fullscreen mode

(haskell)

Map A (Map B [T])
Enter fullscreen mode Exit fullscreen mode

문제는 어떤 경우에는 이 자료가 내부의 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
Enter fullscreen mode Exit fullscreen mode

하지만 최선의 방법이 아니라는것을 알았죠. 왜냐하면 두 자료구조는 분명 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)
Enter fullscreen mode Exit fullscreen mode

(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))
      )
    );
}
Enter fullscreen mode Exit fullscreen mode

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more