文章/答案/技术大牛

发布

社区首页 >问答首页 >TypeScript中的类型级加泰罗尼亚函数

问TypeScript中的类型级加泰罗尼亚函数
EN

Stack Overflow用户

提问于 2022-05-18 06:16:08

回答 2查看 127关注 0票数 4

考虑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);

它返回所有可能的关联二进制运算符的n应用程序的方法，其中n = xs.length。

我想做一些类似的事情，但是在TypeScript中使用类型。然而，我不知道如何实现“其他”分支。

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

javascript

typescript

catalan

回答 2

Stack Overflow用户

回答已采纳

发布于 2022-05-18 15:06:56

于5月19日更新，

天哪，我们还没说完呢。我们可以把它弄得更快！

您可以做的第一件事是将Catalan中的扩展转换为仅：

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

这使得它非常快。现在它只是一个查找表。

然后，我们可以使用分布式条件类型，而不是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;

尝试这新操场来查看这些更改的效果。

当遇到这些类型级别的问题时，最好查看原始代码并查找模式，或者类型系统可以为您做的任何事情。

那么，让我们开始：

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为空，则直接返回x。我们做了一个心理笔记，以后再使用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处拆分元组，并返回这两部分。这将比单独分割两次元组要快得多，并且可以在没有太多麻烦的情况下实现。

最后，我们注意到这个嵌套循环：

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

在类型系统中不需要这样做，我们可以简单地做：

Pair<YS, ZS>

让它从工会中为我们生成所有可能的配对。

好了，是时候解决这个问题了。

回想一下，如果x是空的，则返回xs：

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

同时，当XS只是一个元素时，我们返回这对元素。如果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"。

这意味着这就像原始代码中的循环一样！我们使用映射类型遍历每个索引。

在循环体中，我们在索引XS处划分K。

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关闭所有三元/条件(因为这些子句无论如何都不应该到达)：

              : 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)"

为了结束这个小冒险，游乐场，你可以在那里玩自己。

票数 3

Stack Overflow用户

发布于 2022-05-18 09:26:27

因此，我的尝试是：

首先，我不确定我是否正确地理解了加泰罗尼亚算法。我创建这种类型纯粹是通过查看您给出的示例。您需要测试这种方法是否适用于更大的元组。

解释

我用了一些实用工具来解决这个问题。我需要一个到splice数组的类型，所以我使用了来自这里的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 (字符串)生成的数组的indize转换回数字。我使用了这个助手类型：

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，则返回数组中的元素。如果是length 2，则返回前两个元素的Pair。

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

剩下的就更复杂了。我的方法是在每一个可能的索引上“剪切”数组一次，然后递归地调用_Catalan，同时使用两个子数组。

[ 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创建两个子数组，并通过使用它们调用_Catalan来创建两个子数组的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高层工会，每个成员在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

游乐场

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/72284028

复制

相似问题

问TypeScript中的类型级加泰罗尼亚函数
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问TypeScript中的类型级加泰罗尼亚函数EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问TypeScript中的类型级加泰罗尼亚函数
EN