递归复用

王小明大约 4 分钟

递归复用

针对提取或构造的数组元素个数不确定、字符串长度不确定、对象层数不确定

递归是把问题分解为一系列相似的小问题，通过函数不断调用自身来解决这一个个小问题，直到满足结束条件，就完成了问题的求解

TypeScript 类型系统不支持循环，但支持递归。当处理数量（个数、长度、层数）不固定的类型的时候，可以只处理一个类型，然后递归的调用自身处理下一个类型，直到结束条件也就是所有的类型都处理完了，就完成了不确定数量的类型编程，达到循环的效果

Promise 的递归复用

DeepPromiseValueType

实现 Promise<Promise<Promise<number>>> => number

type test = Promise<Promise<Promise<Record<string, any>>>>;

type DeepPromiseValueType<P extends Promise<unknown>> = P extends Promise<
  infer ValueType
>
  ? ValueType extends Promise<unknown>
    ? DeepPromiseValueType<ValueType>
    : ValueType
  : never;

type result = DeepPromiseValueType<test>;

思路

每次只处理一个类型的提取，也就是通过模式匹配提取出 value 的类型到 infer 声明的局部变量 ValueType 中

然后判断如果 ValueType 依然是 Promise 类型，就递归处理

结束条件就是 ValueType 不为 Promise 类型，那就处理完了所有的层数，返回这时的 ValueType

数组类型的递归

ReverseArr

实现 [1, 2, 3, 4, 5] => [5, 4, 3, 2, 1]

type ReverseArr<Arr extends unknown[]> = Arr extends [
  infer First,
  ...infer Rest,
]
  ? [...ReverseArr<Rest>, First]
  : Arr;

type result = ReverseArr<[1, 2, 3, 4, 5]>;

思路

每次只处理一个元素的提取，放到 infer 声明的局部变量 First 里，剩下的放到 Rest 里。

用 First 作为最后一个元素构造新数组，其余元素递归的取。

结束条件就是取完所有的元素，也就是不再满足模式匹配的条件，这时候就返回 Arr

Includes

实现 [1, 2, 3, 4, 5], 4 => true

type IsEqual<A, B> = (A extends B ? true : false) &
  (B extends A ? true : false);

type Includes<Arr extends unknown[], Ele extends unknown> = Arr extends [
  infer First,
  ...infer Rest,
]
  ? IsEqual<First, Ele> extends true
    ? true
    : Includes<Rest, Ele>
  : false;

type result = Includes<[1, 2, 3, 4, 5], 5>;

思路

每次提取一个元素到 infer 声明的局部变量 First 中，剩余的放到局部变量 Rest

判断 First 是否是要查找的元素，也就是和 FindItem 相等，是的话就返回 true，否则继续递归判断下一个元素

直到结束条件也就是提取不出下一个元素，这时返回 false

相等的判断就是 A 是 B 的子类型并且 B 也是 A 的子类型

RemoveItem

实现 [1, 2, 3, 4, 5], 4 => [1, 2, 3, 5]

type IsEqual<A, B> = (A extends B ? true : false) &
  (B extends A ? true : false);

type RemoveItem<Arr extends unknown[], Ele extends unknown> = Arr extends [
  infer First,
  ...infer Rest,
]
  ? IsEqual<First, Ele> extends true
    ? [...RemoveItem<Rest, Ele>]
    : [First, ...RemoveItem<Rest, Ele>]
  : Arr;

type result = RemoveItem<[1, 2, 3, 4, 5], 5>;

思路

和 Include 主要的区别在 IsEqual 为 true 的处理, 这里为啥为 true 了, 不直接返回 Rest 呢?

看下面例子就明白嘞

type test = IsEqual<1, number>; // true

如果我们传的是 number, [1, 2, 3, 4, 5] 其实每一项都应该被移除的, 所以这里还需要接着 递归

BuildArray

实现 生成固定长度的数组

type BuildArray<
  Len extends number,
  Arr extends unknown[] = [],
> = Arr['length'] extends Len ? Arr : BuildArray<Len, [...Arr, unknown]>;

思路

arr["length"]来 extends Len, 来判断是否是达到要求

字符串类型的递归

ReplaceAll

实现 decadewwwww => decadeaaaaa

type ReplaceAll<
  Str extends string,
  From extends string,
  To extends string,
> = Str extends `${infer Left}${From}${infer Right}`
  ? `${Left}${To}${ReplaceAll<Right, From, To>}`
  : Str;

type result = ReplaceAll<'dddddddecadewwww', 'w', 'a'>;

思路

Left 匹配到的一定是不会含有 From 的, 所以唯一能让我们递归去匹配的只能是 Right

StringToUnion

实现 abc => a | b | c

type StringToUnion<Str extends string> =
  Str extends `${infer First}${infer Rest}`
    ? First | StringToUnion<Rest>
    : never;

type result = StringToUnion<'abcde'>;

ReverseStr

实现 abc => cba

type ReverseStr<Str extends string> = Str extends `${infer First}${infer Rest}`
  ? `${ReverseStr<Rest>}${First}`
  : Str;

type result = ReverseStr<'abcde'>;

对象类型的递归

DeepReadonly

实现 给对象每个key(包括key => value也是对象的话), 都加上 readonly

type DeepReadonly<Obj extends Record<string, any>> = Obj extends any
  ? {
      readonly [Key in keyof Obj]: Obj[Key] extends Record<any, any>
        ? Obj[Key] extends Function // 处理function
          ? Obj[Key]
          : DeepReadonly<Obj[Key]>
        : Obj[Key];
    }
  : never;

type result = DeepReadonly<{
  age: number;
  name: string;
  likes: {
    xxx: {
      xx: {
        x: number;
      };
      xxFn: () => void;
    };
  };
}>;

提示

因为 ts 的类型只有被用到的时候才会做计算, 所以我们先 Obj extends any

总结

递归是把问题分解成一个个子问题，通过解决一个个子问题来解决整个问题。形式是不断的调用函数自身，直到满足结束条件。

在 TypeScript 类型系统中的高级类型也同样支持递归，在类型体操中，遇到数量不确定的问题，要条件反射的想到递归。比如数组长度不确定、字符串长度不确定、索引类型层数不确定等