DEV Community

Ingun 전인건
Ingun 전인건

Posted on

3 2

Inverting Map of Map in functional way

This post is about implementing a function for inverting Map of Maps, that is,

(typescript)

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

I’ll be using Haskell and Typescript throughout the post and show my best attempt in the end.

Table of Contents

Motivation

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 Ts by A thereby I can process all the Ts 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[]>>
Enter fullscreen mode Exit fullscreen mode

(haskell)

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

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
Enter fullscreen mode Exit fullscreen mode

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.

Applicative Map?

At first I thought about conforming Map<B, _> to Applicative then just sequenceing 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.

Combining Monoidal Operations

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.

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

Heroku

Simplify your DevOps and maximize your time.

Since 2007, Heroku has been the go-to platform for developers as it monitors uptime, performance, and infrastructure concerns, allowing you to focus on writing code.

Learn More

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay