型レベルで【 #ゆめみからの挑戦状 ★第7弾】解いてみた


##  #ゆめみからの挑戦状 ★第7弾

最近株式会社ゆめみでは、 Twitter にて [#ゆめみからの挑戦状](https://twitter.com/hashtag/%E3%82%86%E3%82%81%E3%81%BF%E3%81%8B%E3%82%89%E3%81%AE%E6%8C%91%E6%88%A6%E7%8A%B6) という企画を定期開催しています
ゆめみの社員がプログラミングに関する問題を出して、皆さんに引用リツートで答えていただく、というものです

今回はその第7弾を **型レベル** で解けたのでその解説を書きます

https://twitter.com/yumemiinc/status/1578251283546664960?s=20&t=X9leciZTltP-DzxijGDmkg


PHPでの解説と回答例

https://qiita.com/fuwasegu/items/f93af8e256ae354883fd

## まずは素直に書いてみる

https://www.typescriptlang.org/play?#code/C4TwDgpgBAmhCGAnKBeKAmADO9AoXoksCiAsgPYB2wAFgDy5TFJQQAewElAJgM5SUArgFsARhEQAaRlArUa-dpx79ewRAEtKAcwDaAXVRRdAckwBGE5Khn0Vm5gDM9swBYXmAKweAbB4DsHgAcHgCcLuaYEZbWJuZ2+rgAfKgycrSKHFx8xloAZhKyVLSsWSpQapo61gB0dfmFAEoQwvBaWtrpCqXKOZUdBolMTAD8xgAGACQA3nBIAL4zXfPjtXVzZMX0G9bNre06XbxJQ8MAXMaJBODQAPKCwEYbXXQbSbgA9B-DAHojuEA

```ts
type Year = 2022

type YearMonth<
  Year extends number,
  Months extends string[] = ['01', '02', '03', '04', '05', '06', '07', '08', '09', '10', '11', '12']
> =
  Months extends [infer Month extends string, ...infer RemainingMonths extends string[]]
    ? [`${Year}${Month}`, ...YearMonth<Year, RemainingMonths>]
    : []

type Out = YearMonth<Year>
//   ^? type Out = ["202201", "202202", "202203", "202204", "202205", "202206", "202207", "202208", "202209", "202210", "202211", "202212"]
```

`Months` が最初の1つ目の要素 `string` と残りの月の `string[]` に型推論できるとき、 `${Year}${Month}` で文字連結して、残りの月も再帰的に評価する

素直に解いてみましたがいくつかダサい箇所があります

## 2桁の0埋め型

```ts
'01'
```

`'01'` のような2桁の0埋めをベタ書きしてしまっているところが、絶妙にダサいですね。

型レベルで2桁の0埋めをできるようにします

2桁の0埋めをするには、文字列が何桁か判定する必要があります

### 文字列が何桁か判定する

https://www.typescriptlang.org/play?#code/C4TwDgpgBAymA2BLYAeAKlCAPYEB2AJgM5RHABOieA5gHxQC8AUFFBtroSQAYAkA3lQBmEclACqAXwHDRUAGqTuLVlAD8UANriANFAB0huElTzaAXRWsAXFstNQkKAEFGsBMhQByQOGmgdW1AdCUvWiYAelDVAD01JgdwaBgKKmoAGXxqYAALdEwcfGJSJJp6BncTdFpNL3h0rK97R2gAITdEyho0mizvfyCQ8KiYoA

```ts
type Split<T extends string> =
  T extends `${infer U}${infer V}` // 1つ目の文字と残りの文字列に型推論
    ? [U, ...Split<V>] // できたら1つ目の文字と、残りを再帰的に配列に変換する
    : []

type A = Split<'文字列'>
//   ^? type A = ["文", "字", "列"]

type StringLength<T extends string> = Split<T>['length']

type B = StringLength<'文字列'>
//   ^? type B = 3
```

文字列のままでは桁数を得られないので、まずは文字の配列に変換します
その後、配列の `length` プロパティを見て桁数を得ます

### 0埋めする

https://www.typescriptlang.org/play?#code/C4TwDgpgBAymA2BLYAeAKlCAPYEB2AJgM5RHABOieA5gHxQC8AUFFBtroSQAYAkA3lQBmEclACqAXwHDRUAGqTuLVlAD8UANriANFAB0huElTzaAXRWsAXFstNQkWBSrUAMvmrAAFukw58YlIXGnoGWARkdFpNAHJ4Tx9Y+0doNAB3AHsAEQhqZAAtUUyAMUR4eD8OQJIySlDGFRgQ90TfNHpqrigARit1KG4ABgE0JX7bNCYHcGgAQUY2LNz84CLyUvLK2J7Y2iYAegPVAD01adSoACFFjJy8wuKyipQdob3D49YzpiA

```ts
type Split<T extends string> =
  T extends `${infer U}${infer V}`
    ? [U, ...Split<V>]
    : []

type StringLength<T extends string> = Split<T>['length']

type TwoDegitZeroFill<T extends string> =
  StringLength<T> extends 1
    ? `0${T}`
    : T

type A = TwoDegitZeroFill<'1'>
//   ^? type A = "01"

type B = TwoDegitZeroFill<'10'>
//   ^? type B = "10"
```

`TwoDegitZeroFill` 型は単純で、与えられた文字列が1桁だった場合、左に0をつけてあげます。それ以外の場合はそのまま返します

### 2桁の0埋め型を組み込む

https://www.typescriptlang.org/play?#code/C4TwDgpgBAmhCGAnKBeKAmADO9AoXokUAymADYCWwAPACpQQAewEAdgCYDOUnwiFrAOYA+VLihR6TFh24ADACQBvAQDMIyAKoBfZWo1QAatrniJUAPxQA2poA0UAHTPSlGoeEBdMxIBcN7wJwaGI+AUEAGTZBYAALOgZmNi4eMKFRNFcqOmFrAHIyaLi8wMJoWgB3AHsAEQhBKgAtDSqAMQoyMgTpZO5efnSxCVCByKL42lEe2SgARh9LKDlMZVoTBf9afDLYBEQAWSrWOOozOCREmRTWAFcAWwAjDTszQ+PY7mnr+6fEa09UDZZg50A4AMwOAAsDgArA4AGwOADsDgAHA4AJwOWaYbHAubobwZV5HOKfJIzaz6ZBvOKXXpQW6PZ5OZzUqAAJQgd3gAnCtI+9JmTN+-285kW1kUSnOiF0SkqtXqTRa7U61GlApMwhMDmcjllAuosocXJ5fKEAs4Xg2AW2wSgAHkbsBAYbSfFZcJcAB6H3mAB6FlwQA

```ts
type Year = 2022

type Split<T extends string> =
  T extends `${infer U}${infer V}`
    ? [U, ...Split<V>]
    : []

type StringLength<T extends string> = Split<T>['length']

type TwoDegitZeroFill<T extends string> =
  StringLength<T> extends 1
    ? `0${T}`
    : T

type YearMonth<
  Year extends number,
  Months extends number[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
> =
  Months extends [infer Month extends number, ...infer RemainingMonths extends number[]]
    ? [`${Year}${TwoDegitZeroFill<`${Month}`>}`, ...YearMonth<Year, RemainingMonths>]
    : []

type Out = YearMonth<Year>
//   ^? type Out = ["202201", "202202", "202203", "202204", "202205", "202206", "202207", "202208", "202209", "202210", "202211", "202212"]
```

2桁の0埋め型ができたので多少型レベル感が増しました（？）がまだダサいですね

## 1から12までの配列を型レベルで生成する

1から12までの配列を作るには、要素が12個の配列を作ることと、要素の値をインクリメントすることができなければなりません

https://www.typescriptlang.org/play?#code/C4TwDgpgBAggTnAhiAYgezgGQgOwObAAWAPAFBRTb5FQQAewuAJgM5Q4CuAtgEYRwAaclABKENvUY5WUDtIgAzAJY4ITANoBdKAF4oW0gD5do8eoDkAG1wFC57ZOZsqt4QH5TLYQC5YCZOhYNkTELkQC+gB00WIsEXJMiipqmoakpKCQsCbwSKgYYSQAzGkA9KUUUAB6bulAA

### 指定された長さの配列を生成する型

```ts
type ArrayForLength<
  Length extends number,
  Res extends undefined[] = []
> = Res['length'] extends Length // 指定した長さの要素になったら
  ? Res // 配列を返す
  : ArrayForLength<Length, [...Res, undefined]> // それまで要素を1つずつ増やす

type A = ArrayForLength<3>
//   ^? type A = [undefined, undefined, undefined]
```

関数にしてみるとこのような処理の評価をイメージするとわかりやすいかと思います

```ts
const arrayForLength = (length: number, res: undefined[] = []) =>
  res.length === length
    ? res
    : arrayForLength(length, [...res, undefined])
```

### インクリメント型

型レベルでは数値の計算はできません
なので、配列の長さを使ってインクリメントします

https://www.typescriptlang.org/play?#code/C4TwDgpgBAkgdgYwE4QLYTsAPAFShAD2AwBMBnKOAV1QCMIkAaKAVXyNIqrgGs4B7AO5wA2gF0oAXijiAfFIBQUViIDkAGwwBzYAAtVEwsTjkoOJcqgB+GQDp7LZtz5C4YtZrg79Yi8oBcsIgo6Ji4zCL2to5QzgLCYrIKyaCQUACCUkHIaBjYAIwAzEkA9CWWAHpWCkA

```ts
type Increment<T extends number, U extends unknown[] = []> =
  U['length'] extends T // 指定した長さになったら
    ? [...U, unknown]['length'] // 要素を1つ追加して、配列の長さを返す
    : Increment<T, [...U, unknown]> // 再帰的に配列に要素を1つずつ詰める


type A = Increment<13>
//   ^? type A = 14
```

再帰的に配列に要素を詰めていって、指定した長さになったら、最後に要素を1つ追加してその配列の長さを返します

関数で書くとこのようなイメージです

```ts
const increment = (t: number, u: undefined[] = []) =>
  u.length === t
    ? [...u, undefined].length
    : increment(t, [...u, undefined])
```

※ただしこの方法にはいくつか制限があります

```ts
// 配列の要素数がマイナスになることはないので無限ループしてしまう
type B = Increment<-1>
// Type instantiation is excessively deep and possibly infinite.

// 配列の要素数が浮動小数点数になることはないので無限ループしてしまう
type C = Increment<2.3>
// Type instantiation is excessively deep and possibly infinite.

// 数が大きすぎると型の再帰回数の制限に引っかかってしまう
type D = Increment<1000>
// Type instantiation is excessively deep and possibly infinite.
```

### 範囲の配列型

「指定された長さの配列を生成する型」と「インクリメント型」を合わせて指定された範囲の配列を作る型をつくります

https://www.typescriptlang.org/play?#code/C4TwDgpgBAkgdgYwE4QLYTsAPAFShAD2AwBMBnKOAV1QCMIkAaKAVXyNIqrgGs4B7AO5wA2gF0oAXijiAfFIBQUViIDkAGwwBzYAAtVEwsTjkoOJcqgB+GQDp7LZtz5C4YtZrg79Yi8oBcsIgo6Ji4zCL2to5QzgLCYrIKCqCQUACCSEgAhiAAStleEFgWAMrA2UjA7Mam1HQMjBYAoiY1nJQ09EwWeRAURh313eJSMr7y0uWV1YMmFK0kFjaR9n1kzNNVvgEZWbkFRVjwyGgY2FvAssyLEVHrmxXbSSng0OljmTn5hVrFAIzMf4AJiSAHowZYAHpWBRAA

```ts
type Increment<T extends number, U extends unknown[] = []> =
  U['length'] extends T
    ? [...U, unknown]['length']
    : Increment<T, [...U, unknown]>

type ArrayRange<
  Start extends number,
  End extends number,
  Res extends number[] = []
> = Start extends End // Start と End が一致したら
  ? [...Res, Start] // 今までの配列に Start を追加して返す
  : ArrayRange<Increment<Start>, End, [...Res, Start]> // 再帰的に Start をインクリメントしつつ配列に要素を詰める

type A = ArrayRange<1, 12>
//   ^? type A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
```

関数で書くとこのようなイメージです

```ts
const arrayRange = (start: number, end: number, res: number[] = []) =>
  start === end
    ? [...res, start]
    : arrayRange(start + 1, end, [...res, start])
```

### 範囲の配列型を組み込む（完成）

https://www.typescriptlang.org/play?#code/C4TwDgpgBAmhCGAnKBeKAmADO9AoXokUAkgHYDGiEAthKcADwAqUEAHsHQCYDOUpAV2oAjCIgA0UAKqsO3PgNIBrUgHsA7qQDaAXVRRdAPlS4o0rQHIANnQDmwABYW97TqV5Qmps1AD8BgDogqUlFFQ1SHUsbUnsnHW8zAC4SCipaemZJLSCAkKgwtU0dQ3xCaABBRER4EAAleFiIBm8AZWAkYFk3D0ERMXFvAFF3bvl+IVEJbzqIPldxvqndfV1cYzR2zrH3PhGub38coNmeSS3EYATkqCqa+sbbZrJKGjpGC+BDSX3s3NPzh1LiUyuBoK0wFYAJaMFgLXZQHjARBQ2IbbxwuQIgAGABIAN6ogBmYmkAF8CcTSQA1MnYxJ+Az5XIQ6GMamGa4+FJrAhgqDtFGxAAydkczB2HiRQtsGwFkJhzEM0TF8VBRCY6lUABEILYYQAtMSqABiUKsVgl8KlyNRspMZkFdtFsXFTGM1r4AEYGf5sZgCUw6QyUl4+UQ4EgALKqegOBiR5Ceib9CRQGNx+ZY3qTMQrNB3WoNJoML2SL3oQzoswZxxZnp8LRU5C1hySvhLAZQXLNqCzajwVF21v1xa5xC6LlmI54-GJin4zU6vWG41mi0MWetumGOmSXKJ1sJhBp-uD0jD2N1zkhgwJcPQADyAi6aEPV-jidKAHpvz4AHq+LgQA

```ts
type Year = 2022

type Increment<T extends number, U extends unknown[] = []> =
  U['length'] extends T
    ? [...U, unknown]['length']
    : Increment<T, [...U, unknown]>

type ArrayRange<
  Start extends number,
  End extends number,
  Res extends number[] = []
> = Start extends End
  ? [...Res, Start]
  : ArrayRange<Increment<Start>, End, [...Res, Start]>

type Split<T extends string> =
  T extends `${infer U}${infer V}`
    ? [U, ...Split<V>]
    : []

type StringLength<T extends string> = Split<T>['length']

type TwoDegitZeroFill<T extends string> =
  StringLength<T> extends 1
    ? `0${T}`
    : T

type YearMonth<Year extends number, Months extends number[] = ArrayRange<1, 12>> =
  Months extends [infer Month extends number, ...infer RemainingMonths extends number[]]
    ? [`${Year}${TwoDegitZeroFill<`${Month}`>}`, ...YearMonth<Year, RemainingMonths>]
    : []

type Out = YearMonth<Year>
//   ^? type Out = ["202201", "202202", "202203", "202204", "202205", "202206", "202207", "202208", "202209", "202210", "202211", "202212"]
```

`Months` の初期値を `ArrayRange<1, 12>` に変えて完成です！

## 余談

この記事を書いていて気づきましたが別なアプローチをしてもおもしろそうな部分がありました

```ts
type TwoDegitZeroFill<T extends string> =
  T extends `${infer _}${infer _}${infer _}`
    ? T
    : `0${T}`
```

「何かしらの文字と、何かしらの文字と、空文字列」に型推論できたら、そのまま返す、それ以外は0を付けて上げるでも、今回の場合表現できます
`infer _` が3つも並んでいて強烈ですねｗ

## 感想

もとのお題がPHPの問題で、しかも制約の「処理はワンライナーで書かなければいけない（改行は可能）」を無視してしまっているので、完全にレギュレーション違反です
しかしコードを実行せずに型レベルで解けるTypeScriptの型システムはとてもおもしろいと思いました

これからも隙きあらば [#ゆめみからの挑戦状](https://twitter.com/hashtag/%E3%82%86%E3%82%81%E3%81%BF%E3%81%8B%E3%82%89%E3%81%AE%E6%8C%91%E6%88%A6%E7%8A%B6) を型レベルで解いてみようと思います！