기능적 방식으로 지도의 지도 반전
(타이프스크립트)
Map<A, Map<B, T>>
// to
Map<B, Map<A, T>>
포스트 내내 Haskell과 Typescript를 사용하고 마지막에 최선을 다하는 모습을 보여드리겠습니다.
목차
동기 부여
Recently I got to deal with lots of instances of a type T
. Since there were so many of them, I had to group them by some criterion for performance reasons. For example, T
uses resource A
so I group T
s by A
thereby I can process all the T
s that share the same A
at once when it is allocated.
In my case there were two criteria, A
and B
, that I had to take into account simultaneously so naturaly I got to build a data structure of
(typescript)
Map<A, Map<B, T[]>>
(haskell)
Map A (Map B [T])
The problem was that in some cases it needed to be expressed in the form of Map<B, Map<A, T[]>>
which is alteration of switching the outter Map’s Key and inner Map’s Key.
Of course I could just implement it imperatively something like this …
(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
But I thought I could do better. They were the algebraically same data structure therefore there must have been a natural way of transforming into each other. I only needed to find them.
응용 지도?
At first I thought about conforming Map<B, _>
to Applicative then just sequence
ing it. It was possible because Map is Traversable. But soon I found Map couldn’t conform to Applicative because there is simply no way to implement pure
(or of
, if you will) nor ap
(or <*>
, liftA
, if you will). I mean how are you going to construct a Map of functions that satisfies Identity law?!
So I gave up on Applicative Map.
모노 연산 결합
I got thinking that it was evident in the imperative version of implementation above that the whole process is just combination of Monoidal operations: creating empty Map, concatenating list of Ts and ultimately combining all to define monoidal operation on Map<B, Map<A, T>>
.
This observation led me to this functional implementation.
구현
(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))
)
);
}
Reference
이 문제에 관하여(기능적 방식으로 지도의 지도 반전), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/ingun37/functional-gossip-inverting-map-of-map-3kpb텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)