Tkr Blog

TypeScriptで型レベルハイパー演算子

2019/04/12 typescript typelevelprogramming

この記事はTS3.4.3で動作確認をしています。

ハイパー演算子とは

hyper(1,a,b)=a+b
hyper(2,a,b)=a*b
hyper(3,a,b)=a^b
︙

のような演算子です(雑) 詳しくはWikipediaを見て下さい。

定義だけ貼っておきます。

hyper(1,a,b)=a+b
hyper(_,a,1)=a
hyper(i,a,1)=hyper(i-1,a,hyper(i,a,b-1))

型レベルタプル操作

型レベルのタプル操作を行うので以下の記事を読んでおくといいかもしれません。 TypeScript 3.0のExtracting and spreading parameter lists with tuplesで遊ぼう

ちなみに今回は上の記事の型レベルタプル操作などをまとめた自作ライブラリtypeparkを使いますが機能は上の記事の通りです。

再帰制限回避テク

FGが複雑な関数だと以下のような書き方をするとコンパイルエラーが発生することがあります。

type Hoge<T>=F<Cast<G<T>,any[]>>;

このような時は以下のように書き直すことで回避できます。

type Hoge<T>=F<G<T> extends infer X?Cast<X,any[]>:X>;

方針

  • 筋肉で全列挙コードを書くと言った事は一切しない
  • 数値リテラル型3つを受け取って数値リテラル型1つを返す関数を実装する
  • 数が大きいと色々な制限に引っかかって死ぬけど気にしない

実装

数値リテラルを直接扱うのは大変です。 そこでanyN個のタプル型を数値リテラル型のN代わりに使う_Hyper関数を実装しましょう。 例えば_Hyper<[any],[any,any],[any,any,any]>[any,any,any,any,any]です。

これは定義通りですね。 ところどころコンパイルエラー回避のテクニックを使っているくらいです。 数値リテラルの代わりにタプルを使っているのでA-1Tail<T>に、A+BConcat<A,B>と言った書き方が出来ます。

type _Hyper<I extends any[], A extends any[], B extends any[]> = {
  0: Concat<A, B>,
  1: A,
  2: _Hyper<Tail<I>, A, _Hyper<I, A, Tail<B>> extends infer X ? Cast<X, any[]> : never>,
}[I extends [any] ? 0 : (B extends [any] ? 1 : 2)];

では数値リテラルを受け取り数値リテラルを返す関数はどう実装したらいいでしょうか? タプル→数値リテラルと数値リテラル→タプルの変換が出来ればいいことが分かると思います。 前者はT["length"]と書くだけなので簡単です。 後者は以下のようなRepeat関数を使いましょう。

export type Repeat<T, N extends number, R extends any[]=[]> = {
  0: R,
  1: Repeat<T, N, Cons<T, R>>
}[R["length"] extends N ? 0 : 1];

これもtypeparkに含まれていますが、まだ解説してなかったので軽く解説しておきます。 要素TN個持つタプルを返す関数です。 結果値がRなのでRの長さがNになるまでTConsしています。

これでRepeat<any,N>と書くことで数値リテラル→タプルの変換が出来るようになりました。

ではHyper関数の実装です。

export type Hyper<I extends number, A extends number, B extends number>
  = _Hyper<Repeat<any, I> extends infer X ? Cast<X, any[]> : never, Repeat<any, A> extends infer X ? Cast<X, any[]> : never, Repeat<any, B> extends infer X ? Cast<X, any[]> : never> extends infer X ? Cast<X, any[]>["length"] : never;

ところどころコンパイルエラーを回避して実装しています。

Hyper<1, 1, 4>//5
Hyper<2, 5, 4>//20
Hyper<3, 2, 4>//16
Hyper<1, 100, 200>//数値が大きすぎてコンパイルエラー

kgtkr
Web Developer.