Zenn
Closed24

type-challenges【medium】

TypeScript
かしかし

https://github.com/type-challenges/type-challenges

easy はできるやろと思ったので midium からやっていく

ReturnType

問題

T が関数の型になっていれば、その戻り値の型を infer で取り出す

type MyReturnType<T> = T extends (...args: any) => infer R ? R : never;

Omit

問題

最初こういうのを思った

type MyOmit<T, K extends keyof T> = {
  [Key in keyof T]: Key extends K ? never : T[Key]
};

//  `type Result = MyOmit<Todo, 'description'>;` が次のようになってしまう
//  type Result = {
//   title: string;
//   description: never;
//   completed: boolean;
// };

そもそもキーから K を除外する必要があるので、 Exclude を使って次のようにした

type MyOmit<T, K extends keyof T> = {
  [Key in Exclude<keyof T, K>]: T[Key]
};

他の人の回答を見たら Exclude を使わなくてもできるらしい
キー側で never を指定すると型に現れないということみたい

type MyOmit<T, K extends keyof T> = {
  [Key in keyof T as Key extends K ? never : R]: T[Key]
};

Readonly 2

問題

Readonly の応用問題っぽい

Readonly<T> はこんな感じ

type MyReadonly<T> = {
  readonly [Key in keyof T]: T[Key]
}

Readonly2<T, K> は Kが指定されていないときは Readonly と同じ振る舞いをする。
K に T のすべてのキーを指定したときも同じ振る舞いをすることになるので、次のようなデフォルト型引数を与える

type MyReadonly2<T, K extends keyof T = keyof T> = ...

あとは Pick と Omit と Readonly を組み合わせたらおしまい。
こういうことをやりたいはずなので、

type MyReadonly2<T, K extends keyof T = keyof T> = 
  Readonly<Pick<T, K>> & Omit<T, K>;

あとは展開するだけ

type MyReadonly2<T, K extends keyof T = keyof T> = {
  readonly [Key in keyof T]: T[Key]
} & {
  [Key in Exclude<keyof T, K>]: T[Key]
};

DeepReadonly

Readony を object のプロパティに対してさらに深堀できるように拡張したらいいなあと思った。

object として判定されるものは何があるかと思って次の実験をした。

type IsObject<T> = T extends object ? true : false;

type isNumberObject = IsObject<number>; // -> false
type isBooleanObject = IsObject<boolean>; // -> false
type isStringObject = IsObject<string>; // -> false
type isFunctionObject = IsObject<() => void>; // -> true
type isArrayObject = IsObject<number[]>; // -> true
type isObjectObject = IsObject<{a: number}>; // -> true

今回は IsObject が true なもののうち関数の型以外なので、関数の型もプリミティブ型と同じ操作をすればいいことがわかる。

type DeepReadonly<T> =
  {
    readonly [Key in keyof T]:
      T[Key] extends Function
        ? T[Key]
        : T[Key] extends object
        ? DeepReadonly<T[Key]>
        : T[Key]
  };
かしかし

Tuple to Union

問題

ルックアップ型そのもの

type TupleToUnion<T extends unknown[]> = T[number]

Chainable Options

問題

急に難しくなってない？

とりあえず、 get をしたらそれまで option で追加したプロパティを持つ型を吐き出してほしいのだから、 get の型は型引数と一致してよいとわかる。
また、ユースケースを見るとデフォルト型引数が必要そう。

type Chainable<T = {}> = {
  option(key: string, value: any): ...;
  get(): T;
}

option は、 key と value の型を使いたいので、ジェネリクスを使いたい。
また、 戻り値の型も Chainable で、 T と新しく追加したプロパティを持っていればいいので次のようになる。

type Chainable<T = {}> = {
  option<K extends string, V>(key: K, value: V): Chainable<T & {[Key in K]: V}>;
  get(): T;
}

result2 と result3 をみると、option ですでに存在するキーを指定したときの仕様は次のようになる。

  • 別の型で上書きはできる
  • 同じ型で上書きしようとするとエラーになる

また、 result2 の計算過程で get は正常にできているので option の戻り値が never になるのではなく、あくまで引数の型を never とする必要があるらしい。
戻り値の型は、常に Omit<T, K> することで後から指定した型で上書きできるようになる。

type IsValidKeyValue<T, K extends string, V> =
  K extends keyof T
  ? T[K] extends V
    ? false
    : true
  : true

type Chainable<T = {}> = {
  option<K extends string, V>(
    key: IsValidKeyValue<T, K, V> extends true ? K : never,
    value: V
  ): Chainable<Omit<T, K> & {[Key in K]: V}>
  get(): T;
};

Last of Array

問題

スプレッド構文を使う

type Last<T extends any[]> = T extends [...any, infer Last] ? Last : never

Pop

問題

type Pop<T extends any[]> = T extends [...(infer Init), any] ? Init : never

Promise.all

問題

Awaited っぽいものを内部で使いたい

type MyAwaited<T> = T extends Promise<infer U> ? U : T
Awaited との差分

Awaited の問題 の最後のエラーになるケースが地味にいやらしい

type MyAwaited<T extends Promise<any>> =
  T extends Promise<infer U>
  ? U extends Promise<any>
    ? MyAwaited<U>
    : U
  : never

Promise.all の実装では、 Promise でないものはそのままで扱っていいのでもっと簡素な実装になった

こんな感じで実装した。

type MyAwaited<T> = T extends Promise<infer U> ? U : T
type MyAwaitedAll<T extends readonly any[]> =
  T extends readonly [infer Head, ...(infer Tail)]
  ? [MyAwaited<Head>, ...(MyAwaitedAll<Tail>)]
  : T

declare function PromiseAll<T extends readonly any[]>(values: T): Promise<MyAwaitedAll<T>>

MyAwaitedAll で先頭から MyAwaitd を適用していく。

この実装だと promiseAllTest3 が通らない（Promise<(number | Promise<number>)[]> という型になる）。
引数が const か否かにかかわらず配列の要素それぞれの型を抽出する必要があるので、引数のほうに readonly を追加する

declare function PromiseAll<T extends readonly any[]>(values: readonly T): Promise<MyAwaitedAll<T>>

// error: 'readonly' type modifier is only permitted on array and tuple literal types.(1354)

T をタプルだと認識させればテストが通る。
あと、引数の型に readonly を付与したので型引数にはなくてよいらしい

declare function PromiseAll<T extends any[]>(values: readonly [...T]): Promise<MyAwaitedAll<T>>
かしかし

Type Lookup

問題

Extract というユーティリティ型がある

type LookUp<U extends { type: string }, T extends U['type']>= Extract<U, {type: T}>;

これで動くので、要は Extract を実装したいということ

Distributive conditional types を使っていい感じに実装できそう。

Distributive conditional types について

https://www.typescriptlang.org/docs/handbook/release-notes/typescript-2-8.html#distributive-conditional-types

Conditional types in which the checked type is a naked type parameter are called distributive conditional types. Distributive conditional types are automatically distributed over union types during instantiation. For example, an instantiation of T extends U ? X : Y with the type argument A | B | C for T is resolved as (A extends U ? X : Y) | (B extends U ? X : Y) | (C extends U ? X : Y).

Conditional types にユニオン型を渡したものを Distributive conditional types と呼び、自動でユニオン型に分散して解釈される
というようなことだと思う（曖昧）

結局 type S<T, U> = T extends U ? X : Y; としたとき、S<A | B | C> は (A extends U ? X : Y) | (B extends U ? X : Y) | (C extends U ? X : Y) と解釈されるということらしい。

type MyExtract<T, U> = T extends U ? T : never;
type LookUp<U extends { type: string }, T extends U['type']>= MyExtract<U, {type: T}>;

まとめるとこんなかんじ

type LookUp<U extends { type: string }, T extends U['type']> =
  U extends { type: T } ? U : never;

Trim Left

問題

Template Literal Types を使う。

type TrimLeft<S extends string> = S extends `${' '|'\n'|'\t'}${infer T}` ? TrimLeft<T> : S;

Trim

問題

type TrimLeft<S extends string> = S extends `${' '|'\n'|'\t'}${infer T}` ? TrimLeft<T> : S;
type TrimRight<S extends string> = S extends `${infer T}${' '|'\n'|'\t'}` ? TrimRight<T> : S;
type Trim<S extends string> = TrimLeft<TrimRight<S>>

Capitalize

問題

type LowerToUpperMap = {
  a: 'A',
  b: 'B',
  c: 'C',
  ...
  y: 'Y',
  z: 'Z',
};

type Upper<T extends string> =
  T extends keyof LowerToUpperMap ? LowerToUpperMap[T] : T;

type MyCapitalize<S extends string> =
  S extends `${infer H}${infer T}` ? `${Upper<H>}${T}` : S

Uppercase というのがいたらしい

type MyCapitalize<S extends string> =
  S extends `${infer H}${infer T}` ? `${Uppercase<H>}${T}` : S
かしかし

Replace

問題

はじめはこんな感じで実装した。

type Replace<S extends string, From extends string, To extends string> =
  S extends `${infer X}${From}${infer Y}`
  ? `${X}${To}${Y}`
  : S

3つ目のケースで From が空文字列であるがために意図しない挙動になるため、これを対処する必要がある。

type Replace<S extends string, From extends string, To extends string> =
  From extends ''
  ? S
  : S extends `${infer X}${From}${infer Y}`
  ? `${X}${To}${Y}`
  : S

To を例えば 'hoge' | 'bar' とするとどうなるのか気になった

type Test = Replace<'abc', 'b', 'HOGE' | 'BAR'>;
// -> type Test = "aHOGEc" | "aBARc"

ReplaceAll

問題

Replace を入れ子にする感じ

type ReplaceAll<S extends string, From extends string, To extends string> =
  From extends ''
  ? S
  : S extends `${infer X}${From}${infer Y}`
  ? `${X}${To}${ReplaceAll<Y, From, To>}`
  : S

Append Argument

問題

type AppendArgument<Fn, A> =
  Fn extends (...args: infer Args) => infer Result
  ? (...args: [...Args, A]) => Result
  : never
かしかし

Permutation

問題

なんもわからんかったから これ を参考にした。

Distributive conditional types を使って次のようにしてみる

type S1<U> = U extends any? [U]: never;
type P1 = S1<'A' | 'B' | 'C'>;
// type P1 = ['A'] | ['B'] | ['C']

分配された型以外を次に引き継ぐ必要がある。
引数に C を追加し、分配されずに残っている型の情報を保持させる。

type S2<U, C=U> =  U extends any ? [U, S2<Exclude<C, U>>] : never;
type P2 = S2<'A' | 'B' | 'C'>;
// type P2 = ["A", ["B", ["C", never]] | ["C", ["B", never]]] | ["B", ["A", ["C", never]] | ["C", ["A", never]]] | ["C", ["A", ["B", never]] | ["B", ["A", never]]]

（playground の表示がおかしいらしく ["C", ["B", never]]] みたいな項がいるけど、内部では ["C", ["B", ["A", never]]] と推論されている。）

多分こういう推論がされているはず

S2<'A' | 'B' | 'C'>
->   'A' extends any ? ['A', S2<Exclude<'A' | 'B' | 'C', 'A'>>] : never
   | 'B' extends any ? ['B', S2<Exclude<'A' | 'B' | 'C', 'B'>>] : never
   | 'C' extends any ? ['C', S2<Exclude<'A' | 'B' | 'C', 'C'>>] : never
->   ['A', S2<'B' | 'C'>]
   | ['B', S2<'A' | 'C'>]
   | ['C', S2<'A' | 'B'>]

各項の最後に出てきている never は S2<never> -> never に起因するものらしい。
（Distributive conditional types で never を分配できなくて never になってるという解釈でいいのかな）
never のときに空配列を返すようにする。
U extends never ? [] : ... ではなく [U] extends [never] ? [] : ... としているのは、Distributive conditional types として推論されてしまわないようにするため。

type S3<U, C=U> =
  [U] extends [never]
  ? []
  : U extends any
  ? [U, S3<Exclude<C,U>>]
  : never;
type P3 = S3<'A'|'B'|'C'>;
// type P3 = ["A", ["B", ["C", []]] | ["C", ["B", []]]] | ["B", ["A", ["C", []]] | ["C", ["A", []]]] | ["C", ["A", ["B", []]] | ["B", ["A", []]]]

最後に配列の入れ子を展開すれば完成

type Permutation<U, C=U> =
  [U] extends [never]
  ? []
  : U extends any
  ? [U, ...Permutation<Exclude<C,U>>]
  : never;
かしかし

Length of String

問題

type StringToCharArray<S extends string> =
  S extends `${infer H}${infer T}`
  ? [H, ...(StringToCharArray<T>)]
  : []
type LengthOfString<S extends string> = StringToCharArray<S>['length']

Array にも String にも length というプロパティがあるけど、型の扱いが異なるのが面白い

type LengthOfArray = ['H', 'e', 'l', 'l', 'o']['length'];
// type LengthOfArray = 5

type LengthOfString = 'Hello'['length'];
// type LengthOfString = number

Flatten

問題

type Flatten<T> =
  T extends []
  ? []
  : T extends [infer Head, ...(infer Tail)]
  ? [...Flatten<Head>, ...Flatten<Tail>]
  : [T];

配列ならとにかく展開する。
Flatten は常に flat な配列の型を返すと思って、普通の再帰関数を書くのと同じように実装できる。

Append to object

問題

最初にこの実装をしたけどテストケースが通らなかった
Alike だと true になるけど、 Equal だと false

type AppendToObject<T, U extends string, V> = T & { [Key in U]: V };

交差型は使わずに、新しい型を作り直すように修正

type AppendToObject<T, U extends string, V> =
  { [Key in keyof T | U]: Key extends keyof T ? T[Key] : V };

Absolute

問題

string だけは解法わかったのでとりあえず実装する。

type AbsoluteString<T extends string> = T extends `-${infer Num}` ? Num : T;

number も bigint も Template literal types を使って同様に扱える。

type Absolute<T extends number | string | bigint> =
  `${T}` extends `-${infer Num}`
  ? Num
  : `${T}`;

String to Union

問題

「Length of String」とほぼ同じ。

type StringToCharArray<S extends string> =
  S extends `${infer H}${infer T}`
  ? [H, ...(StringToCharArray<T>)]
  : []
type StringToUnion<S extends string> = StringToCharArray<S>[number]
かしかし

Merge

問題

Append to object とほぼ同じ

type Merge<F extends Record<any, any>, S extends Record<any, any>> = {
  [Key in keyof (F & S)]: Key extends keyof S ? S[Key] : F[Key]
};

KebabCase

問題

基本的には大文字を全部 「- + 小文字」 に変換したらいい。

type UpperToBarLower<S extends string> =
  S extends `${infer Head}${infer Tail}`
  ? Head extends Lowercase<Head>
    ? `${Head}${UpperToBarLower<Tail>}`
    : `-${Lowercase<Head>}${UpperToBarLower<Tail>}`
  : S;
type KebabCase<S extends string> = UpperToBarLower<S>;

先頭だけ - をつけたくないのでフラグを追加した。

type UpperToBarLowerExceptFirst<S extends string, IsFirstLetter extends boolean = false> =
  S extends `${infer Head}${infer Tail}`
  ? Head extends Lowercase<Head>
    ? `${Head}${UpperToBarLowerExceptFirst<Tail>}`
    : `${IsFirstLetter extends true ? '' : '-'}${Lowercase<Head>}${UpperToBarLowerExceptFirst<Tail>}`
  : S;
type KebabCase<S extends string> = UpperToBarLowerExceptFirst<S, true>;

Uncapitalizeを使って2文字目が大文字かを判定することで、 IsFirstLetter の判定が必要なくなる。

type UpperToBarLowerExceptFirst<S extends string> =
  S extends `${infer Head}${infer Tail}`
  ? Tail extends Uncapitalize<Tail>
    ? `${Head}${UpperToBarLowerExceptFirst<Tail>}`
    : `${Head}-${UpperToBarLowerExceptFirst<Uncapitalize<Tail>>}`
  : S;
type KebabCase<S extends string> = UpperToBarLowerExceptFirst<Uncapitalize<S>>;

もうちょっとまとめる。

type KebabCase<S extends string> =
  S extends `${infer Head}${infer Tail}`
  ? `${Lowercase<Head>}${Tail extends Uncapitalize<Tail> ? '' : '-'}${KebabCase<Uncapitalize<Tail>>}`
  : S;

Diff

問題

返す型のキーの集合は O1 のキーか O2 のキーのいずれか一方のみに含まれるものなので、排他的論理和的をつくるようなイメージ。

type Diff<O1 extends Record<any, any>, O2 extends Record<any, any>> = {
  [Key in Exclude<keyof O1, keyof O2> | Exclude<keyof O2, keyof O1>]: Key extends keyof O1 ? O1[Key] : O2[Key]
};

AnyOf

問題

各要素が Truthy か判定する。
型ごとに Truthy か判定できるようにして、先頭から見ていけばいい。

type NumberTruthy<T extends number> = T extends 0 ? false : true;
type StringTruthy<T extends string> = T extends '' ? false : true;
type BooleanTruthy<T extends boolean> = T;
type ArrayTruthy<T extends any[]> = T extends [] ? false : true;
type RecordTruthy<T extends Record<any, any>> = keyof T extends never ? false : true

type Truthy<T> =
  T extends number
  ? NumberTruthy<T>
  : T extends string
  ? StringTruthy<T>
  : T extends boolean
  ? BooleanTruthy<T>
  : T extends any[]
  ? ArrayTruthy<T>
  : T extends Record<any, any>
  ? RecordTruthy<T>
  : never

type AnyOf<T extends readonly any[]> =
  T extends [infer Head, ...(infer Tail)]
  ? Truthy<Head> extends true
    ? true
    : AnyOf<Tail>
  : false;

IsNever

問題

type IsNever<T> = T extends never ? true : false; とすると Distributive conditional types の影響で意図したとおりに動作しない点に注意。

type IsNever<T> = [T] extends [never] ? true : false;
かしかし

IsUnion

問題

Distributive conditional types で分配されたら true にすればよさそう。
引数として、分配する型 T とは別に、元の型を保持する U を追加する。

type IsUnion<T, U=T> = T extends ...;

Exclude<元の型, 分配した型> extends never ? false : true とするといいことがわかる。

type IsUnion<T, U=T> =
  T extends U
  ? Exclude<U, T> extends never ? false : true
  : never;

これだと IsUnion<never> が never になってしまうので、前問の IsNever を使って次のようにして完成。

type IsUnion<T, U=T> =
  IsNever<T> extends true
  ? false
  : T extends U
  ? Exclude<U, T> extends never ? false : true
  : never;

ReplaceKeys

問題

U の各キーに対して、

  • T に含まれてないなら元の型 U[Key]
  • T に含まれて Y のキーでもあるなら Y[Key] で置き換える
  • T に含まれて Y のキーにないなら never 
type ReplaceKeys<U, T extends string, Y extends Record<any, any>> =
  {
    [Key in keyof U]:
      Key extends T
      ? Key extends keyof Y
        ? Y[Key]
        : never
      : U[Key]
  };

Remove Index Signature

問題

インデックス型のフィールド名の型に指定できる string``number``symbolを判定する IsIndexedSymbol を実装する。
Key Remapping を使って Index Symbol のフィールドを作らないようにする。

https://www.typescriptlang.org/docs/handbook/2/mapped-types.html#key-remapping-via-as

type IsIndexSymbol<T> =
  string extends T
  ? true
  : number extends T
  ? true
  : symbol extends T
  ? true
  : false;

type RemoveIndexSignature<T> = {
  [Key in keyof T as (IsIndexSymbol<Key> extends true ? never : Key)]: T[Key]
};

Percentage Parser

問題

頭から符号を取る関数、お尻から記号を取る関数を作って組み合わせる。

type TakePlusMinus<S extends string> =
  S extends `+${infer Else}`
  ? ['+', Else]
  : S extends `-${infer Else}`
  ? ['-', Else]
  : ['', S];

type TakePercentage<S extends string> =
  S extends `${infer Else}%`
  ? [Else, '%']
  : [S, ''];

type PercentageParser<A extends string> =
  TakePlusMinus<A> extends [infer PlusMinus, infer Else]
  ? Else extends string
    ? TakePercentage<Else> extends [infer Num, infer Percentage]
      ? [PlusMinus, Num, Percentage]
      : never
    : never
  : never;

Drop Char

問題

まず C は空文字列のときにエラーにするテストケースがあるので、先に潰してしまう。
あとは先頭から順に見ていって、見ている文字が C と一致するならば捨てることを繰り返す。

type DropChar<S extends string, C extends string> =
  C extends ''
  ? never
  : S extends `${infer Head}${infer Tail}`
    ? Head extends C
      ? DropChar<Tail, C>
      : `${Head}${DropChar<Tail, C>}`
    : S;
かしかし

MinusOne

問題

筆算の要領でやる

  • 最後の桁が 0 なら上の桁から1引いて 9 にする
  • 最後の桁が 0 以外なら一の位から1引く

これで数字を意味する文字列の生成まではできたけど、ここからどうやって number にするんだろう

type NumChar = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';
type CharMinusOne = {
  '0': '9',
  '1': '0',
  '2': '1',
  '3': '2',
  '4': '3',
  '5': '4',
  '6': '5',
  '7': '6',
  '8': '7',
  '9': '8',
};

type OmitFirst<T extends string> = T extends `0${infer U}` ? U : T;

type StringMinusOne<T extends string> =
  T extends `${infer Num10}${NumChar}`
  ? T extends `${Num10}${infer Num1}`
    ? Num1 extends NumChar
      ? Num1 extends '0'
        ? OmitFirst<`${StringMinusOne<Num10>}9`>
        : `${Num10}${CharMinusOne[Num1]}`
      : ''
    : ''
  : never;

type Result1 = StringMinusOne<'1'>;
// type Result1 = "0"
type Result55 = StringMinusOne<'55'>;
// type Result55 = "54"
type Result100000 = StringMinusOne<'100000'>;
// type Result100000 = "99999"

array['length'] を使って変換できるなあと思った。
ただし、 1000 を超えると再帰制限によってエラーになる。

type NumStringToAnyArray<T extends string, Acc extends any[] = []> =
  T extends '1'
  ? Acc
  : NumStringToAnyArray<StringMinusOne<T>, [any, ...Acc]>;

type MinusOne<T extends number> =
  NumStringToAnyArray<`${T}`> extends [any, ...(infer MinusOneArray)]
  ? MinusOneArray['length']
  : 0;

type Result1000 = MinusOne<1000>;
// type Result1000 = 999
type Result1001 = MinusOne<1001>;
// error: Type instantiation is excessively deep and possibly infinite.(2589)

十進数であることを使うと繰り返しの回数が桁数になるので、（たぶん）1000桁くらいまで再帰制限の問題を無視できる。

type NumCharToArray = {
  '0': [],
  '1': [any],
  '2': [any, any],
  '3': [any, any, any],
  '4': [any, any, any, any],
  '5': [any, any, any, any, any],
  '6': [any, any, any, any, any, any],
  '7': [any, any, any, any, any, any, any],
  '8': [any, any, any, any, any, any, any, any],
  '9': [any, any, any, any, any, any, any, any, any],
};

type Repeat10<T extends any[]> = [
  ...T,
  ...T,
  ...T,
  ...T,
  ...T,
  ...T,
  ...T,
  ...T,
  ...T,
  ...T
];

type NumStringToAnyArray<T extends string> =
  T extends `${infer Num10}${NumChar}`
  ? T extends `${Num10}${infer Num1}`
    ? Num1 extends NumChar
      ? Num10 extends ''
        ? NumCharToArray[Num1]
        : [...NumCharToArray[Num1], ...Repeat10<NumStringToAnyArray<Num10>>]
      : never
    : never
  : never;

type MinusOne<T extends number> =
  NumStringToAnyArray<`${T}`> extends [any, ...(infer MinusOneArray)]
  ? MinusOneArray['length']
  : 0;

引く数を 1 だけでなく、一般化してみる。
ペアノ算術と似ているね（ただし T < U のときは never とする）。

type MinusByArray<T extends any[], U extends any[]> =
  U extends [any, ...(infer NextU)]
  ? T extends [any, ...(infer NextT)]
    ? MinusByArray<NextT, NextU>
    : never
  : T['length']

type Minus<T extends number, U extends number> =
  MinusByArray<NumStringToAnyArray<`${T}`>, NumStringToAnyArray<`${U}`>>

type MinusOne<T extends number> = Minus<T, 1>;

数え上げでやる方法だと再帰制限を突破するのが難しいかな...

type MinusOne<T extends number, Acc extends any[] = []> =
  [any, ...Acc]["length"] extends T
  ? Acc['length']
  : MinusOne<T, [any, ...Acc]>;

type Result1001 = MinusOne<1001>;
// error: Type instantiation is excessively deep and possibly infinite.(2589)
かしかし

NumStringToAnyArray は先頭から計算したほうが楽だな。

参考
https://github.com/type-challenges/type-challenges/issues/8644

type NumStringToAnyArray<T extends string, Acc extends any[] = []> =
  T extends `${infer Head}${infer Tail}`
  ? Head extends NumChar
    ? Tail extends ''
      ? [...Acc, ...NumCharToArray[Head]] 
      : NumStringToAnyArray<Tail, Repeat10<[...Acc, ...NumCharToArray[Head]]>>
    : never
  : never;
かしかし

PickByType

問題

T[Key] extends U なる Key のみ採用するといい。

type PickByType<T, U> = {
  [Key in keyof T as (T[Key] extends U ? Key : never)]: T[Key]
};

StartsWith

問題

type StartsWith<T extends string, U extends string> = T extends `${U}${infer _}` ? true : false;

EndsWith

問題

わざわざ出題するのだから StartsWith と同じ方法でできないのかと思ったけど問題なくできた。

type EndsWith<T extends string, U extends string> = T extends `${string}${U}` ? true : false;

PartialByKeys

問題

Omit と Pick を使って K に含まれる/含まれないプロパティ名を分離する。
& を使って交差型を作ると型として一致しないので、すでに作った Merge を使う。

type PartialByKeys<T extends Record<string, any>, K extends string = string> =
  Merge<Omit<T, K>, Partial<Pick<T, Extract<K, keyof T>>>>;
かしかし

Mutable

問題

readonly や ? は + と - を使って指定の付け外しができるらしい。
+/- の記号なしで使うと + の意味で解釈されるらしい。

https://www.typescriptlang.org/docs/handbook/2/mapped-types.html#mapping-modifiers

Required の定義を見ると確かに -? を使ってる。

type Required<T> = { [P in keyof T]-?: T[P]; }

type Mutable<T extends Record<any, any>> = {
  -readonly[Key in keyof T]: T[Key]
};

OmitByType

問題

PickByType の逆

type OmitByType<T, U> = {
  [Key in keyof T as (T[Key] extends U ? never : Key)]: T[Key]
};

ObjectEntries

問題

Distributive conditional types を使ってこうやって解いたらうまくいかなかった。

type ObjectEntries<T, K extends keyof T = keyof T> =
  K extends any
  ? [K, T[K]]
  : never;

2つ目の Partial を使うケースでうまくいかないので、 Required で対処することにした。
これもうまくいかなかった。

type ObjectEntries<T, K extends keyof T = keyof T> =
  K extends any
  ? [K, Required<T>[K]]
  : never;

3つ目の { key?: never } が never になってしまう。
optional でプロパティの型が undefined なケースだけ対処して完了

type ObjectEntries<T, K extends keyof T = keyof T> =
  K extends any
  ? [
      K,
      Required<T>[K] extends never
      ? undefined
      : Required<T>[K]
    ]
  : never;
かしかし

Shift

問題

type Shift<T extends any[]> =
  T extends [any, ...(infer Tail)] ? Tail : [];

Tuple to Nested Object

問題

type TupleToNestedObject<T, U> =
  T extends [infer Head, ...(infer Tail)]
  ? Record<Head & string, TupleToNestedObject<Tail, U>>
  : U;

Tuple to Nested Object

問題

type TupleToNestedObject<T, U> =
  T extends [infer Head, ...(infer Tail)]
  ? Head extends string
    ? Record<Head, TupleToNestedObject<Tail, U>>
    : never
  : U;

他の人の解答見て気づいたけど、交差型を使うと Head extends string の判定しなくていいのか。
気づきがあった

type TupleToNestedObject<T, U> =
  T extends [infer Head, ...(infer Tail)]
  ? Record<Head & string, TupleToNestedObject<Tail, U>>
  : U;

Reverse

問題

type Reverse<T extends any[]> =
  T extends [infer Head, ...(infer Tail)]
  ? [...Reverse<Tail>, Head]
  : [];
かしかし

Flip Arguments

問題

Reverse を使う。

type FlipArguments<T extends (...args: any) => any> =
  T extends (...args: infer Args) => infer ReturnType
  ? (...args: Reverse<Args>) => ReturnType
  : never;

FlattenDepth

問題

MinusOne を使って次のように実装したら最後のケースでうまくいかなかった。

type FlattenDepth<T extends any[], U extends number = 1> =
  U extends 0
  ? T
  : T extends []
  ? []
  : T extends [infer Head, ...(infer Tail)]
  ? Head extends any[]
    ? Tail extends any[]
      ? [...(FlattenDepth<Head, MinusOne<U>>), ...(FlattenDepth<Tail, U>)]
      : never
    : [Head, ...(FlattenDepth<Tail, U>)]
  : [T];

FlattenDepth<[1, [2, [3, [4, [5]]]]], 19260817>;
// error: Type produces a tuple type that is too large to represent.(2799)

MinusOne が与えられた長さの配列を生成する都合上、あまり大きな値は扱えない。
同様に、 FlattenDepth で与えるオブジェクトも深くならないので、現在展開した深さを管理する配列 V を使って実装する。
展開するたびに、 V の長さを1ずつ増やしていく。

type FlattenDepth<T extends any[], U extends number = 1, V extends any[] = []> =
  V['length'] extends U
  ? T
  : T extends [infer Head, ...(infer Tail)]
  ? Head extends any[]
    ? [...(FlattenDepth<Head, U, [...V, any]>), ...(FlattenDepth<Tail, U, V>)]
    : [Head, ...(FlattenDepth<Tail, U, V>)]
  : T;
かしかし

BEM style string

問題

Distributive conditional types を使って E と M を分配する。

type BEM<B extends string, E extends string[], M extends string[]> =
  `${
    B
  }${
    E[number] extends never ? '' : `__${E[number]}`
  }${
    M[number] extends never ? '' : `--${M[number]}`
  }`;

InorderTraversal

問題

次のように実装しようとしたらエラーになる

type InorderTraversal<T extends TreeNode | null> =
  T extends TreeNode
  ? [
      ...InorderTraversal<T["left"]>,
      T["val"],
      ...InorderTraversal<T["right"]>
    ]
  : [];

// error: Type instantiation is excessively deep and possibly infinite.(2589)
// error: Expression produces a union type that is too complex to represent.(2590)

こうするとエラーが無くなるんだけどよくわからない。

type InorderTraversal<T extends TreeNode | null> =
  [T] extends [TreeNode]
  ? [
      ...InorderTraversal<T["left"]>,
      T["val"],
      ...InorderTraversal<T["right"]>
    ]
  : [];
かしかし

Flip

問題

type Flip<T extends Record<any, string | number | boolean>> = {
  [Key in keyof T as `${T[Key]}`]: Key
};

Fibonacci Sequence

問題

フィボナッチ数列とは次の3式で定義される数列。

F_{n+2} = F_n + F_{n+1} \\ F_0 = 0 \\ F_1 = 1

配列の長さが F_n と F_{n+1} を意味する F_n と F_m を保持して再帰的に定義する。
Count は、 F_n がフィボナッチ数列の何項目を表しているかをカウントしていて、 T と比較されている。

type Fibonacci<T extends number, F_n extends any[] = [], F_m extends any[] = [any], Count extends any[] = []> =
  Count["length"] extends T
  ? F_n["length"]
  : Fibonacci<T, F_m, [...F_n, ...F_m], [any, ...Count]>;
かしかし

AllCombinations

問題

例題にはないけれど、入力の文字列の中で重複する文字があってもよいこととしてして回答する。

配列として使う index の Union type を作る Indices という型を定義する。

type Indices<T extends any[]> =
  T extends [any, ...(infer Tail)]
  ? Tail["length"] | Indices<Tail>
  : never;

Indices<['','','','']>;
// -> 0 | 1 | 2 | 3

これと Permutation を使うと全ての並び方の配列の Union type を作ることができる。
しかし、長さが元も文字列と一致する組み合わせしか作ることができない。
終了記号も順列を作るための要素として組み込むことで、すべての長さの順列を再現することができた。

type TerminateSymbol = -1;

type PermutationWithTerminateSymbol<U, V=U|TerminateSymbol, C=V> =
  V extends TerminateSymbol // 終了記号を見つけたら、それ以降を捨てる
  ? []
  : V extends any
  ? [V, ...PermutationWithTerminateSymbol<Exclude<C,V>>]
  : never;

Permutation<0|1|2>;
// -> [0, 1, 2] | [0, 2, 1] | [1, 0, 2] | [1, 2, 0] | [2, 0, 1] | [2, 1, 0]
PermutationWithTerminateSymbol<0|1|2>;
// -> [] | [2] | [1, 2] | [1] | [2, 1] | [0, 1, 2] | [0, 2, 1] | [0, 2] | [0] | [2, 0] | [1, 0, 2] | [1, 2, 0] | [0, 1] | [1, 0] | [2, 0, 1] | [2, 1, 0]

あとは文字の配列と順列のパターンから文字列を生成する BuildStringByIndex を使って次のように実装しておしまい。

type BuildStringByIndex<CharArray extends string[], Pattern extends number[]> =
  Pattern extends [infer Phead, ...(infer Ptails)]
  ? Ptails extends number[]
    ? `${CharArray[Phead & number]}${BuildStringByIndex<CharArray, Ptails>}`
    : never
  : '';

type AllCombinations<S extends string, CharArray extends string[] = StringToCharArray<S>, Pattern = PermutationWithTerminateSymbol<Indices<CharArray>>> =
  Pattern extends number[]
  ? BuildStringByIndex<CharArray, Pattern>
  : never;

Permutation を使わない方法も考えた。
文字列を文字（重複した文字を別として扱うために id となる数字を一緒に添えている）の Union type を作る StringToCharArrayWithId を実装する。

type StringToCharArrayWithId<S extends string, Count extends any[] = []> =
  S extends `${infer Head}${infer Tail}`
  ? [Head, Count["length"]] | StringToCharArrayWithId<Tail, [any, ...Count]>
  : never;`

StringToCharArrayWithId<"ABCDA">;
// -> ["A", 0] | ["B", 1] | ["C", 2] | ["D", 3] | ["A", 4]

Distributive conditional types を使って、これらの文字を一つずつ使いながら文字列を作っていく。
作っていく途中経過のすべての Union type を作れば完成。

type AllCombinationsSub<T, Acc extends string = '', U=T> =
  Acc
  | ( T extends [infer C, any]
    ? AllCombinationsSub<Exclude<U, T>, `${Acc}${C & string}`>
    : never);

type AllCombinations<S extends string> = AllCombinationsSub<StringToCharArrayWithId<S>>;

作ってから気づいたけど結局 Permutation と同じような実装になってるね。

かしかし

Greater Than

問題

Minus をそのまま使ったらよさそう。

type GreaterThan<T extends number, U extends number> =
  Minus<T, U> extends 0 | never ? false : true;

Zip

問題

type Zip<T extends any[], U extends any[], Acc extends any[] = []> =
  [T, U] extends [[infer Thead, ...(infer Ttail)], [infer Uhead, ...(infer Utail)]]
  ? Zip<Ttail, Utail, [...Acc, [Thead, Uhead]]>
  : Acc;

IsTuple

問題

次の点に注目する

  • never で false になるようにする
  • readonly か否かが結果に影響しないようにする
  • length プロパティの型は、 array は number で Tuple は特定の数値になる
type IsTuple<T> =
  [T] extends [never]
  ? false
  : T extends readonly any[]
  ? number extends T["length"]
    ? false
    : true
  : false;

Chunk

問題

T から Acc へ値を移していく。
Acc の長さが N に達したらリセットする。

type Chunk<T extends any[], N extends number, Acc extends any[] = []> =
  Acc["length"] extends N
  ? [Acc, ...Chunk<T, N>]
  : T extends [infer Head, ...(infer Tail)]
  ? Chunk<Tail, N, [...Acc, Head]>
  : Acc extends []
  ? []
  : [Acc];
かしかし

Fill

問題

現在の index を意味する Tuple である Count と、 Start と End の間である置き換えの対象かを決める Replace を使う。

  • Count が Start と一致すると Replace を true にする
  • Count が End と一致すると、それ以降はすべて置き換えなくてよい
  • Count が Start とも End とも一致しないときは Replace の状態によって置き換えるかどうかを決める
type Fill<
  T extends unknown[],
  N,
  Start extends number = 0,
  End extends number = T['length'],
  Count extends any[] = [],
  Replace extends boolean = false
> =
  Count["length"] extends End
  ? T
  : T extends [infer Head, ...(infer Tail)]
  ? [Start, Replace] extends [Count["length"], any] | [any, true]
    ? [N, ...Fill<Tail, N, Start, End, [any, ...Count], true>]
    : [Head, ...Fill<Tail, N, Start, End, [any, ...Count], false>]
  : [];

Trim Right

問題

TrimLeft と一緒

type TrimRight<S extends string> = S extends `${infer T}${' '|'\n'|'\t'}` ? TrimRight<T> : S;

Without

問題

T を先頭から U と一致しないか見ていく。
U が Tuple の場合は U[number] で Union type にする。

type Without<T extends any[], U extends any> =
  T extends [infer Head, ...(infer Tail)]
  ? Head extends (U extends any[] ? U[number] : U)
    ? Without<Tail, U>
    : [Head, ...Without<Tail, U>]
  : [];
かしかし

Trunc

問題

文字列が "." を含むならそれよりも前を、含まないならそのものを返す。

type Trunc<T extends number | string> =
  `${T}` extends `${infer Num}.${any}`
  ? Num
  : `${T}`;

IndexOf

問題

any を含むため、一致の検査が面倒くさい。
@type-challenges/utils の Equal を使う。

type IndexOf<T extends any[], U, Count extends any[] = []> =
  T extends [infer Head, ...(infer Tail)]
  ? Equal<Head, U> extends true
    ? Count["length"]
    : IndexOf<Tail, U, [any, ...Count]>
  : -1;

Equal の実装はこんな感じ

https://github.com/type-challenges/type-challenges/blob/991cbf5fe04d0b496af7048df81445f4b73537ea/utils/index.d.ts#L7-L10

typelevel-ts というライブラリでも同じ書き方がされている

https://github.com/gcanti/typelevel-ts/blob/886583dd3b0ef879b7a4ceee78c6f5c66537f651/src/index.ts#L21-L23

なぜこれで動作するのか考える。
まず、次のような差がある。

type a = string extends number ? 1 : 2
// type a = 2

type b = (() => string extends number ? 1 : 2)
// type b = () => string extends number ? 1 : 2

a のほうは string extends number ? 1 : 2 が計算されて 2 となっている。
一方 b のほうは、 () => string extends number ? 1 : 2 のままで計算が停止している。

おそらく、最後まで計算させないことがlenges/type-challenges/blob/991cbf5fe04d0b496af7048df81445f4b73537ea/utils/index.d.ts#L7-L10

typelevel-ts というライブラリでも同じ書き方がされている

https://github.com/gcanti/typelevel-ts/blob/886583dd3b0ef879b7a4ceee78c6f5c66537f651/src/index.ts#L21-L23

なぜこれで動作するのか考える。
まず、次のような差がある。

type a = string extends number ? 1 : 2
// type a = 2

type b = (() => string extends number ? 1 : 2)
// type b = () => string extends number ? 1 : 2

a のほうは string extends number ? 1 : 2 が計算されて 2 となっている。
一方 b のほうは、 () => string extends number ? 1 : 2 のままで計算が停止している。
だからどういうことかというと、よくわからなかった

ちなみに下のような実装ではうまくいかない。

type A = { name: string, age: number };
type B = { name: string } & { age: number };

export type WrongEqual1<X, Y> =
  (() => unknown extends Y ? 1 : 2) extends
  (() => unknown extends X ? 1 : 2) ? true : false;

export type WrongEqual2<X, Y> =
  (<C>() => C extends Y ? unknown : unknown) extends
  (<C>() => C extends X ? unknown : unknown) ? true : false;

type x = WrongEqual1<A, B>
// type x = true
type y = WrongEqual2<A, B>
// type y = true
type z = Equal<A, B>
// type z = false
かしかし

Join

問題

Tuple の長さが 2 以上か否かで分岐

type Join<T extends any[], U extends string | number> =
  T extends [infer First, infer Second, ...(infer Rests)]
  ? `${First & string}${U}${Join<[Second, ...Rests], U>}`
  : T extends [infer Char]
  ? Char & string
  : '';

LastIndexOf

問題

IndexOf を逆から操作するだけ

type LastIndexOf<T extends any[], U> =
  T extends [...(infer Init), infer Last]
  ? Equal<Last, U> extends true
    ? Init["length"]
    : LastIndexOf<Init, U>
  : -1;

Unique

問題

すでにできてた型を保持する U と、 Include を使って実装。

type Include<T extends any[], U> =
  T extends [infer Head, ...(infer Tail)]
  ? Equal<U, Head> extends true
    ? true
    : Include<Tail, U>
  : false;

type Unique<T extends any[], U extends any[] = []> =
  T extends [infer Head, ...(infer Tail)]
  ? true extends Include<U, Head>
    ? Unique<Tail, U>
    : [Head, ...Unique<Tail, [Head, ...U]>]
  : [];
かしかし

MapTypes

問題

最後のケース以外はこれで通る

type MapTypes<T, R extends { mapFrom: any, mapTo: any }> = {
  [Key in keyof T]: T[Key] extends R["mapFrom"] ? R["mapTo"] : T[Key]
};

MapTypes<{ name: string; date: Date }, { mapFrom: string; mapTo: boolean } | { mapFrom: Date; mapTo: string }>
// -> { name: string | boolean; date: string | boolean; }

Distributive conditional types で扱えるように、 Map を定義する。

type Map<R extends { mapFrom: any, mapTo: any }, T> =
  R extends { mapFrom: infer From, mapTo: infer To }
  ? From extends T
    ? To
    : never
  : never;

type MapTypes<T, R extends { mapFrom: any, mapTo: any }> = {
  [Key in keyof T]: Map<R, T[Key]> extends never ? T[Key] : Map<R, T[Key]>
};

Construct Tuple

問題

type ConstructTuple<L extends number, Acc extends unknown[] = []> =
  Acc["length"] extends L
  ? Acc
  : ConstructTuple<L, [unknown, ...Acc]>;

Number Range

問題

Fill と同じ方法でやろうとしたけどエラーになった。（48以上でエラーになる）

type NumberRange<L, H, Count extends any[] = [], InRange extends boolean = false> =
  Count["length"] extends H
  ? H
  : [Count["length"], InRange] extends [L, any] | [any, true]
  ? Count["length"] | NumberRange<L, H, [any, ...Count], true>
  : NumberRange<L, H, [any, ...Count], false>;

NumberRange<0, 140>;
// error: Type instantiation is excessively deep and possibly infinite.(2589)

0 から N までの Union type を返す ToN を定義し、 0~H \ 0~(L-1) を求める。

type ToN<N extends number, IncludeN extends boolean, Count extends any[] = [], Acc = never> =
  Count["length"] extends N
  ? IncludeN extends true
    ? N | Acc
    : Acc
  : ToN<N, IncludeN, [any, ...Count], Count["length"] | Acc>;

type NumberRange<L extends number, H extends number> =
  Exclude<ToN<H, true>, ToN<L, false>>;
かしかし

Combination

問題

候補のひとつUをとってきて、U そのものか U と残りの候補の Combination を足したものかを返す。

type Combination<
  T extends string[],
  U = T[number],
  Candidates = U
> =
  U extends U
  ? U | `${U & string} ${Combination<[], Exclude<Candidates, U>> & string}`
  : never;

Subsequence

問題

先頭から、取るか取らないかの二択を繰り返す。

type Subsequence<T extends any[]> =
  T extends [infer Head, ...(infer Tail)]
  ? Subsequence<Tail> | [Head, ...Subsequence<Tail>]
  : [];
かしかし

medium はおしまい！
hard 以降は別のスクラップでやる

このスクラップは2022/09/30にクローズされました