Type-level Catalan function in TypeScript

Question

Consider the following Catalan function in JavaScript.

class Pair {
    constructor(fst, snd) {
        this.fst = fst;
        this.snd = snd;
    }
}

const catalan = (x, xs) => {
    if (xs.length === 0) return [x];
    const result = [];
    for (let i = 0; i < xs.length; i++) {
        const ys = catalan(x, xs.slice(0, i));
        const zs = catalan(xs[i], xs.slice(i + 1));
        for (const y of ys) for (const z of zs) result.push(new Pair(y, z));
    }
    return result;
};

const show = (x) => x instanceof Pair
    ? `(${show(x.fst)} <> ${show(x.snd)})`
    : JSON.stringify(x);

const log = (x) => console.log(x);

catalan(1, []).map(show).forEach(log);
catalan(1, [2]).map(show).forEach(log);
catalan(1, [2, 3]).map(show).forEach(log);
catalan(1, [2, 3, 4]).map(show).forEach(log);

It returns all the possible ways of associating n applications of a binary operator, where n = xs.length.

I want to do something similar, but with types in TypeScript. However, I don't know how to implement the “else” branch.

class Pair<A, B> {
    constructor(public fst: A, public snd: B) {}
}

type Catalan<X, XS extends unknown[]> = XS extends []
    ? X
    : /* how to define this “else” branch? */;

type C0 = Catalan<1, []>; // 1

type C1 = Catalan<1, [2]>; // Pair<1, 2>

type C2 = Catalan<1, [2, 3]>; // Pair<1, Pair<2, 3>> | Pair<Pair<1, 2>, 3>

type C3 = Catalan<1, [2, 3, 4]>; /* Pair<1, Pair<2, Pair<3, 4>>> |
                                  * Pair<1, Pair<Pair<2, 3>, 4>> |
                                  * Pair<Pair<1, 2>, Pair<3, 4>> |
                                  * Pair<Pair<1, Pair<2, 3>>, 4> |
                                  * Pair<Pair<Pair<1, 2>, 3>, 4>
                                  * /

Any help will be greatly appreciated. By the way, I want to use this Catalan type to define the following function.

declare const flatten: <X, XS extends unknown[]>(
    x: Catalan<X, XS>
) => [X, ...XS];

Here's how the flatten function is implemented in JavaScript.

class Pair {
    constructor(fst, snd) {
        this.fst = fst;
        this.snd = snd;
    }
}

const catalan = (x, xs) => {
    if (xs.length === 0) return [x];
    const result = [];
    for (let i = 0; i < xs.length; i++) {
        const ys = catalan(x, xs.slice(0, i));
        const zs = catalan(xs[i], xs.slice(i + 1));
        for (const y of ys) for (const z of zs) result.push(new Pair(y, z));
    }
    return result;
};

const flatten = (x) => x instanceof Pair
    ? [...flatten(x.fst), ...flatten(x.snd)]
    : [x];

const log = (x) => console.log(JSON.stringify(x));

catalan(1, []).map(flatten).forEach(log);
catalan(1, [2]).map(flatten).forEach(log);
catalan(1, [2, 3]).map(flatten).forEach(log);
catalan(1, [2, 3, 4]).map(flatten).forEach(log);

---

Edit: If it helps, here's an implementation of the value-level catalan function in Haskell.

import Data.List (inits, tails)

data Catalan a = Catalan a :<>: Catalan a | Lift a deriving Show

split :: [a] -> [([a], [a])]
split = init . (zipWith (,) <$> inits <*> tails)

catalan :: a -> [a] -> [Catalan a]
catalan x [] = [Lift x]
catalan x xs = do
    (ys, z:zs) <- split xs
    y <- catalan x ys
    z <- catalan z zs
    return $ y :<>: z

main :: IO ()
main = do
    mapM_ print $ catalan 1 []
    mapM_ print $ catalan 1 [2]
    mapM_ print $ catalan 1 [2, 3]
    mapM_ print $ catalan 1 [2, 3, 4]

Here's the output of the above Haskell program.

Lift 1
Lift 1 :<>: Lift 2
Lift 1 :<>: (Lift 2 :<>: Lift 3)
(Lift 1 :<>: Lift 2) :<>: Lift 3
Lift 1 :<>: (Lift 2 :<>: (Lift 3 :<>: Lift 4))
Lift 1 :<>: ((Lift 2 :<>: Lift 3) :<>: Lift 4)
(Lift 1 :<>: Lift 2) :<>: (Lift 3 :<>: Lift 4)
(Lift 1 :<>: (Lift 2 :<>: Lift 3)) :<>: Lift 4
((Lift 1 :<>: Lift 2) :<>: Lift 3) :<>: Lift 4

Answer 1

updated may 19

Oh boy, we aren't done yet. We can make this thing even faster!

The first thing you can do is transform the extends in Catalan to only:

type Catalan<X, XS extends List> = ({
    "0": X;
    "1": Pair<X, XS[0]>;
} & {
    [_: `${number}`]: CatalanLoop<X, XS>;
})[`${XS["length"]}`];

This makes it extremely fast. It's only a lookup table now.

Then instead of big clunky loop for CatalanLoop, we can use distributive conditional types!

type CatalanLoop<X, XS extends List, K extends keyof XS & `${bigint}` = keyof XS & `${bigint}`> =
        K extends K
            ? Partition<XS, K> extends infer P
                ? P extends [List, List]
                    ? P extends P
                        ? CatalanPairs<X, XS, P, K>
                        : never
                    : never
                : never
            : never

And you'll notice a new type to help with the distributing:

type CatalanPairs<X, XS extends List, P extends [List, List], K extends keyof XS> = K extends K ? Pair<Catalan<X, P[0]>, Catalan<XS[K], P[1]>> : never;

Try this new playground to see the effects of these changes.

---

When encountering type-level problems like these, it's best to look at the original code and look for patterns, or anything that the type system can do for you.

So let's begin:

const catalan = (x, xs) => {
    if (xs.length === 0) return [x];
    const result = [];
    for (let i = 0; i < xs.length; i++) {
        const ys = catalan(x, xs.slice(0, i));
        const zs = catalan(xs[i], xs.slice(i + 1));
        for (const y of ys) for (const z of zs) result.push(new Pair(y, z));
    }
    return result;
};

First we notice that if xs is empty, then we directly return x. We make a mental note to use XS["length"] extends 0 ? X : ... later.

Then we see that this:

const ys = catalan(x, xs.slice(0, i));
const zs = catalan(xs[i], xs.slice(i + 1));

is really just partitioning xs in such a way that:

partition [1, 2, 3, 4, 5] at 3 => [1, 2, 3] [5]

In other words, we split the tuple at index 3 and return the two halves. This will be much faster than slicing the tuple two times individually and can be implemented without much trouble.

Finally we notice this nested loop:

for (const y of ys) for (const z of zs) result.push(new Pair(y, z));

No need for this in the type system, we can simply do:

Pair<YS, ZS>

and have it generate all the possible pairs for us from the unions.

Alright, time to get cracking away at the solution.

Recall that x is returned if xs is empty:

type Catalan<X, XS extends ReadonlyArray<unknown>> = 
  XS["length"] extends 0 ? X : 

And also when XS is only one element then we return that pair. If XS has more than one element, we enter the loop instead:

... : XS["length"] extends 1 ? Pair<X, XS[0]> : CatalanLoop<X, XS>;

Let's see the loop now:

type CatalanLoop<X, XS extends ReadonlyArray<unknown>> = {
  [K in keyof XS & `${bigint}`]: ...
}[keyof XS & `${bigint}`];

Now, what's this funny looking thing:

keyof XS & `${bigint}`

keyof XS would give us something in the form of number | "0" | "1" | "2" | "at" | "concat" | "...", but we only want the indices of XS. If we intersect keyof XS with the interpolated bigint, we get the desired "0" | "1" | "2" only.

That means this is just like the loop in the original code! We loop over each index using a mapped type.

Inside the loop body we partition XS at index K:

type CatalanLoop<X, XS extends ReadonlyArray<unknown>> = {
  [K in keyof XS & `${bigint}`]:
    Partition<XS, K> extends [infer Left, infer Right]
      ? ...
      : ...
}[keyof XS & `${bigint}`];

But we have to assert to TypeScript that our partitioning type will definitely give us tuples like this first:

    Partition<XS, K> extends [infer Left, infer Right]
      ? Left extends ReadonlyArray<unknown>
        ? Right extends ReadonlyArray<unknown>

Then we call Catalan and make our pairs:

          ? Catalan<X, Left> extends infer YS
            ? Catalan<XS[K], Right> extends infer ZS 
              ? Pair<YS, ZS>

This is doing what this original code does:

const ys = catalan(x, xs.slice(0, i));
const zs = catalan(xs[i], xs.slice(i + 1));
for (const y of ys) for (const z of zs) result.push(new Pair(y, z));

And let's close off all our ternaries/conditionals with never (because these clauses should never be reached anyways):

              : never
            : never
          : never
        : never
      : never

Finally, we need to make our partitioning type.

To do that, we need a type to increment a number. This can be done with a tuple like this:

type Increment = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33];

Increment[0]  // => 1
Increment[15] // => 16
Increment[32] // => 33

Now that we can increment a number, we define Partition:

type Partition<
  XS extends ReadonlyArray<unknown>,
  At extends string,
  Index extends number = 0,
  Left extends ReadonlyArray<unknown> = [],
> = XS extends [infer First, ...infer Rest]
    ? `${Index}` extends At
      ? [Left, Rest]
      : Partition<Rest, At, Increment[Index], [...Left, First]>
    : never

This type loops over XS until it hits At, the index to partition at. It excludes the element at At and stops, giving us [Left, Rest], the two halves. Partition is the type that replaces xs.slice(0, i) and xs.slice(i + 1).

Lastly, just for kicks, let's also make a type to mimic the original show function:

type Show<Pairs> = Pairs extends Pair<infer A, infer B> ? `(${Show<A>} <> ${Show<B>})` : `${Pairs & number}`;

And wow! It really does work!

type ShowFifth = Show<Catalan<1, [2, 3, 4, 5]>>;
// =>
// | "(1 <> (2 <> (3 <> (4 <> 5))))"
// | "(1 <> (2 <> ((3 <> 4) <> 5)))"
// | "(1 <> ((2 <> 3) <> (4 <> 5)))"
// | "(1 <> ((2 <> (3 <> 4)) <> 5))"
// | "(1 <> (((2 <> 3) <> 4) <> 5))"
// | "((1 <> 2) <> (3 <> (4 <> 5)))"
// | "((1 <> 2) <> ((3 <> 4) <> 5))"
// | "((1 <> (2 <> 3)) <> (4 <> 5))"
// | "((1 <> (2 <> (3 <> 4))) <> 5)"
// | "((1 <> ((2 <> 3) <> 4)) <> 5)"
// | "(((1 <> 2) <> 3) <> (4 <> 5))"
// | "(((1 <> 2) <> (3 <> 4)) <> 5)"
// | "(((1 <> (2 <> 3)) <> 4) <> 5)"
// | "((((1 <> 2) <> 3) <> 4) <> 5)"

To end off this little adventure, a playground where you can play around with this yourself.

Answer 2

So here is my attempt:

First of all, I am not sure if I understood the Catalan algorithm correctly. I created this type purely by looking at the examples you gave. You need to test if this works for bigger tuples as well.

Explanation

I used some utilities to solve this problem. I needed a type to splice arrays, so I used the type Splice from here.

type Absolute<T extends string | number | bigint> = T extends string
  ? T extends `-${infer R}`
    ? R
    : T
  : Absolute<`${T}`>;

type isNegative<T extends number> = `${T}` extends `-${infer _}` ? true : false;

type SliceLeft<
  Arr extends any[],
  Index extends number,
  Tail extends any[] = []
> = Tail["length"] extends Index
  ? [Tail, Arr]
  : Arr extends [infer Head, ...infer Rest]
  ? SliceLeft<Rest, Index, [...Tail, Head]>
  : [Tail, []];

type SliceRight<
  Arr extends any[],
  Index extends string,
  Tail extends any[] = []
> = `${Tail["length"]}` extends Index
  ? [Arr, Tail]
  : unknown extends Arr[0]
  ? [[], Tail]
  : Arr extends [...infer Rest, infer Last]
  ? SliceRight<Rest, Index, [Last, ...Tail]>
  : [[], Tail];

type SliceIndex<
  Arr extends any[],
  Index extends number
> = isNegative<Index> extends false
  ? SliceLeft<Arr, Index>
  : SliceRight<Arr, Absolute<Index>>;

type Slice<
  Arr extends any[],
  Start extends number = 0,
  End extends number = Arr["length"]
> = SliceIndex<SliceIndex<Arr, End>[0], SliceIndex<Arr, Start>[0]["length"]>[1];

I also needed a way to convert the indizes of the array produzed by keyof X (which are strings) back to numbers. I used this helper type:

type Indizes = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Now to the algorithm itself.

It was not clear to me why X and XS needed to be seperate things. For the first step I took X and XS and merged them into a single array.

type Catalan<X, XS extends unknown[]> = _Catalan<[X, ...XS]>

To evaluate the result I created the recursive type _Catalan which takes a tuple. The first two steps are simple. If the tuple is of length 1, return the element inside the array. If it is of length 2 ,return a Pair of the first two elements.

X["length"] extends 1 
  ? X[0]
  : X["length"] extends 2 
    ? Pair<X[0], X[1]>
    : /* ... */

The rest is a bit more complicated. My approach was to "cut" the array once at every possible index and recursively call _Catalan with both resulting sub-arrays.

[ 1 , 2 , 3 , 4 ]

    |                <- first cut here

[ 1 ] [ 2 , 3 , 4 ]

          |          <- next cut here

[ 1 ] [ 2 ] [ 3 , 4 ]

=> Pair<1, Pair<2, Pair<3,4>>

So on the highest level I iterate through each element and convert all iterations to a union with [keyof X & '${bigint}'].

{
  [I in keyof X & `${bigint}`]: /* ... */
}[keyof X & `${bigint}`]

I then convert the index to the corresponding number and also skip the first iteration since we only need to cut the array n - 1 times.

I extends keyof Indizes 
  ? Indizes[I] extends 0
    ? never
    : /* ... */
  : never

And last of all I create both sub-arrays with Slice and create a Pair of both sub-arrays by calling _Catalan with them.

Pair<_Catalan<Slice<X, 0, Indizes[I]>>, _Catalan<Slice<X, Indizes[I], X["length"]>>>

Result

The end result looks like this:

type _Catalan<X extends unknown[]> = X["length"] extends 1 
  ? X[0]
  : X["length"] extends 2 
    ? Pair<X[0], X[1]>
    : {
        [I in keyof X & `${bigint}`]: I extends keyof Indizes 
          ? Indizes[I] extends 0
            ? never
            : Indizes[I] extends number 
              ? Pair<_Catalan<Slice<X, 0, Indizes[I]>>, _Catalan<Slice<X, Indizes[I], X["length"]>>>
              : never
          : never
    }[keyof X & `${bigint}`]

type Catalan<X, XS extends unknown[]> = _Catalan<[X, ...XS]>

Usage:

class Pair<A, B> {
    constructor(public fst: A, public snd: B) {}
}

type _Catalan<X extends unknown[]> = X["length"] extends 1 
  ? X[0]
  : X["length"] extends 2 
    ? Pair<X[0], X[1]>
    : {
        [I in keyof X & `${bigint}`]: I extends keyof Indizes 
          ? Indizes[I] extends 0
            ? never
            : Indizes[I] extends number 
              ? Pair<_Catalan<Slice<X, 0, Indizes[I]>>, _Catalan<Slice<X, Indizes[I], X["length"]>>>
              : never
          : never
    }[keyof X & `${bigint}`]

type Catalan<X, XS extends unknown[]> = _Catalan<[X, ...XS]>

type C0 = Catalan<1, []>; // 1

type C1 = Catalan<1, [2]>; // Pair<1, 2>

type C2 = Catalan<1, [2, 3]>; // Pair<1, Pair<2, 3>> | Pair<Pair<1, 2>, 3>

type C3 = Catalan<1, [2, 3, 4]>; /* Pair<1, Pair<2, Pair<3, 4>>> |
                                  * Pair<1, Pair<Pair<2, 3>, 4>> |
                                  * Pair<Pair<1, 2>, Pair<3, 4>> |
                                  * Pair<Pair<1, Pair<2, 3>>, 4> |
                                  * Pair<Pair<Pair<1, 2>, 3>, 4>
                                  */

If you hover over the type C3, you will notice that it looks different from what you specified. There are only 3 top-level unions and each member will have unions inside the Pairs.

Pair<1, Pair<2, Pair<3, 4>> | Pair<Pair<2, 3>, 4>>
//instead of 
Pair<1, Pair<2, Pair<3, 4>>> | Pair<1, Pair<Pair<2, 3>, 4>>

But this is purely a visual thing and they should functionally not be different.

Some tests to validate the result:

type Test1 = Pair<1, Pair<2, Pair<3, 4>>> extends C3 ? true : false
type Test2 = Pair<1, Pair<Pair<2, 3>, 4>> extends C3 ? true : false
type Test3 = Pair<Pair<1, 2>, Pair<3, 4>> extends C3 ? true : false
type Test4 = Pair<Pair<1, Pair<2, 3>>, 4> extends C3 ? true : false
type Test5 = Pair<Pair<Pair<1, 2>, 3>, 4> extends C3 ? true : false

Playground