👋

TSで高階型を定義する

に公開
TypeScript
tech

TL;DR

前提知識

前提知識としてまずは型コンストラクタと高階関数を押さえておきます。

型コンストラクタ

type Age = number;
type Name = string;

上記の普通の型に対して以下は型コンストラクタと呼ばれます。

type ArrayA = Array<number>; // Array は型コンストラクタ

高階関数

const add = (x: number) => (y: number) => x + y;

これは高階関数と呼ばれ、関数を引数に取る関数や、関数を返す関数のことを指します。
これと似たような概念として高階型というものがあります。
高階型は「型コンストラクタを受け取って、別の型コンストラクタを返す」仕組みです。

高階型

const as = [1, 2, 3, 4, 5, 6]; // as :: number[]
const f = (a: number): string => a.toString();

const bs = as.map(f); // bs :: string[]
console.log(bs); // => [ '1', '2', '3', '4', '5', '6' ]

これは js の map 関数を使った例です。map 関数は配列に対して適用される高階関数であり、各要素に対して関数を適用し、新しい配列を生成します。
この map 関数を配列の prototype から別の interface で実装すると以下のようにできます。

interface MappableArray {
  readonly map: <A, B>(f: (a: A) => B, as: A[]) => B[];
}

// 上記をカリー化
interface MappableArray {
  readonly map: <A, B>(f: (a: A) => B) => (as: A[]) => B[];
}

また map 関数は Set や Map などにも実装できることが想像できます。

type MapForSet = <A, B>(f: (a: A) => B) => (as: Set<A>) => Set<B>;
type MapForMap = <A, B>(
  f: (a: A) => B
) => (as: Map<FixedKeyType, A>) => Map<FixedKeyType, B>;

こう見てみると何となく汎用的な interface にすることができそうに思います。
以下のようにしてみます。

interface Mappable<F> {
  readonly map: <A, B>(f: (a: A) => B) => (fa: F<A>) => F<B>;
}

しかし、これは「型 'F' はジェネリックではありません。」というエラーが出て機能しません。
上記の Mappable では F を F<A>や F<B>のように型パラメータを持つ型（型コンストラクタ）として使おうとしています。
TS では、型パラメータ F は具体的な型を表すものとして扱われるため、F が型コンストラクタとして扱えないことを意味しています。
つまり TS は「型コンストラクタを受け取って、別の型コンストラクタを返す = 高階型」をサポートしていません。

Lightweight Higher‑Kinded Polymorphism

defunctionalization（高階プログラムを一次関数に落とし込む手法）を利用し、次の３つの手順で HKT（高階型） を模倣します。

  1. 型コンストラクタを'Array', 'Set'などの一意な文字列リテラル ID に置換する
  2. Kind<ID, A>のような ユーティリティ型を定義
  3. ID ↔ 型コンストラクタを対応付ける Dictionary(URItoKind)を定義する
interface URItoKind<A> {
  Array: Array<A>;
  Set: Set<A>;
} // a dictionary for 1-arity types: Array, Set, Tree, Promise, Maybe, Task...
interface URItoKind2<A, B> {
  Map: Map<A, B>;
} // a dictionary for 2-arity types: Map, Either, Bifunctor...

type URIS = keyof URItoKind<unknown>; // sum type of names of all 1-arity types
// and so on, as you desire

type Kind<F extends URIS, A> = URItoKind<A>[F];

これらの型を使い Mappable を再定義します。
すると以下のように定義でき、任意の 1 項のコンストラクタに対して多相的に Mappable を定義し、異なるデータ構造に対してインスタンスを実装することができます。

// before
// interface Mappable<F> {
//   readonly map: <A, B>(f: (a: A) => B) => (fa: F<A>) => F<B>;
// }

// after
interface Mappable<F extends URIS> {
  readonly map: <A, B>(f: (a: A) => B) => (as: Kind<F, A>) => Kind<F, B>;
}

const mappableArray: Mappable<'Array'> = {
  // here `as` will have type A[], without any menthioning of the utility type `Kind`:
  map: (f) => (as) => as.map(f),
};
const mappableSet: Mappable<'Set'> = {
  // a little bit unfair — you can make it more efficient by iterating over the iterator for the set manually,
  // but the purpose of this article is not to make the implementation as efficient as possible, but to explain the concept
  map: (f) => (as) => new Set(Array.from(as).map(f)),
};

実際に動かしてみると以下のようになります。

const ma = mappableArray.map((a: number) => a.toString())([1, 2, 3]); // mm :: string[]
console.log('ma =', ma);
// ma = [ '1', '2', '3' ]

ここまで定義してきた Mappable は 関数型プログラミングで Functor と呼ばれます。
Functor は T 型と fmap 関数からなり、A => B関数を使用してT<A>をT<B>のように同じ型コンストラクタ内で、内部の値の型を変換することができます。

まとめ

今回は簡易的な HKT と Functor を実装しました。
次はIntro to fp-ts, part 2: Type Class Patternを読んでいきます。

GitHubで編集を提案

Discussion