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