BidirectionalMap.md

Bidirectional Map

The problem

Imagine you're working on a platform that manages some kind of orders. These orders are managed in different ways depending on its status. You get all possible statuses from server, but they are represented as an array of numbers (IDs).

{
  "statuses": [1, 2, 3, 4, 5, 6, 7]
}

In order to make it easier to implement business logic which is based on these statuses you would probably want to map them to some more meaningful type.

Since we know what each status (ID) mean, we can create a custom type which will represent a more readable format:

type Status = 'New' | 'Open' | 'Approved' | 'InProgress' | 'Completed' | 'Cancelled' | 'Rejected';

Now we can write a simple switch-case function which will map status IDs to our Status type:

const toStatus = (id: 1 | 2 | 3| 4 | 5 | 6 | 7): Status => {
  switch (id) {
    case 1:
      return 'New';
    case 2:
      return 'Open';
    case 3:
      return 'Approved';
    case 4:
      return 'InProgress';
    case 5:
      return 'Completed';
    case 6:
      return 'Cancelled';
    case 7:
      return 'Rejected';
  }
};

We can now use this function when getting data from server.

All right, we can now deal with business logic in a much easier and readable way! But at some point we will need to send that status back to server. How are we going to handle this? Well, the easiest solution is to write another function which will do the opposite mapping of our Status type to status IDs:

const toStatusId = (status: Status): 1 | 2 | 3 | 4 | 5 | 6 | 7 => {
  switch (id) {
    case 'New':
      return 1;
    case 'Open':
      return 2;
    case 'Approved':
      return 3;
    case 'InProgress':
      return 4;
    case 'Completed':
      return 5;
    case 'Cancelled':
      return 6
    case 'Rejected':
      return 7;
  }
}

Okay, now, before sending data to server, we will map status back to its initial representation.

The problem is - scalability and repeatability.

What if you have more than 20 statuses? What if you have not only place, where some data from server needs to be mapped? Is it convenient to write such functions each and every time?

The solution

Let's treat out statuses as a set of unique values. Our goal is to map it to some other set of unique values. We can also conclude that those sets will have the same length.

So we need some kind of a Map which can be queried in both directions - by key and by value... and it's called BidirectionalMap!

Introduction

A bidirectional map is a model from computer science where key – value pairs have a bijective 1-1 relationship between the keys and the values. This allows us not only to query by key and get a value, but also to query by the value and get the key.

So we need some kind of a map, where we can query by 'Approved' status and get 3 back and vice versa.

BidirectionalMap consists of two forms - forward (original map) and reverse (map, where keys are represented as values and values are represented as keys).

Let's first of all create an original map where keys represent a set of Statuses that we created ('New' | 'Open'...) and values represent status IDs (1 | 2 | 3...).

const StatusMap = {
  New: 1,
  Open: 2,
  Approved: 3,
  InProgress: 4,
  Completed: 5,
  Cancelled: 6,
  Rejected: 7,
};

Types

Let's think about types for a moment.

How can we represent a bidirectional map using TypeScipt type system? First of all, I would use Mapped types to create a generic Reverse<T> type which accepts some other type as a parameter and "swaps" keys and values in it. We should also add a type constraint for a type parameter which will check whether provided type is a Record where both keys and values are of type string | number:

type Mappable = Record<string | number, string | number>;

export type Reverse<T> = {
  readonly [K in T[keyof T]]: keyof T;
};

Okay, now we can create a type that will represent a BidirectionalMap itself. This one is easy:

export type BidirectionalMap<T extends Mappable> = {
  forward: T;
  reverse: Reverse<T>;
};

And one extra utility type, that will let us get a type of Values from a map:

export type Values<T extends Mappable> = keyof Reverse<T>;

There is no need to create a utility type for Keys since we can just use keyof T.

Implementation

Now let's think about a function that will reverse some map for us. Its type signature will look like this:

declare function reverse<T extends Mappable>(m: T): Reverse<T>

All we have to do is to map m to an array of entries (array of keys and values), than swap keys and values in each entry and create a record from those entries.

We will now create a couple of utility functions that we will later use inside of reverse Implementation:

function entries<K extends string | number, A>(record: Record<K, A>): [K, A][] {
  return Object.entries(record) as [K, A][];
}

function fromEntries<K extends string | number, A>(ens: [K, A][]): Record<K, A> {
  return Object.fromEntries(ens) as Record<K, A>;
}

const record = {
  entries,
  fromEntries,
}

Okay, we have everything we need, let's do it:

(I'm using an fp-ts library in almost all of my projects, that's where pipe and array.map come from).

function reverse<K extends string | number, V extends string | number, T extends Record<K, V>>(
  bm: T,
): Reverse<T> {
  return pipe(bm, record.entries, array.map(tuple.swap), record.fromEntries);
}

As you may have noticed, I had to adjust reverse type signature a bit. I've added K and V type parameters for better type inference, otherwise TypeScript would not be able to infer types as precise as we need.

Last thing that is left is a "constuctor" function that will make a BidirectionalMap for us. And again, it's as easy as BidirectionalMap type is:

function make<K extends string | number, V extends string | number, T extends Record<K, V>>(
  bm: T,
): BidirectionalMap<T> {
  return {
    forward: bm,
    reverse: reverse(bm),
  };
}

export const bidirectionalMap = {
  make,
};

That's it! Now let's try to use it!

Example

That's an example map that we want to create a BidirectionalMap from:

const StatusMap = {
  New: 1,
  Open: 2,
  Approved: 3,
  InProgress: 4,
  Completed: 5,
  Cancelled: 6,
  Rejected: 7,
};

const StatusBiMap = bidirectionalMap.make(StatusMap);

// Infers type as 1
// It knows exactly what type of value we will get
const value = StatusBiMap.forward['New'];

// Infers type as 'New' | 'Open' | 'Appoved'...
// When we query by value TypeScript cannot tell which type of key we will get,
// but I think it's fine anyway
const key = StatusBiMap.reverse[1];

Okay, now coming back to our original problem...

Our toStatus function will now look like this:

const toStatus = (status: Values<typeof StatusMap>) => StatusMap.reverse[status];

How do you like it?

And toStatusId will look like this:

const toStatusId = (status: keyof StatusMap) => StatusMap.forward[status];

Only one line of code... isn't that beautiful?

Bonus

I usually use io-ts library for runtime validation and that's where this solution really shines in my opinion.

We can define a Decoder that will decode status IDs and then map them to our readable status format using BidirectionalMap:

import * as D from 'io-ts/Decoder';

const StatusDecoder = pipe(
  D.literal(1, 2, 3, 4, 5, 6, 7),
  D.map((status) => StatusBiMap.reverse[status])
);

// 'New' | 'Open' | 'Approved'...
type Status = D.TypeOf<typeof StatusDecoder>;

And we can also define an Encoder that will do the oppsoite thing which is useful when sending data to server:

const StatusEncoder = {
  encode: (status: Status) => StatusBiMap.forward[status]
};

And the last one - we can combine both Decoder and Encoder into a Codec:

import * as C from 'io-ts/Codec';

const Status = C.make(StatusDecoder, StatusEncoder);

And I think it's beautiful!