기능적 방식으로 지도의 지도 반전

이 포스트는 Map of Maps를 반전시키는 함수를 구현하는 것, 즉,

(타이프스크립트)

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


포스트 내내 Haskell과 Typescript를 사용하고 마지막에 최선을 다하는 모습을 보여드리겠습니다.

목차


  • Motivation
  • Applicative Map?
  • Combining Monoidal Operations
  • Implementation

  • 동기 부여

    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))
          )
        );
    }
    

    좋은 웹페이지 즐겨찾기