TypeScript 中的类型级 Catalan 函数
Type-level Catalan function in TypeScript
考虑 JavaScript.
中的以下 Catalan 函数
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);
它returns所有可能的关联方式n二元运算符的应用，其中n = xs.length.
我想做类似的事情，但使用 TypeScript 中的类型。但是，我不知道如何实现“else”分支。
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>
* /
任何帮助将不胜感激。对了，我想用这个Catalan类型来定义下面的函数
declare const flatten: <X, XS extends unknown[]>(
x: Catalan<X, XS>
) => [X, ...XS];
下面是 flatten 函数在 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);
编辑： 如果有帮助，这里是 Haskell.
中值级别 catalan 函数的实现
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]
这是上述 Haskell 程序的输出。
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
所以这是我的尝试：
首先，我不确定我是否正确理解了Catalan算法。我纯粹是通过查看您提供的示例来创建这种类型的。您需要测试这是否也适用于更大的元组。
说明
我使用了一些实用程序来解决这个问题。我需要 splice 数组的类型，所以我使用 here.
中的 Splice 类型
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];
我还需要一种方法将 keyof X 生成的数组的索引（字符串）转换回数字。我使用了这个助手类型：
type Indizes = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
现在是算法本身。
我不清楚为什么 X 和 XS 需要分开。第一步，我采用 X 和 XS 并将它们合并到一个数组中。
type Catalan<X, XS extends unknown[]> = _Catalan<[X, ...XS]>
为了评估结果，我创建了采用元组的递归类型 _Catalan。前两个步骤很简单。如果元组是 length 1，return 数组内的元素。如果是length 2 ,return a Pair 的前两个元素。
X["length"] extends 1
? X[0]
: X["length"] extends 2
? Pair<X[0], X[1]>
: /* ... */
剩下的就有点复杂了。我的方法是在每个可能的索引处“切割”数组一次，然后递归调用 _Catalan 并得到两个结果 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>>
因此，在最高级别上，我遍历每个元素并将所有迭代转换为具有 [keyof X & '${bigint}'] 的并集。
{
[I in keyof X & `${bigint}`]: /* ... */
}[keyof X & `${bigint}`]
然后我将索引转换为相应的数字并跳过第一次迭代，因为我们只需要切割数组 n - 1 次。
I extends keyof Indizes
? Indizes[I] extends 0
? never
: /* ... */
: never
最后，我用 Slice 创建了两个 sub-arrays，并通过调用 _Catalan 为两个 sub-arrays 创建了一个 Pair。
Pair<_Catalan<Slice<X, 0, Indizes[I]>>, _Catalan<Slice<X, Indizes[I], X["length"]>>>
结果
最终结果如下所示：
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]>
用法：
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>
*/
如果将鼠标悬停在类型 C3 上，您会注意到它看起来与您指定的不同。只有 3 top-level 个工会，每个成员在 Pair 内都有工会。
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>>
但这纯粹是视觉上的东西，它们在功能上应该没有什么不同。
验证结果的一些测试：
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
5 月 19 日更新
天哪，我们还没有完成。我们可以让这件事变得更快！
您可以做的第一件事是将 Catalan 中的扩展转换为仅：
type Catalan<X, XS extends List> = ({
"0": X;
"1": Pair<X, XS[0]>;
} & {
[_: `${number}`]: CatalanLoop<X, XS>;
})[`${XS["length"]}`];
这使得它非常快。现在只是查找table。
然后 CatalanLoop 我们可以使用分布式条件类型，而不是笨拙的大循环！
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
您会注意到一种有助于分发的新类型：
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;
尝试 this new playground 以查看这些更改的效果。
遇到type-level这样的问题时，最好查看原始代码并寻找模式，或者类型系统可以为您做的任何事情。
让我们开始吧：
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;
};
首先我们注意到如果xs为空，那么我们直接returnx。我们记下稍后使用 XS["length"] extends 0 ? X : ...。
然后我们看到这个：
const ys = catalan(x, xs.slice(0, i));
const zs = catalan(xs[i], xs.slice(i + 1));
实际上只是按照以下方式对 xs 进行分区：
partition [1, 2, 3, 4, 5] at 3 => [1, 2, 3] [5]
换句话说，我们将索引 3 处的元组和 return 分成两半。这比将元组单独切片两次要快得多，并且可以毫不费力地实现。
最后我们注意到这个嵌套循环：
for (const y of ys) for (const z of zs) result.push(new Pair(y, z));
在类型系统中不需要这个，我们可以简单地做：
Pair<YS, ZS>
并让它从联合中为我们生成所有可能的对。
好的，是时候开始解决问题了。
回想一下，如果 xs 为空，x 会被 return 编辑：
type Catalan<X, XS extends ReadonlyArray<unknown>> =
XS["length"] extends 0 ? X :
而且当 XS 只是一个元素时，我们 return 那对。如果 XS 有多个元素，我们进入循环：
... : XS["length"] extends 1 ? Pair<X, XS[0]> : CatalanLoop<X, XS>;
现在让我们看看循环：
type CatalanLoop<X, XS extends ReadonlyArray<unknown>> = {
[K in keyof XS & `${bigint}`]: ...
}[keyof XS & `${bigint}`];
现在，这个看起来很有趣的东西是什么：
keyof XS & `${bigint}`
keyof XS 会给我们 number | "0" | "1" | "2" | "at" | "concat" | "..." 形式的东西，但我们只想要 XS 的索引。如果我们将 keyof XS 与插值 bigint 相交，我们只会得到所需的 "0" | "1" | "2"。
这意味着这就像原始代码中的循环一样！我们使用映射类型遍历每个索引。
在循环体内，我们在索引 K:
处划分 XS
type CatalanLoop<X, XS extends ReadonlyArray<unknown>> = {
[K in keyof XS & `${bigint}`]:
Partition<XS, K> extends [infer Left, infer Right]
? ...
: ...
}[keyof XS & `${bigint}`];
但是我们必须向 TypeScript 断言我们的分区类型肯定会首先给我们这样的元组：
Partition<XS, K> extends [infer Left, infer Right]
? Left extends ReadonlyArray<unknown>
? Right extends ReadonlyArray<unknown>
然后我们调用 Catalan 并配对：
? Catalan<X, Left> extends infer YS
? Catalan<XS[K], Right> extends infer ZS
? Pair<YS, ZS>
这就是原始代码的作用：
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));
然后让我们用 never 结束所有 ternaries/conditionals（因为无论如何都不应该达到这些子句）：
: never
: never
: never
: never
: never
最后，我们需要制作分区类型。
为此，我们需要一个类型来递增数字。这可以用这样的元组来完成：
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
现在我们可以增加一个数字，我们定义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
这种类型循环遍历 XS，直到它到达 At，即要分区的索引。它排除了 At 处的元素并停止，给我们 [Left, Rest] 两半。 Partition 是替代 xs.slice(0, i) 和 xs.slice(i + 1) 的类型。
最后，为了好玩，我们也做一个类型来模仿原始的 show 函数：
type Show<Pairs> = Pairs extends Pair<infer A, infer B> ? `(${Show<A>} <> ${Show<B>})` : `${Pairs & number}`;
哇！真的有用！
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)"
要结束这个小冒险，a playground 你可以自己玩这个。
考虑 JavaScript.
中的以下 Catalan 函数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);
它returns所有可能的关联方式n二元运算符的应用，其中n = xs.length.
我想做类似的事情，但使用 TypeScript 中的类型。但是，我不知道如何实现“else”分支。
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>
* /
任何帮助将不胜感激。对了，我想用这个Catalan类型来定义下面的函数
declare const flatten: <X, XS extends unknown[]>(
x: Catalan<X, XS>
) => [X, ...XS];
下面是 flatten 函数在 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);
编辑： 如果有帮助，这里是 Haskell.
中值级别catalan 函数的实现
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]
这是上述 Haskell 程序的输出。
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
所以这是我的尝试：
首先，我不确定我是否正确理解了Catalan算法。我纯粹是通过查看您提供的示例来创建这种类型的。您需要测试这是否也适用于更大的元组。
说明
我使用了一些实用程序来解决这个问题。我需要 splice 数组的类型，所以我使用 here.
Splice 类型
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];
我还需要一种方法将 keyof X 生成的数组的索引（字符串）转换回数字。我使用了这个助手类型：
type Indizes = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
现在是算法本身。
我不清楚为什么 X 和 XS 需要分开。第一步，我采用 X 和 XS 并将它们合并到一个数组中。
type Catalan<X, XS extends unknown[]> = _Catalan<[X, ...XS]>
为了评估结果，我创建了采用元组的递归类型 _Catalan。前两个步骤很简单。如果元组是 length 1，return 数组内的元素。如果是length 2 ,return a Pair 的前两个元素。
X["length"] extends 1
? X[0]
: X["length"] extends 2
? Pair<X[0], X[1]>
: /* ... */
剩下的就有点复杂了。我的方法是在每个可能的索引处“切割”数组一次，然后递归调用 _Catalan 并得到两个结果 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>>
因此，在最高级别上，我遍历每个元素并将所有迭代转换为具有 [keyof X & '${bigint}'] 的并集。
{
[I in keyof X & `${bigint}`]: /* ... */
}[keyof X & `${bigint}`]
然后我将索引转换为相应的数字并跳过第一次迭代，因为我们只需要切割数组 n - 1 次。
I extends keyof Indizes
? Indizes[I] extends 0
? never
: /* ... */
: never
最后，我用 Slice 创建了两个 sub-arrays，并通过调用 _Catalan 为两个 sub-arrays 创建了一个 Pair。
Pair<_Catalan<Slice<X, 0, Indizes[I]>>, _Catalan<Slice<X, Indizes[I], X["length"]>>>
结果
最终结果如下所示：
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]>
用法：
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>
*/
如果将鼠标悬停在类型 C3 上，您会注意到它看起来与您指定的不同。只有 3 top-level 个工会，每个成员在 Pair 内都有工会。
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>>
但这纯粹是视觉上的东西，它们在功能上应该没有什么不同。
验证结果的一些测试：
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
5 月 19 日更新
天哪，我们还没有完成。我们可以让这件事变得更快！
您可以做的第一件事是将 Catalan 中的扩展转换为仅：
type Catalan<X, XS extends List> = ({
"0": X;
"1": Pair<X, XS[0]>;
} & {
[_: `${number}`]: CatalanLoop<X, XS>;
})[`${XS["length"]}`];
这使得它非常快。现在只是查找table。
然后 CatalanLoop 我们可以使用分布式条件类型，而不是笨拙的大循环！
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
您会注意到一种有助于分发的新类型：
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;
尝试 this new playground 以查看这些更改的效果。
遇到type-level这样的问题时，最好查看原始代码并寻找模式，或者类型系统可以为您做的任何事情。
让我们开始吧：
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;
};
首先我们注意到如果xs为空，那么我们直接returnx。我们记下稍后使用 XS["length"] extends 0 ? X : ...。
然后我们看到这个：
const ys = catalan(x, xs.slice(0, i));
const zs = catalan(xs[i], xs.slice(i + 1));
实际上只是按照以下方式对 xs 进行分区：
partition [1, 2, 3, 4, 5] at 3 => [1, 2, 3] [5]
换句话说，我们将索引 3 处的元组和 return 分成两半。这比将元组单独切片两次要快得多，并且可以毫不费力地实现。
最后我们注意到这个嵌套循环：
for (const y of ys) for (const z of zs) result.push(new Pair(y, z));
在类型系统中不需要这个，我们可以简单地做：
Pair<YS, ZS>
并让它从联合中为我们生成所有可能的对。
好的，是时候开始解决问题了。
回想一下，如果 xs 为空，x 会被 return 编辑：
type Catalan<X, XS extends ReadonlyArray<unknown>> =
XS["length"] extends 0 ? X :
而且当 XS 只是一个元素时，我们 return 那对。如果 XS 有多个元素，我们进入循环：
... : XS["length"] extends 1 ? Pair<X, XS[0]> : CatalanLoop<X, XS>;
现在让我们看看循环：
type CatalanLoop<X, XS extends ReadonlyArray<unknown>> = {
[K in keyof XS & `${bigint}`]: ...
}[keyof XS & `${bigint}`];
现在，这个看起来很有趣的东西是什么：
keyof XS & `${bigint}`
keyof XS 会给我们 number | "0" | "1" | "2" | "at" | "concat" | "..." 形式的东西，但我们只想要 XS 的索引。如果我们将 keyof XS 与插值 bigint 相交，我们只会得到所需的 "0" | "1" | "2"。
这意味着这就像原始代码中的循环一样！我们使用映射类型遍历每个索引。
在循环体内，我们在索引 K:
XS
type CatalanLoop<X, XS extends ReadonlyArray<unknown>> = {
[K in keyof XS & `${bigint}`]:
Partition<XS, K> extends [infer Left, infer Right]
? ...
: ...
}[keyof XS & `${bigint}`];
但是我们必须向 TypeScript 断言我们的分区类型肯定会首先给我们这样的元组：
Partition<XS, K> extends [infer Left, infer Right]
? Left extends ReadonlyArray<unknown>
? Right extends ReadonlyArray<unknown>
然后我们调用 Catalan 并配对：
? Catalan<X, Left> extends infer YS
? Catalan<XS[K], Right> extends infer ZS
? Pair<YS, ZS>
这就是原始代码的作用：
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));
然后让我们用 never 结束所有 ternaries/conditionals（因为无论如何都不应该达到这些子句）：
: never
: never
: never
: never
: never
最后，我们需要制作分区类型。
为此，我们需要一个类型来递增数字。这可以用这样的元组来完成：
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
现在我们可以增加一个数字，我们定义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
这种类型循环遍历 XS，直到它到达 At，即要分区的索引。它排除了 At 处的元素并停止，给我们 [Left, Rest] 两半。 Partition 是替代 xs.slice(0, i) 和 xs.slice(i + 1) 的类型。
最后，为了好玩，我们也做一个类型来模仿原始的 show 函数：
type Show<Pairs> = Pairs extends Pair<infer A, infer B> ? `(${Show<A>} <> ${Show<B>})` : `${Pairs & number}`;
哇！真的有用！
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)"
要结束这个小冒险，a playground 你可以自己玩这个。