Questionably useful Typescript: Permutations

Knowing how exceptionally nerd snipable I am, a colleague recently posed a challenge to me:

Suppose I have a union of five literal strings, like 'A' | 'B' | 'C' | 'D' | 'E'. How would I design a type that represents an array of exactly three of these with no duplicates?

That is, how do I allow ['A', 'B', 'C'] while disallowing ['A', 'B', 'A']?

This is certainly a tricky one, so let’s begin by getting some of the easy pieces out of the way.

Suppose I loosen the restriction and decide to allow repetition. This now becomes very easy: I can just declare a tuple with three elements of the same type.

type letter = 'A' | 'B' | 'C' | 'D' | 'E';
type allowRepetition = [letter, letter, letter];
function testHardCodedType() {
  // This one should always be permitted
  const permutationWithoutRepetition: allowRepetition =
    ['A', 'B', 'C'];
  // We'd like this one to eventually emit an error
  const permutationWithRepetition: allowRepetition =
    ['A', 'B', 'A'];
}
What the compiler sees
The type alias…
is evaluated as…
letter
"A" | "B" | "C" | "D" | "E"
allowRepetition
[letter, letter, letter]

But the notion that we’re trying to build a tuple with three elements seems a bit incidental to the problem, and if I wanted permutations of, say, 10 or even 20 elements, this could get cumbersome pretty quickly. To better reflect this, we could borrow a technique from my last Typescript blog post and allow the length of our tuple to be expressed as a type parameter.¹

type tupleWithLength<
  element,
  length extends number,
  accumulator extends element[] = []
> =
  length extends accumulator['length'] ?
    accumulator :
    tupleWithLength<element, length, [element, ...accumulator]>;
type longerPermutation = tupleWithLength<letter, 4>;
What the compiler sees
The type alias…
is evaluated as…
longerPermutation
[letter, letter, letter, letter]

However, because each element of these tuples is its own union, it’s difficult to make much more progress than this with the current approach. We need some way to lift the “union-ness” out of the elements up to the level of the tuple. Or more concisely: we need a union of tuples, not a tuple of unions.

Building a union of single element tuples

Starting with a single element, we can make use of the distributive property of conditional types : if we apply a conditional type to a union, Typescript will apply the condition to each member of the union and then construct a union of the results.

In this case though, we don’t actually care about the condition itself, so we can just use on that succeeds with anything at all².

type unionToSingletonTuple<union> = union extends unknown ? [union] : never;
type singletonTuple = unionToSingletonTuple<letter>;
What the compiler sees
The type alias…
is evaluated as…
singletonTuple
["A"] | ["B"] | ["C"] | ["D"] | ["E"]

Building multi-element tuples

Now that we can do this for a single element, we can split long tuples by recursively applying the transformation to each element!

type tupleToUnion<tuple> =
  tuple extends [] ?
    tuple :
    tuple extends [infer first, ...infer rest] ?
      [...unionToSingletonTuple<first>, ...tupleToUnion<rest>] :
      never;
type multiElementTupleUnion = tupleToUnion<tupleWithLength<'A' | 'B', 2>>;
What the compiler sees
The type alias…
is evaluated as…
multiElementTupleUnion
["A", "A"] | ["A", "B"] | ["B", "A"] | ["B", "B"]

Excluding repetitions

Once we have a union of tuples containing each possible permutation (including those with duplicates), our task becomes filtering this down to just those tuples that have no duplicate elements.

Here again, the distributive property of conditional types works in our favor. If we can supply a condition that inspects a single tuple and evaluates to

• itself when there are no repetitions,

• otherwise, never

Then applying it to a union of tuples will leave us with just those that contain no duplicate elements!

This still leaves us with a tricky problem: how do we determine whether a particular tuple has duplicate elements?

While there are a couple of ways one could go about this, the one that I find most clear makes use of indexed access types ; specifically, if we have an array—including tuples—we can get a union of all the possible element types by applying the [number] indexer, like so:

type tupleElements = ['A', 'B'][number];
type emptyTupleElements = [][number];
What the compiler sees
The type alias…
is evaluated as…
tupleElements
"A" | "B"
emptyTupleElements
never

We can use this to perform a sort of proof by induction:

• An empty array has no duplicate elements

• For a longer array, split the first element away from the rest of it

  • There’s a repetition if the type of first overlaps with rest[number]

  • Otherwise, check whether there’s a repetition in rest

Here’s what that looks like as a type:

type excludeTuplesWithRepetition<tuple> =
  tuple extends [] ?
    [] :
    tuple extends [infer first, ...infer rest] ?
      first extends rest[number] ?
        never :
        [first ...excludeTuplesWithRepetition<rest>] :
      never;
type excluded = excludeTuplesWithRepetition<
  | ['A', 'A']
  | ['A', 'B']
  | ['A', 'B', 'A']
  | ['A', 'B', 'C']
>;
What the compiler sees
The type alias…
is evaluated as…
excluded
["A", "B", "C"] | ["A", "B"]

Putting all the pieces together

The general solution to the original problem can now be written as the composition of each of the tools we’ve built up to this point:

type permutationsWithoutRepetition<union, length extends number> =
  excludeTuplesWithRepetition<
    tupleToUnion<
      tupleWithLength<union, length>>>;
type solution = permutationsWithoutRepetition<letter, 3>;
What the compiler sees
The type alias…
is evaluated as…
solution
["A", "B", "C"] | ["A", "B", "D"] | ["A", "B", "E"] | ["A", "C", "B"] | ["A", "C", "D"] | ["A", "C", "E"] | ["A", "D", "B"] | ["A", "D", "C"] | ["A", "D", "E"] | ["A", "E", "B"] | ["A", "E", "C"] | ["A", "E", "D"] | ["B", "A", "C"] | ["B", "A", "D"] | ["B", "A", "E"] | ["B", "C", "A"] | ["B", "C", "D"] | ["B", "C", "E"] | ["B", "D", "A"] | ["B", "D", "C"] | ["B", "D", "E"] | ["B", "E", "A"] | ["B", "E", "C"] | ["B", "E", "D"] | ["C", "A", "B"] | ["C", "B", "A"] | ["C", "A", "D"] | ["C", "A", "E"] | ["C", "B", "D"] | ["C", "B", "E"] | ["C", "D", "A"] | ["C", "D", "B"] | ["C", "D", "E"] | ["C", "E", "A"] | ["C", "E", "B"] | ["C", "E", "D"] | ["D", "A", "B"] | ["D", "B", "A"] | ["D", "B", "C"] | ["D", "A", "C"] | ["D", "A", "E"] | ["D", "B", "E"] | ["D", "C", "A"] | ["D", "C", "B"] | ["D", "C", "E"] | ["D", "E", "A"] | ["D", "E", "B"] | ["D", "E", "C"] | ["E", "A", "B"] | ["E", "B", "A"] | ["E", "B", "C"] | ["E", "A", "C"] | ["E", "A", "D"] | ["E", "B", "D"] | ["E", "C", "A"] | ["E", "C", "B"] | ["E", "C", "D"] | ["E", "D", "A"] | ["E", "D", "B"] | ["E", "D", "C"]

We can even rewrite our original test function in terms of this type to verify that it actually works as intended!

function testGeneratedType() {
  // This one should will still be permitted
  const permutationWithoutRepetition: solution = ['A', 'B', 'C'];
  // This one will emit an error
  const permutationWithRepetition: solution = ['A', 'B', 'A'];
}
ts(2322): Type '["A", "B", "A"]' is not assignable to type 'solution'.
  Type '["A", "B", "A"]' is not assignable to type '["A", "B", "C"] | ["A", "B", "D"] | ["A", "B", "E"]'.
    Type '["A", "B", "A"]' is not assignable to type '["A", "B", "C"]'.
      Type at position 2 in source is not compatible with type at position 2 in target.
        Type '"A"' is not assignable to type '"C"'.

Why this is questionably useful

While the idea of representing permutations as a type seems powerful and exciting, their utility in practice is hampered by limitations³ of the type system as a whole.

To take one example, consider the case of transposing two elements of a permutation. That’s something that should obviously result in another permutation, right?

…Right?

The compiler says “no”.

function transposeElements(permutation: solution): solution {
  const [first, second, third] = permutation;
  return [second, first, third];
}
ts(2322): Type '["A" | "B" | "C" | "D" | "E", "A" | "B" | "C" | "D" | "E", "A" | "B" | "C" | "D" | "E"]' is not assignable to type 'solution'.
  Type '["A" | "B" | "C" | "D" | "E", "A" | "B" | "C" | "D" | "E", "A" | "B" | "C" | "D" | "E"]' is not assignable to type '["A", "B", "C"]'.
    Type at position 0 in source is not compatible with type at position 0 in target.
      Type '"A" | "B" | "C" | "D" | "E"' is not assignable to type '"A"'.
        Type '"B"' is not assignable to type '"A"'.

If we dig into the detailed output of this error message, we see that when dealing with the union as a whole, Typescript is unable to understand the relationships between the types of the individual elements, and doing something as simple as swapping two of them is impossible for the compiler to verify. The only way to write a method like this in a way that the compiler can verify would be write out the code for all sixty variations of this permutation, and that gets unpalatable really quickly.

It turns out that the only general case where Typescript can verify the correctness of any particular permutation construction is when the whole permutation is when it’s hard coded, as they were in testGeneratedType.

This means that this technique could be useful in applications that contain a lot of handwritten configuration and needs to be constrained in this way, but for nearly every other case, you’re likely to be better off writing robust runtime checks.

But now you know a cool Typescript party trick, and some of the techniques we used along the way can be used for much more practical effects!