考虑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中的类型.然而,我不知道如何实现"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];

下面是如何在JavaScript中实现flatten函数.

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:如果有帮助,下面是Haskell中value level 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

推荐答案

updated may 19

哦,天哪,我们还没做完.我们可以把这件事做得更快!

您可以做的第一件事是将extends in 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;

try this个新操场,看看这些变化的影响.


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

那么,让我们开始:

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>

让它从unions 中为我们生成所有可能的配对.

好了,是时候开始研究解决方案了.

回想一下,如果xs为空,则返回x:

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

这意味着这就像原始代码中的循环!我们使用映射类型循环每个索引.

在循环体内部,我们在索引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来结束所有的ternary/conditional(因为无论如何都不应该达到这些子句):

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

为了结束这场小小的冒险,你可以自己玩.

Javascript相关问答推荐

MathJax可以导入本地HTML文档使用的JS文件吗?

如何通过使用vanilla JS限制字体大小增加或减少两次来改变字体大小

如何控制Reaction路由加载器中的错误状态?

如何在ASP.NET中使用Google Charts API JavaScript将条形图标签显示为绝对值而不是负值

JQuery Click事件不适用于动态创建的按钮

如何发送从REST Api收到的PNG数据响应

连接到游戏的玩家不会在浏览器在线游戏中呈现

Vaadin定制组件-保持对javascrip变量的访问

向数组中的对象添加键而不改变原始变量

使用Ace编辑器对子组件实例的native-element 进行Angular 获取时面临的问题

在查看网页时,如何使HTML中的按钮工作方式类似于鼠标上的滚轮或箭头键?

不同表的条件API端点Reaction-redux

谷歌饼图3D切片

如何正确地在ComponentWillUnmount中卸载状态以避免内存泄漏?

在使用JavaScript以HTML格式显示Google Drive中的图像时遇到问题

Js问题:有没有办法将数据从标记表转换成图表?

Reaction:从子组件调用父组件中的函数

ReactJS扫描线演示:多个曲面未同时更新的问题

如何使用Reaction/Redux创建购物车逻辑?

Oracle APEX-如何调用Java脚本函数