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
Advertisement
Answer
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.