在 TypeScript 中实现类型级别深度优先搜索

发布于08月30日

我正在try 使用TypeScrip中的类型函数来实现深度优先搜索(DFS)算法.

以下是我的代码: 首先，我定义了最终的DFSRecursive类型函数所需的所有不同类型的函数，在那里我实现了递归DFS算法.

const MyGraph: Graph = {
  A: ["B", "C", "D"],
  B: ["F", "E"],
  C: ["E", "F"],
  D: ["E", "F", "G"],
  E: [],
  F: [],
  G: [],
};

type Graph = {
  A: ["B", "C", "D"],
  B: ["F", "E"],
  C: ["E", "F"],
  D: ["E", "F", "G"],
  E: [],
  F: [],
  G: [],
}

export type Concat<T extends string[], U extends string[]> = [...T, ...U];
export type Pop<T extends string[]> = T extends [...infer Rest extends string[], infer Last extends string]
  ? T extends [infer Last]
  ? []
  : Rest
  : never;
export type Append<T extends string[], U extends string> = [...T, U];
export type IsEmpty<T extends string[]> = T extends [] ? true : false;
export type Difference<T extends string[], U extends string[], Result extends string[] = []> =
  T extends [infer First extends string, ...infer Rest extends string[]]
  ? false extends Contains<U, First> 
  ? Difference<Rest, U, Append<Result, First>>
  : Difference<Rest, U, Result>
  : T extends string[]
  ? string[]
  : Result;
export type Peek<T extends string[]> = T extends [...infer Rest extends string[], infer Last extends string]
  ? Last
  : T extends [infer Last extends string]
  ? Last
  : T extends string[]
  ? never
  : never;
export type Contains<T extends string[], Element extends string> = T extends [infer Head, ...infer Rest extends string[]]
  ? Head extends Element
  ? true
  : Contains<Rest, Element>
  : false;

export type DFSRecursive<Curr extends string, GraphType extends Graph, Stack extends string[], Visited extends string[] = []> =
  true extends IsEmpty<Stack>
  ? Visited
  : true extends Contains<Visited, Peek<Stack>>
  ? DFSRecursive<Peek<Stack>, GraphType, Pop<Stack>, Visited> //Append<Visited, Peek<Stack>>>
  : GraphType[keyof Graph & Peek<Stack>] extends infer GT extends string[]
  ? Difference<GT, Visited> extends infer D extends string[]
  ? Peek<Stack> extends infer PS extends string
  ? Append<Visited, PS> extends infer A extends string[]
  ? Concat<Pop<Stack>, D> extends infer C extends string[]
  ? DFSRecursive<Peek<Stack>, GraphType, C, A>
  : never
  : never
  : never
  : never
  : never;

type X = DFSRecursive<"A", Graph, ["A"]>

工作了几个小时后，我意识到有一个错误:

Type instantiation is excessively deep and possibly infinite.

我怎么可能解决这个问题呢？

Playground个

export type Contains<A extends string[], E extends string> = A extends [infer Head extends string, ...infer Rest extends string[]] ? Head extends E ? true : Contains<Rest, E> : false; export type Minus<A extends string[], B extends string[]> = A extends [infer First extends string, ...infer Rest extends string[]] ? (true extends Contains<B, First> ? Minus<Rest, B> : [First, ...Minus<Rest, B>]) : []; export type DFSRecursiveImpl< GraphType extends Record<string, string[]>, Stack extends string[], Visited extends string[]> = Stack extends [...infer Prefix extends string[], infer V extends string] ? Minus<GraphType[V], Visited> extends [infer W extends string, ...string[]] ? DFSRecursiveImpl<GraphType, [...Stack, W], [...Visited, W]> : DFSRecursiveImpl<GraphType, Prefix, Visited> : Visited; export type DFSRecursive<GraphType extends Record<string, string[]>, Start extends string> = DFSRecursiveImpl<GraphType, [Start], [Start]>;

export type DFSRecursiveSafe< Vertex extends string, GraphType extends Record<Vertex, Vertex[]>, Start extends Vertex> = DFSRecursive<GraphType, Start>; type Accepted = DFSRecursiveSafe<keyof Graph, Graph, "A">; // A B F E C D G

graph = { 'A': ["B", "C", "D"], 'B': ["F", "E"], 'C': ["E", "F"], 'D': ["E", "F", "G"], 'E': [], 'F': [], 'G': [], } def DfsRecursive(stack, visited): if not stack: return visited v = stack[-1] for w in graph[v]: if w not in visited: return DfsRecursive(stack + [w], visited + [w]) return DfsRecursive(stack[:-1], visited) print(DfsRecursive(['A'], ['A']))

在 TypeScript 中实现类型级别深度优先搜索

推荐答案

Typescript相关问答推荐

typescribe不能使用值来索引对象类型，该对象类型满足具有该值的另一个类型'

如何在排版中正确键入中间件链和控制器链

未在DIST中正确编译TypeScrip src模块导入

在TypeScrip的数组中判断模式类型

从子类构造函数推断父类泛型类型

如何实现异构数组内函数的类型缩小

部分更新类型的类型相等

TypeError：正文不可用-NextJS服务器操作POST

按函数名的类型安全类型脚本方法包装帮助器

常量类型参数回退类型

vue-tsc失败，错误引用项目可能无法禁用vue项目上的emit

有没有一种方法可以确保类型的成员实际存在于TypeScript中的对象中？

刷新时保持当前名称的Angular

如何使函数参数数组不相交？

在类型脚本中创建显式不安全的私有类成员访问函数

我可以将一个类型数组映射到TypeScrip中的另一个类型数组吗？

导航链接不触发自定义挂钩

Typescript泛型-键入对象时保持推理

如何使用动态生成的键和值定义对象的形状？

req.files = 未定义(Multer、Express、Typescript)