二叉树类型实例化的高度过高

2024-04-17

我正在尝试类型系统,目前正在尝试在类型级别进行反向级别顺序遍历。这些是我正在使用的类型:

type LEFT = 0;
type VALUE = 1;
type RIGHT = 2;

type List = ReadonlyArray<unknown>;

type Increment<N extends List> = [...N, unknown];
type Decrement<N extends List> = N extends readonly [...infer H, any] ? H : never;

// `Node` already exists as a built-in... so I used Deno...
type Deno = [LEFT: Deno | undefined, VALUE: number, RIGHT: Deno | undefined];

我使用元组而不是对象类型来表示节点,因为创建和更改测试值会更容易。我还有一些别名,以使其在访问数据时更加“可读”(MyDeno[LEFT]MyDeno[0])。另外,我使用元组长度来表示数字,因为它们是much更容易使用,并且不需要手动指定限制。

无论如何,我可以用 JavaScript 获取树的高度,如下所示:

function height(node) {
  if (!node) return 0;

  const lhs = height(node.left);
  const rhs = height(node.right);

  return Math.max(lhs, rhs) + 1;
}

但是我尝试将其传输到类型系统会产生错误:

type Max<A extends List, B extends List> = A extends [...B, ...any[]] ? A : B;

type Height<Root extends Deno | undefined> =
    Root extends Deno
        ? Max<Increment<Height<Root[LEFT]>>, Increment<Height<Root[RIGHT]>>>
//            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Type instantiation is excessively deep and possibly infinite.
        : [];

即使它适用于示例数据:

type Data = [
    [
        [undefined, 4, undefined],
        2,
        [undefined, 5, undefined],
    ],
    1,
    [undefined, 3, undefined],
];

// Should be 3 since the height of `Data` is 3
type T = Height<Data>["length"];
//   ^? 3

我没想到这会抛出“类型实例化过深”......我的类型中的错误在哪里,我该如何重构我的Height输入这样就不会抛出此错误?在我能纠正这个问题之前,我会坚持使用//@ts-ignore.

操场 https://tsplay.dev/mAreQW


已完成实施 https://github.com/kelsny/ja-reverse-level-order-traversal/blob/main/translated.ts and 操场 https://tsplay.dev/WzP32N


我注意到有时当递归条件类型 https://www.typescriptlang.org/docs/handbook/release-notes/typescript-4-1.html#recursive-conditional-types are 分配性的 https://www.typescriptlang.org/docs/handbook/2/conditional-types.html#distributive-conditional-types与非分布式类型相比,达到实例化深度限制的可能性更大。

因此,我采取的一种方法是看看我是否可以通过关闭联合的分配性来继续(通过标准的一元组包装技术X extends Y ? A : B[X] extends [Y] ? A : B):

type Height<Root extends Deno | undefined> =
    [Root] extends [Deno]
    ? Max<Increment<Height<Root[LEFT]>>, Increment<Height<Root[RIGHT]>>>  // okay
    : [];

这有效,至少对于您的示例代码来说是这样。

Playground 代码链接 https://www.typescriptlang.org/play?#code/C4TwDgpgBAMgogMQCpQLxQAwG4CwAoUSKANQEEYBVONKARlwPGgCUBJAcQAkV0AmB-IWgwAlgGdgNZhACGAEwD2AOwA2IUgCcNMkAB4ArkoDWShQHclAPgGMirJQGMNEALYQlwXQDkoEAB7A7nJisOLAljQA2gB0sV4ANFCGJuZKALoMQlAAIhBOru6ePv6BSsGhEhHoxQFBIc7yympQMbEiSgBmEBpQnIkySiBpUAD8vVAAXFBKEABu3TZZuaZR8MhTywpQAD5JZRAd7RByiWSUcFNK+i4ARt2JbFxIG+5bu4ZyB0dyGfiCTFAALIyPy6Ui+WplEKiCSJABCENK5Rh4Ro4JKdRasWicMS2IGIEiaWGY3BUzhiwBnAgIgA5gALTzMBQKSQYqE5V47PafQ4zORVfBQYUtZms4bs8qRTZpIUisbA0H2fJuDy6al0xm6MXASJrJBpSyWRLK5yqzwahlMlm6x7cQ1G4UAeidUAURh0cuFUyJlKI2RkwBkUS9LVDIpaHy+-MSABZElG+cc0vFwyLeKm8BGI5FE99EgBWBP7JM-TMRlOh2jlkW5kv5qAAZmLvO+lbwvzw+BdUAAyvSFPoVHIoHcm1AxO0HNBgPToHPNZIFB0oAADANB1dQcRN-5EHi9GlW3QbmSWSIAIhU7lps4vnZ7woAeiMgA

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

二叉树类型实例化的高度过高 的相关文章

随机推荐

  • 如何使用 UIPath 中的“关闭选项卡”活动关闭子选项卡

    UiPath 是closing the 主窗口而不是子窗口 我在中定义了一个浏览器变量attach browser活动并将该浏览器变量传递给Close tab活动 Chrome 主窗口仍处于关闭状态 另附上项目 xaml 文件https d
  • iOS11 AppIcon无法更改

    Xcode 9 测试版 6 iOS 11 测试版 10 我想要使 用自定义应用程序图标打包应用程序 因此我尝试替换 DerivedData Users XXX Library Developer Xcode DerivedData proj
  • Pyparsing 分隔列表仅返回第一个元素

    这是我的代码 l 1 3E 2 2 5E 1 parser Word alphanums grammar delimitedList parser delim t print grammar parseString l 它返回 1 3E 2
  • iOS:从 url 加载图像

    我需要从 url 加载图像并将其设置在 UIImageView 中 问题是我不知道图像的确切大小 那么如何才能正确显示图像呢 只需使用 UIImage 的 size 属性即可 例如 NSURL url NSURL URLWithString
  • 将带有ajax请求的数组发送到php

    我像这样创建了数组 9 ques 5 19 ques 4 现在我想将它从 JS 发送到 PHP 但我没有得到正确的结果 我的JS代码是 button click function e e preventDefault ajax type p
  • nameof 和 typeof 的区别

    如果我错了请纠正我 但是做类似的事情 var typeOfName typeof Foo Name and var nameOfName nameof Foo 应该给你完全相同的输出 根据该消息来源 可以理解的原因之一是 https msd
  • 使用 RPATH 但不使用 RUNPATH?

    这一页 https web archive org web 20120418232524 http labs qt nokia com 2011 10 28 rpath and runpath 说关于图书馆检索的顺序ld so Unless
  • 覆盖特定模型的 Django 管理 URL?

    首先是一些背景 我有一个Event模型具有各种event types 我想将这些事件类型之一 电影 分解到它自己的管理中 我已经具备了基本功能 继承自的代理模型Event named Film 该代理模型的自定义管理器 仅将其过滤为 电影
  • 从 GoDaddy 托管的 ASP.NET MVC 应用程序发送邮件消息时出现问题

    我在 GoDaddy 托管的 MVC Web 应用程序上有一个表单 用户可以填写该表单并发送给我们的办公室 我目前正在使用 Gmail 帐户和 GoDaddy 电子邮件帐户 链接到我的托管空间 对其进行测试 使用 Gmail 代码后 电子邮
  • 如何使用自动生成的列隐藏 ASP.NET GridView 中的列?

    即使 SqlDataSource1 DataBind GridView1 Columns Count 也始终为零 但网格没问题 I can do for int i 0 i lt GridView1 HeaderRow Cells Coun
  • Android CursorLoader 带有选择和selectionArgs[]

    我在用Loader for RecyclerView Adapter列出项目 我想列出数据库表中的特定项目 所以我做了 public Loader
  • 从 csv 文件创建代理时使用 to-reports

    我的问题有点长 如果您能阅读全部内容 我真的很感激 并且我将非常感谢您的任何建议 我有与 2 位海龟消费者相关的数据 他们对笔记本电脑的功能进行了评级 笔记本电脑有两种特征 屏幕尺寸和电池寿命 每个都有一些级别 例如电池续航时间有5小时 1
  • 从 firebase 渲染 FlatList 中的数据

    我正在使用 React Native 0 49 我从 firebase 中获取了数据 用户列表users 这个列表中的每一项都是这样设置的firebase database ref users userId set userInfo 用户
  • bigquery 允许的表数量是否有限制

    BigQuery 中可以拥有的表数量有限制吗 我正在尝试创建多个小表以减少查询成本 谢谢 表的数量没有限制 由于查询字符串的长度有 10k 的限制 因此您可能会在查询所有这些内容时遇到问题
  • 使用承诺 - 在失败处理程序中记录堆栈跟踪

    我对 Nodejs 相当陌生 所以我将更详细地解释我想要做什么 我有一个网络服务器 如果请求失败 我想记录该异常的堆栈跟踪 但提供错误页面而不是使服务器崩溃 例如 处理请求的函数 var Q require q var requestHan
  • 使用 awk 对单独行上的多个字段进行数学运算

    我一直在对 3 字段 x 2 行文件进行一些数学运算 如下所示 3216 01 2724 81 1708 25 1762 48 617 436 1650 79 我的问题是如何引用第一行的第一个字段并在同一计算中引用第二行的第一个字段 为了完
  • 使用逻辑回归时sklearn重要特征错误

    以下代码使用随机森林模型为我提供一个显示特征重要性的图表 from sklearn feature selection import SelectFromModel import matplotlib clf RandomForestCla
  • Gradle-与外部项目的多项目?

    在 Gradle 多项目设置中是否无法使用主项目文件夹之外的外部依赖项 就像在settings gradle文件 我可以没有类似的东西吗 include C some path to dependent project ChildA Chi
  • 检查 python 调试器中的复杂变量,例如 pudb

    如何使用 python 调试器检查复杂变量 列表 字典 对象 值 我是 python 新手 我尝试了 pudb 看起来当变量类型为复杂类型时 调试器仅显示变量的类型 而不显示变量的类型价值 是否可以使用 pudb 检查值 或者有其他 pyt
  • 二叉树类型实例化的高度过高

    我正在尝试类型系统 目前正在尝试在类型级别进行反向级别顺序遍历 这些是我正在使用的类型 type LEFT 0 type VALUE 1 type RIGHT 2 type List ReadonlyArray