이 글은 임의의 서로다른 키 값을 가진 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))
)
);
}
Top comments (0)