Inverting Map of Map in functional way
Tags: fpts, typescript, haskell, functional
Published: 2021-07-25 15:23:02

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

(typescript)
```typescript
Map<A, Map<B, T>>
// to
Map<B, Map<A, T>>
```

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

## Table of Contents
* [Motivation](#motivation)
* [Applicative Map?](#applicativemap)
* [Combining Monoidal Operations](#mapasmonoid)
* [Implementation](#implementation)

## Motivation <a name="motivation"></a>

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)
```typescript
Map<A, Map<B, T[]>>
```

(haskell)
```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.

## Applicative Map? <a name="applicativemap"></a>

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.

## Combining Monoidal Operations <a name="mapasmonoid"></a>

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 <a name="implementation"></a>

(Haskell)
```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)
```typescript

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