TypeScriptとHigher Kinded Type(高階型)

関数型はデータ型というものを非常に重視する。
データ型によって値をモデリングし、どういった性質のデータなのかを表現する。
更に型システムと組み合わせることでデータ型はさらなる力を得る。

型システムによってデータ型を抽象化するときに利用する型の一つにHigher Kinded Type(高階型)がある。
tsでは高階型は直接サポートされていないがそれをエンコードすることはできる。

この記事では高階型とはそもそも何なのか、それをTypeScriptでどの様に実現するかを説明する。

高階型とは

まずは馴染み深い値から始めよう。
値とは言ってしまえば生データのことである。
最も具体的な概念で、取り扱いやすい。

const name = "john";
const one = 1;
const oneAndTwo = [1, 2];

変数定義の右側を見るとただのデータで、馬鹿らしいほど理解しやすい。
当たり前じゃん、という感じだと思う。

仮に誰かにtシャツの値段を聞かれたとしよう。
それに5000円と答えると彼らはたちどころに理解すると思う。

だけど「円」ってなに?と聞かれるとちょっと質問としては難しくなる。
このようなときに役に立つのが型という概念である。

型、properな型

const name: string = "john";
const one: number = 1;
const oneAndTwo: Array<number> = [1, 2];

さっきの変数定義に型を付けてみる。
この様に値に対して直接付与できるようなものを単に型、もしくは協調してproperな型などと言ったりする。
ここで言うとstring、number、Array<number>はproperな型である。

properな型は値よりは上位の概念である。
型は値を生み出すためにある意味「インスタンス化」できて、逆に値は型の特定の「インスタンス」である。

stringはあらゆるstringリテラル(“a”, “ab”, “hello”, …)を生み出すことができる。
値の説の例では「円」は1円、3円、99999円…などにインスタンス化できる。

properな型を考えることで抽象度のレベルが上がった。
もっと抽象度を上げてみよう。

first-order type

前の例だとArray<number>はproperな型だと言った。
しかしそれではArrayとはなんだろう?
例えば以下の様なコードを考えてみる。

const arr: Array = [1, 2, 3];
// error TS2314: Generic type 'Array<T>' requires 1 type argument(s).

これはコンパイルできない。
値がArrayであるということは許されない。
コンパイラはarrが「何か」の配列、つまりArray<_>のような感じで宣言して欲しがっている。

「何か」の配列であることを示すためにArrayにはスロットが一つ用意されている。
properな型がほしいのならスロットに何かを入れる必要がある。
これは見方を変えると型を返す関数へのパラメータのようなものである。
この様にスロットを埋めると型が返るようなものにはtype constructorという名前がついている。
type constructorにはArray<_>やPromise<_>、Map<_, _>などがある。
ただ面白いのがMapだけがちょっと違う。
Mapをconstructするにはkeyとvalueのための2つの型パラメタを埋める必要がある。

そしてtype constructorによってproperな型を生み出す事ができるような型、つまりArrayやPromise、Mapのことをfirst-order typeなどという。
first-order typeによってproperな型からまた一つ抽象度が上がった。
ここから先はTypeScriptでは素直には抽象化の道を進めないのだが、一旦それは忘れてもう少し考えてみる。

first-order typeより上の抽象

これまでの抽象化を眺めてみると、一つ前のステップを抽象したものである。

[1]  -> number[]    -> number         ->    ???
// 値   properな型    first-order type       ???

次に仮にできたとして、first-order typeを抽象化したものを考えると以下のようなものになる。

type Mappable<F<_>> = ...

F<_>という見慣れないものに集中するために、一旦Mappableが何なのかは考えないことにする。
F<_>とは一つだけスロットの空いたfirst-order typeのことである。
例えばArray<_>やPromise<_>。

このようなときMappableのことをsecond-order typeとか言ったりする。
second-order typeはスロットとして型を抽象化したものを更に抽象化したものである。
意味が不明だと思うのでもうちょっと説明する。

Higher Kinded Type

ここでようやくHigher Kinded Type(高階型)の登場である。
type constructorを受け取るような型のことを高階型と呼ぶ。

type constructorは型を受け取って型を返す型レベルの関数だとみなせる。
type constructorと関数を少し見比べて見る。
type constructorであるArray<_>は型レベルの関数である。

T => Array<T>

例えばstringという実態を入れ込めばproperな型が返ってくる。

string => Array<string>

しかしここで返すものがproperな型ではなく、他のfirst-order typeだとするとどうなるだろう。
Mappableがまさにそのようなものである。

F<_> => Mappable<F<_>>

型レベルの関数(F<_>)をとって別の型レベルの関数を返している。
値レベルの似たようなお話として高階関数がある。
関数を引数に取るような関数のことを高階関数と呼ぶ。
なんだか似ている。

実際に使うときには例えばArray<_>などを埋め込むことができる。

Array<_> => Mappable<Array<_>>

*記法とkind

型の型はkindと呼ばれ、*を用いてそれを視覚的に表現できる。

  • stringやnumberは*のkindでオーダーが0
  • Array<_>は* -> *のkind、つまり一つの型を受け取りproperな型を受け取るオーダー1のkind。例えばstringをとってArray<string>を生み出す。
  • Map<_, _>は* -> * -> *のkind、つまり2つのオーダー0の型を受け取りproperな型を生むオーダー1な型。例えばstringとnumberを受け取ってMap<string, number>を生み出す。
  • (仮にそう書けたとして)Mappable<F<_>>は(* -> *) -> *のkind、つまりオーダー1の型を受け取ってproperな型を生み出すオーダー2な型。

なぜ高階型が必要なのか

もし高階型が可能だとしたら以下のようなコードが書ける。

type Mappable<F<_>> = {
  map: <A, B>(fa: F<A>) => (f: A => B) => F<B>
}

FをArrayやPromiseなどのfirst-order typeと読み替えて見ると理解しやすいと思う。
mapはある種Arrayなどを値を保持するコンテナとして認識して、中の値を操作するような処理である。
Promiseだとthenが似たような意味を持つ。

この型定義はすべてのfirst-order typeに対してmap関数のインターフェースを定義している。
高階型を定義すればいろんな異なるfirst-order typeに対して型安全に関数を一挙に定義できる。
ここでは深く潜らないが、これは関数型では広く使われるテクニックである。

高階型のTypeScriptでのエンコード

残念なお知らせ

ここまで高階型が何なのかを学んできたが、ここで残念なお知らせがある。
高階型はTypeScriptでは直接記述することができない。
つまり上で書いたようなMappable<F<_>>のようなコードは書くことができない。

そうであるならば上で学んだことは無駄なのだろうか?
そうではない。
高階型をTypeScriptでエミュレートする方法がある。
それを学ぼう。

ここで説明する高階型の実装はTypeScriptの関数型ライブラリであるfp-tsの方法に基づいている。

問題設定

ここでは以下のようなインターフェースFunctorを動作させることを目標にする。

interface Functor {
  map: <A, B>(f: (a: A) => B, fa: ?) => ?;
}

これは上で出てきたMappableの様に何らかのコンテナの中に入っている値を操作するような処理を表現している。
つまりF<A> => F<B>のような操作のことである。
ただし直接高階型を表現できないので、いまは?で該当の部分を置いている。

これを型クラスとして、何らかのデータ型に対してFunctor型クラスのインスタンスを定義できればゴールである。
型クラスについて理解していない人は以下の記事を参照してほしい。

Functor化するデータ型

Functorのインスタンスを作成する対称のデータ型としてOptionというデータ型を考える。

// opt.ts

// 値が何も無いことを表す
export class None {
  readonly tag: "None" = "None";
}

// 何かしらA型の値を保持していることを表す
export class Some<A> {
  readonly tag: "Some" = "Some";
  constructor(readonly value: A) {}
}

export type Option<A> = None | Some<A>;

export const none: Option<never> = new None();

export const some = <A>(a: A): Option<A> => {
  return new Some(a);
};

// Optionに対してのmap処理
// Someとして中身がある場合には関数fを使用して値を変換する
// Noneの場合には何もせずにそのままNoneを返す
const map = <A, B>(f: (a: A) => B, fa: Option<A>): Option<B> => {
  switch (fa.tag) {
    case "None":
      return fa;
    case "Some":
      return some(f(fa.value));
  }
};

Option<A>はSomeもしくはNoneで値があるかないかを表す。
使い方は以下のような感じ。

const double = (n: number): number => n * 2;
const len = (s: string): number => s.length;

console.log(map(double, some(1))); // Some { tag: 'Some', value: 2 }
console.log(map(double, none)); // None { tag: 'None' }
console.log(map(len, some(2))); // <= static error: Type 'number' is not assignable to type 'string'

こいつにたいしてFunctorのインスタンスを定義したい。

高階型のエミュレート

何度も述べたように高階型を直接表現できないが、以下の様な型によって模すことはできる。

// hkt.ts

export interface HKT<F, A> {
  _URI: F
  _A: A
}

Fは対象のコンテナ型の識別子、例えばOptionなら”Option”のような文字列のことである。
そしてAはコンテナの中に格納される値の型を表している。
例えばHKT<“Option”, string>はOption<string>を表現しているといったような具合である。

HKTを用いれば今まではコードに落とし込めなかったFunctorの定義をコード化することができる。

// functor.ts

import { HKT } from "./hkt";

export interface Functor<F> {
  map: <A, B>(f: (a: A) => B, fa: HKT<F, A>) => HKT<F, B>;
}

HKTを用いてFunctorと関わることができるようにOptionを書き換えよう。

// opt.ts

// Optionの識別子
export const URI = "Option";

export type URI = typeof URI;

export class None {
  readonly _URI!: URI;
  readonly _A!: never
  readonly tag: "None" = "None";
}

export class Some<A> {
  readonly _URI!: URI;
  readonly _A!: A
  readonly tag: "Some" = "Some";
  constructor(readonly value: A) {}
}

export type Option<A> = None | Some<A>;

export const none: Option<never> = new None();

export const some = <A>(a: A): Option<A> => {
  return new Some(a);
};

const map = <A, B>(f: (a: A) => B, fa: Option<A>): Option<B> => {
  switch (fa.tag) {
    case "None":
      return fa;
    case "Some":
      return some(f(fa.value));
  }
};

このようにOptionを定義したことでOptionのFunctorインスタンスを定義できる。

export const option: Functor<URI> = {
  map,
};
// error TS2322: Type '<A, B>(f: (a: A) => B, fa: Option<A>) => Option<B>' is not assignable to type '<A, B>(f: (a: A) => B, fa: HKT<"Option", A>) => HKT<"Option", B>'.
//   Types of parameters 'fa' and 'fa' are incompatible.
//     Type 'HKT<"Option", A>' is not assignable to type 'Option<A>'.
//       Type 'HKT<"Option", A>' is missing the following properties from type 'Some<A>': tag, value
//
// map,

と思ったがまだできない。
なぜならHKTは表現上高階型を模しているだけで、実質的にはHKT<“Option”, A> = Option<A>ではないからだ。
この場合で言うとmapの引数faが適合していない。

エラーメッセージを見て?と思った人はいると思う。
なぜならFunctorのmapに対してOptionのmapを割り当てているはずなのにエラーではHKT<“Option”, A>がOption<A>に割り当てることはできないという逆のメッセージが出ているからだ。
これは型の変位(variance)という概念に関わるもので、気になる人は以下の記事を参照してほしい。

話を戻して、前述のFunctorインスタンスの定義を修正するにはOptionのmapをHKTを用いたものに書き換える必要がある。

const map = <A, B>(f: (a: A) => B, hfa: HKT<URI, A>): Option<B> => {
  const fa = hfa as Option<A>;
  switch (fa.tag) {
    case "None":
      return fa;
    case "Some":
      return some(f(fa.value));
  }
};

export const option: Functor<URI> = {
  map, // コンパイルが通る
};

HKTの改善

以上でHKTを用いてOptionのFunctorインスタンスは定義できたがひとつ問題がある。
残念ながら以下のコードがHKT<“Option”, number>だと推論されてしまう。

const x = option.map(double, some(1)) // HKT<"Option", number>

これは嬉しくない。
理想的にはOption<number>だと推論されてほしい。
もっと言えば任意のAに対してHKT<“Option”, A>がOption<A>だと推論されてほしい。

この目的を達成するためにURI(=データ型の識別子)を実際のデータ型に変換するための型レベルの辞書URI2HKTを用意する。

export interface URI2HKT<A> {}

URI2HKTの使い方はTypeScript自体のinterface拡張機能を利用して、データ型が増えるたびにURI2HKTを拡張していく。
例えばOptionというデータ型を定義したならば、それを用いてURI2HKTを拡張する。

declare module "./hkt" {
  interface URI2HKT<A> {
    Option: Option<A>; // "Option"というリテラル型をOption<A>に紐付ける
  }
}

この様に拡張すればURI2HKTを用いてURIから実際の型を引っ張り出せる。

const a: URI2HKT<number>["Option"] = some(1); // Option<number>

URI2HKTを用いてHKTを改善する前に2つのヘルパー型を用意したい。

export type URIS = keyof URI2HKT<any>

export type Type<URI extends URIS, A> = URI2HKT<A>[URI]

URISはURI2HKTを拡張したデータ型の識別子のUnionである。
TypeはさっきOptionでやったようにURIから実際の型を取り出すヘルパー型である。
URIに対してURISの制約をかけることで関係ない型に対して使用できないようになっている。

const a: Type<"Option", number> = some(1); // Option<number>

これらを用いてFunctorを定義しなおせる。

export interface Functor<F extends URIS> {
  map: <A, B>(f: (a: A) => B, fa: Type<F, A>) => Type<F, B>
}

この定義を使用してOptionのインスタンスを定義しなおそう。

const map = <A, B>(f: (a: A) => B, fa: Option<A>): Option<B> => {
  switch (fa.tag) {
    case 'None':
      return fa
    case 'Some':
      return some(f(fa.value))
  }
}

export const option: Functor1<URI> = {
  map
}

const x = option.map(double, some(1)) // x: Option<number>

いい感じにHKTが表現できて、さらにちゃんと具体的な型まで推論されるようになった。

fp-tsの実際

fp-tsでも上の様にHKTを実現している。
更に* -> *なkind以外の* -> * -> *のkindに対してもHKT2などの様に定義されている。

https://gcanti.github.io/fp-ts/modules/HKT.ts.html

参考

  • https://gist.github.com/gcanti/2b455c5008c2e1674ab3e8d5790cdad5
fp-tsとMonoid fp-tsとoption ScalaのAuxパターン
View Comments
There are currently no comments.