【TypeScript】式木の美しき表現【解答編】
こんにちは、SHIFTビジネスプロセスアウトソーシンググループに所属しているShunkiです。 運用関連のお仕事でご飯を食べさせてもらっています。 プログラミングの理論面を調べて遊ぶのが趣味の1つです。 遊ぶさいは、Microsoftが誇るTypeScriptというプログラミング言語をよく使っています。
この記事は、題名の通り【TypeScript】に関する問いへの【解答】を示します。 問いの詳細は前回の記事をご覧ください。
流れ
前回の記事で載せたヒントに沿って解答の実装を示していきます。
TypeScriptの型を対象、関数を射とする圏を考える(より正確には圏とみなすために必要な性質を持った型と関数のみを以降の議論では扱う)。
べき乗関手を定義する(Pow.Schema、Pow.Diagram、Pow.mapを実装する)。
多項式関手を定義する(Poly.Schema、Poly.Diagram、Poly.mapをPowを使って実装する)。
多項式関手のF-代数が考えられることを確認する(代数は対象と射の組であるが、ここではそのうちの射のみ、さらにその射が属する型を作る型関数Poly.Algebraが実装できればよい)。
多項式関手の最小不動点を定義する(Poly.Fixを再帰型に関するエラーに注意しながら実装する)。
多項式関手のcatamorphismを定義する(Poly.cataをPoly.Algebra、Poly.Fix、Poly.mapを使って実装する)。
前回の記事で提示されたPoly.When、Poly.caseOfの型引数を限定すると、代数Poly.Algebraを構築できることを確認し、Poly.Cata.Whenを実装する。
Poly.caseOfとPoly.cataを関数合成し、関数Poly.Cata.caseOfを実装する。
本題に入る前に少し捕捉しておくと、我々がやりたいのはプログラムの実装であって、圏論ではありません。 この記事では数学の一分野である圏論の用語をよく使いますが、それは使い勝手の良い概念を圏論から借用しているだけです。 例えば、472円の商品を買うのに500円玉を出したら、お釣りとして28円が返ってきます。 この計算は「500 - 472 = 28」という整数の計算です。 しかし、だからといってお釣りの計算をしたい人すべてが整数論について詳しくなる必要などまったくないでしょう。 同様に、この記事を読むのに圏論について詳しくなる必要はありません。
前回の出題編の記事におけるキーワードを抽出すれば、『 「再帰的な構造」と「再帰的な解釈」の拡張性 』となるでしょうか。 ただ、再帰性と拡張性を同時に扱うのはそれなりに困難です。 再帰的な構造から再帰を分離するのに、自己関手の最小不動点が使えることが、計算機科学の分野では知られています。 また、再帰的な解釈から再帰を分離するのに、catamorphismが使えることも知られています。 そのため、自己関手の最小不動点やcatamorphismなどの圏論の概念を借用しました。 ただし、それは圏論における個別の結果を利用しているだけであって、圏論全般の知識が要請されるわけではありません。 繰り返しになりますが、圏論について詳しくなる必要はないのです。
ともかく、圏論の結果を利用することで『 「再帰的な構造」と「再帰的な解釈」の拡張性 』から再帰性は分離され、『多項式関手としての「構造」と「解釈」の拡張性』に帰着されます。 解答実装では、多項式関手を構成する基本情報をSchemaへと分離し、関手としての各種機能(Diagramやmap、Fix、cata、caseOf)をSchemaへ後付けできるようにしています。 そうすることでSchemaの拡張に伴い、関手としての各種機能が追随して自動的に拡張されるようになります。 Schemaの取り扱い方は圏論の積と余積を参考にしているのですが、圏論よりもTypeScriptの型パズルの方が比重は大きいです。
型と関数のなす圏
形式的には、対象の集まりと射の集まりの組で合って、次の4条件を満たせば、圏とみなせます。
すべての射に対して,始域(domain)と呼ばれる対象と終域(codomain) と呼ばれる対象が定められている。
2つの射f,gについて、fの終域とgの始域が一致するとき、fとgは合成可能であると言う。すべての合成可能なfとgについて、合成射と呼ばれる射f;gが定められている。ただし、f;gの始域はfの始域と一致し、f;gの終域はgの終域と一致していなければならない。
射の合成は結合律を満たす。すなわち、fとgが合成可能で、gとhが合成可能であれば、どのようなf,g,hについても、(f;g);h = f;(g;h)が成り立つ。
すべての対象に対して、恒等射と呼ばれる射が存在して、射の合成に関する単位元となる。すなわち、fの始域がXで、終域がY、対象Xの恒等射をid_X、対象Yの恒等射をid_Yとすれば、どのようなf,X,Yについても、id_X;f = f = f;id_Yが成り立つ。
この節ではTypeScriptの型を対象、1変数の関数を射とする圏を考えます。
圏の4条件の内、条件1は問題ないでしょう。 素直に、関数の引数の型を始域、関数の戻り値の型を終域とすれば良いです。
圏の4条件の内、射の合成には次のthenを使います。 これが条件2を満たすことは型Thenから明らかでしょう。 念のため確認しておくと、fの終域Yとgの始域Yが一致しないとTypeScriptの型検査に通りません。 そのため合成可能なことは型検査によって担保できます。 また、合成射then(f, g)の始域Xはfの始域Xと一致し、合成射then(f, g)の終域Zはgの終域Zと一致しています。
type Then = <X, Y, Z>(f: (x: X) => Y, g: (y: Y) => Z) => (x: X) => Z;
const then: Then = (f, g) => x => g(f(x));
結合律
圏の4条件の内、射の合成の結合律(条件3)は、次のようなプログラム運算(calculational programming)をすることで確かめられます。
then(then(f, g), h)
= // thenの定義
x => h(then(f, g)(x))
= // thenの定義
x => h(y => g(f(y)))(x)
= // 関数適用
x => h(g(f(x)))
= // 関数適用の逆
x => (y => h(g(y)))(f(x))
= // thenの定義
x => then(g, h)(f(x))
= // thenの定義
then(f, then(g, h))
恒等射
圏の4条件の内、条件4に出てくる恒等射として、次のidを使います。 任意の対象Xに対してid<X>が、XからXへの射となります。
type Id = <X>(x: X) => X;
const id: Id = x => x;
idが左単位元となることは次のように確かめられます。
then(id, f)
= // thenの定義
x => f(id(x))
= // idの定義
x => f(x)
= // ポイントフリースタイルへの変換
f
idが右単位元となることも同様に確かめられます。
then(f, id)
= // thenの定義
x => id(f(x))
= // idの定義
x => f(x)
= // ポイントフリースタイルへの変換
f
以上より、TypeScriptの型と関数が、確かに圏を成すことがわかりました。
べき乗関手
この節では自己関手を定義します。 形式的には、ある圏の対象をその圏の対象に、その圏の射をその圏の射へ対応付けるものであって、次の3条件を満たせば、自己関手 (endofunctor)とみなせます。
始域、終域と自己関手が交換できる。射を自己関手で送った先の射の始域と、射の始域を自己関手で送った先の対象が一致する。同様に、射を自己関手で送った先の射の終域と、射の終域を自己関手で送った先の対象が一致する。
合成可能な射について、合成してから自己関手で送った先の射と、それぞれの射を自己関手で送ってから合成した射が一致する。
恒等射について、恒等射を自己関手で送った先の射と、その恒等射の始域(終域)を自己関手で送った先の対象の恒等射と一致する。
自己関手として次のPowを使います。 対象XはDiagram<S, X>で別の対象へ対応付けられます。 雰囲気として、X↦XSX↦XSのように対象が対応付けられます。 また、射fはmap(f)<S>で別の射へ対応付けられます。 したがって、Diagramの型引数Sを選ぶごとに自己関手が1つ手に入ります。
自己関手の3条件の内、条件1については型Mapから明らかでしょう。 念のため確認しておくと、mapで送った後の射の始域Diagram<S, X>と、送る前の射の始域XをDiagramで送ったDiagram<S, X>は一致します。 同様に、mapで送った後の射の終域Diagram<S, Y>と、送る前の射の始域YをDiagramで送ったDiagram<S, Y>は一致します。
namespace Pow {
export type Schema = string;
export type Diagram<S extends Schema, X> = { readonly [i in S]: X };
type Map = <X, Y>(xy: (x: X) => Y) => <S extends Schema>(pow: Diagram<S, X>) => Diagram<S, Y>;
export const map: Map = f => x => {
type Y = Diagram<keyof typeof x, ReturnType<typeof f>>;
const y: Partial<Y> = {};
for (const i in x) y[i] = f(x[i]);
return y as Y;
};
}
射の合成の保存
自己関手の3条件の内、射の合成の保存(条件2)は、次のように確かめられます。 なお、Pow.mapの本質はfor文の箇所です。 そのため、Pow.mapをその実装へと展開する場合は、for文の部分のみ明記し、その他の部分は...で省略しています。
then(map(f), map(g))
= // thenの定義
x => map(g)(map(f)(x))
= // Pow.mapの定義
x => map(g)((x => {...; for (const i in x) y[i] = f(x[i]); ...})(x))
= // y を y[i] = f(x[i]) と置く
x => map(g)(y)
= // Pow.mapの定義
x => {...; for (const i in y) z[i] = g(y[i]); ...}
= // yの定義
x => {...; for (const i in x) z[i] = g(f(x[i])); ...}
= // thenの定義
x => {...; for (const i in x) y[i] = then(f, g)(x[i]); ...}
= // Pow.mapの定義
x => map(then(f, g))(x)
= // ポイントフリースタイルへの変換
map(then(f, g))
単位射の保存
自己関手の3条件の内、単位射の保存(条件3)は、次のように確かめられます。
map(id)
= // ポイントフリースタイルの解除
x => map(id)(x)
= // mapの定義
x => {...; for (const i in x) y[i] = id(x[i]); ...}
= // idの定義
x => {...; for (const i in x) y[i] = x[i]; ...}
= // オブジェクトの外延的等価性
x => x
= // idの定義
id
以上より、べき乗関手Powが確かに自己関手であることがわかりました。
多項式関手
べき乗関手Powから多項式関手Polyを定義します。 対象XはDiagram<S, X>で別の対象へ対応付けられます。 雰囲気として、$${X \mapsto \sum_{i \in S} A_i X^{N_i}}$$のように対象が対応付けられます。 また、射fはmap(f)<S>で別の射へ対応付けられます。 したがって、Diagramの型引数Sを選ぶごとに自己関手が1つ手に入ります。
自己関手の3条件の内、条件1については型Mapから明らかでしょう。
namespace Poly {
export type Schema<I extends string = string, A = unknown, N extends Pow.Schema = Pow.Schema> = { [i in I]: { a: A, n: N } };
export type Diagram<S extends Schema, X> = { [i in keyof S]: Readonly<{ i: i & string, a: S[i]["a"], x: Pow.Diagram<S[i]["n"], X> }> }[keyof S];
type Map = <X, Y>(xy: (x: X) => Y) => <S extends Schema>(poly: Diagram<S, X>) => Diagram<S, Y>;
export const map: Map = f => ({ i, a, x }) => ({ i, a, x: Pow.map(f)(x) });
}
射の合成の保存
自己関手の3条件の内、射の合成の保存(条件2)は、次のように確かめられます。
then(map(f), map(g))
= // thenの定義
({ i, a, x }) => map(g)(map(f)({ i, a, x }))
= // Poly.mapの定義
({ i, a, x }) => map(g)((({ i, a, x }) => ({ i, a, x: Pow.map(f)(x) }))({ i, a, x }))
= // 関数適用
({ i, a, x }) => map(g)({ i, a, x: Pow.map(f)(x) })
= // Poly.mapの定義
({ i, a, x }) => (({ i, a, y }) => ({ i, a, x: Pow.map(g)(y) }))({ i, a, x: Pow.map(f)(x) })
= // 関数適用
({ i, a, x }) => ({ i, a, x: Pow.map(g)(Pow.map(f)(x)) })
= // thenの定義
({ i, a, x }) => ({ i, a, x: then(Pow.map(f), Pow.map(g))(x) })
= // Pow.mapの関手性:射の合成の保存
({ i, a, x }) => ({ i, a, x: Pow.map(then(f, g))(x) })
= // Poly.mapの定義
({ i, a, x }) => map(then(f, g))({ i, a, x })
= // ポイントフリースタイルへの変換
map(then(f, g))
単位射の保存
自己関手の3条件の内、単位射の保存(条件3)は、次のように確かめられます。
map(id)
= // Poly.mapの定義
({ i, a, x }) => ({ i, a, x: Pow.map(id)(x) })
= // Pow.mapの関手性:単位射の保存
({ i, a, x }) => ({ i, a, x: id(x) })
= // idの定義
({ i, a, x }) => ({ i, a, x: x })
= // idの定義
id
以上より、多項式関手Polyが確かに自己関手であることがわかりました。
多項式関手の代数
ある対象と、その対象に対する条件を満たす射の組を(F-)代数と呼びます。 その条件とは、射の始域が対象を自己関手で送った先の対象であること、かつ射の終域がその対象であることです。 自己関手にPolyを取れば、次のPoly.Algebra型に属する関数と型引数Xの組が代数になります。
namespace Poly {
export type Algebra<S extends Schema, X> = (poly: Diagram<S, X>) => X;
}
2つの代数「対象X, 射a_x」と「対象Y, 射a_y」があった時、始域がXかつ終域がYの射fについて、then(a_x, f)とthen(map(f), a_y)が等しいとき、fは代数「対象X, 射a_x」から代数「対象Y, 射a_y」への準同型であると言います。 代数を対象、準同型を射とすると、これは再び圏を成します。
射の合成は、そのままthenが使えます。 射の合成にthenが使えることから、準同型の合成の結合律が成り立つことは明らかでしょう。 なお、準同型f,gがあった時、then(f, g)が再び準同型になることは、次のように確かめられます。
then(a_x, then(f, g))
= // thenの結合律
then(then(a_x, f), g)
= // fは準同型
then(then(map(f), a_y), g)
= // thenの結合律
then(map(f), then(a_y, g))
= // gは準同型
then(map(f), then(map(g), a_z))
= // thenの結合律
then(then(map(f), map(g)), a_z)
= // 自己関手の性質: 射の合成の保存
then(map(then(f, g)), a_z)
恒等射も、そのままidが使えます。 恒等射にidが使えることから、単位律が成り立つことは明らかでしょう。 なおidが、任意の代数「対象X, 射a」について、その代数からその代数自身への準同型になることは、次のように確かめられます。
then(a, id)
= // idの恒等律
a
= // idの恒等律
then(id, a)
= // 自己関手の性質: 恒等射の保存
then(map(id), a)
以上より、代数と準同型が確かに圏を成すことがわかりました。
多項式関手の不動点とcatamorphism
始対象と呼ばれる特殊な対象の性質を指す用語があります。 始対象であれば、どのような対象を選んできても、始対象を始域とし、選んできた対象を終域とする射が、ちょうどひとつ存在します。
一般の圏に始対象が存在するとは限りませんが、代数の圏の始対象として次の代数「不動点Fix<S>、恒等射id」が使えます。 なお、代数を構成する射として恒等射が使えることから、TypeScriptの型システムはDiagram<S, Fix<S>>とFix<S>を同じ型として扱うことがわかります。
namespace Poly {
export type Fix<S extends Schema> = { [i in keyof S]: Readonly<{ i: i & string, a: S[i]["a"], x: Pow.Diagram<S[i]["n"], Fix<S>> }> }[keyof S];
}
namespace TypeCheck {
const _ = <S extends Poly.Schema>() => {
const a: Poly.Algebra<S, Poly.Fix<S>> = id;
}
}
代数の圏における始対象から伸びる、ただ一つの準同型を特別にcatamorphismと呼びます。 catamorphismは次のcataのように定義できます。
namespace Poly {
type Cata = <S extends Schema, X>(algebra: Algebra<S, X>) => (fix: Fix<S>) => X;
export const cata: Cata = a => x => a(map(cata(a))(x));
}
上記のcata(a)が、代数「対象Fix<S>、射id」から任意の代数「対象X、射a」への準同型になっていることは、次のように確認できます。 つまり、どのような代数「対象X、射a」を選んできても、代数「対象Fix<S>、射id」からの準同型が存在します。
then(id, cata(a))
= // idの単位律
cata(a)
= // cataの定義
x => a(map(cata(a))(x))
= // thenの定義
then(map(cata(a)), a)
逆に、cata(a)が準同型であるならば、次のようにしてcata(a)の定義が導かれます。 つまり、代数「対象Fix<S>、射id」からの準同型が存在するならば、その準同型は一意です。
cata(a)
= // idの単位律
then(id, cata(a))
= // cata(a)は準同型
then(map(cata(a)), a)
= // thenの定義
x => a(map(cata(a))(x))
以上より、代数「不動点Fix<S>、恒等射id」が確かに始対象であることがわかりました。
なお、cata(a)の定義でthenを展開しているのは、正格評価に伴う無限再帰を避けるためです。 then(map(cata(a)), a)のままだと、mapの引数に与えるためのcata(a)が先に評価されるため、必ず無限に再帰してしまいます。 一方、x => a(map(cata(a))(x))であれば、xが与えられるまでcata(a)の評価を遅延できるので、即座に無限の再帰へ陥ることはありません。
関数の積をひとつの関数へ合成する
前回の記事で提示したPoly.WhenとPoly.caseOfを再掲します。 雰囲気として、caseOfの始域When<S, X, Y>を数式っぽく書けば、$${\prod_{i \in S} \text{Hom}(A_i X^{N_i}, Y)}$$となります。 ここで、総乗(Π)がHomの外にあるので、独立した関数が複数あることを意味しています。
一方、caseOfの終域(poly: Diagram<S, X>) => Yを数式っぽく書けば、$${\prod_{i \in S} \text{Hom}(A_i X^{N_i}, Y)}$$となります。 こちらは総和(Σ)がHomの中にあるので、一つの関数にまとめられていることを意味しています。 つまり、caseOfは複数の独立した関数を一つの関数にまとめる関数となります。
namespace Poly {
export type When<S extends Schema, X, Y> = { readonly [i in keyof S]: (a: S[i]["a"], x: Pow.Diagram<S[i]["n"], X>) => Y };
type CaseOf = <S extends Schema, X, Y>(when: When<S, X, Y>) => (poly: Diagram<S, X>) => Y;
export const caseOf: CaseOf = f => ({ i, a, x }) => f[i](a, x);
}
caseOfの終域(poly: Diagram<S, X>) => YのYをXにすれば、これはAlgebra<S, X>と同じです。 そこで、catamorphism用に特化したPoly.Cata.WhenとPoly.Cata.caseOfを次のように実装しておきます。
これにより、代数を構成する射を独立して定義しても、後から合成するだけで、好きなように拡張できるのです。
namespace Poly {
export namespace Cata {
export type When<S extends Schema, X> = Poly.When<S, X, X>;
type CaseOf = <S extends Schema, X>(when: When<S, X>) => (fix: Fix<S>) => X;
export const caseOf: CaseOf = then(Poly.caseOf, Poly.cata);
}
}
お疲れ様でした。以上で解答は終了です。
発展問題への解答
出題編の最後に載せていた、発展問題への解答も示しておきます。 Powで主役だったオブジェクトの代わりに関数を使うだけで、ここまでの実装とほとんど変わりません。 と言うか、べき指数に制限のないPow.Lazyのほうが多項式関手としては正統でしょう。 無理な制約がない分、Pow.Lazyは全体的に簡潔で見通しの良い実装となります。
PowにないPow.Lazyの機能としては、strictやlazyなど、オブジェクトと関数の相互変換を行う実装があります。 この部分については、理論的には表現可能関手が関係しています。 ただ、これも非常に簡潔な実装なので、取り立てて補足は不要でしょう。
namespace Pow {
export namespace Lazy {
export type Schema = unknown;
export type Diagram<S extends Schema, X> = (i: S) => X;
type Map = <X, Y>(xy: (x: X) => Y) => <S extends Schema>(pow: Diagram<S, X>) => Diagram<S, Y>;
export const map: Map = f => g => x => f(g(x));
export type Positions<S extends Pow.Schema> = { readonly [i in S]: i };
export type Table<S extends Pow.Schema, X> = { [i in S]?: X };
type Strict = <S extends Pow.Schema>(positions: Positions<S>) => <X>(pow: Diagram<S, X>) => Pow.Diagram<S, X>;
export const strict: Strict = x => f => Pow.map(f)(x);
type Lazy = <S extends Pow.Schema, X>(pow: Pow.Diagram<S, X>) => Diagram<S, X>;
export const lazy: Lazy = f => x => f[x];
type Memoize = <S extends Pow.Schema, X>(pow: Diagram<S, X>, table?: Table<S, X>) => Diagram<S, X>;
export const memoize: Memoize = (f, t = {}) => x => x in t ? t[x]! : t[x] = f(x);
}
}
namespace Poly {
export namespace Lazy {
export type Schema<I extends string = string, A = unknown, N = Pow.Lazy.Schema> = { [i in I]: { a: A, n: N } };
export type Diagram<S extends Schema, X> = { [i in keyof S]: Readonly<{ i: i & string, a: S[i]["a"], x: Pow.Lazy.Diagram<S[i]["n"], X> }> }[keyof S];
type Map = <X, Y>(xy: (x: X) => Y) => <S extends Schema>(poly: Diagram<S, X>) => Diagram<S, Y>;
export const map: Map = f => ({ i, a, x }) => ({ i, a, x: Pow.Lazy.map(f)(x) });
export type Algebra<S extends Schema, X> = (poly: Diagram<S, X>) => X;
export type When<S extends Schema, X, Y> = { readonly [t in keyof S]: (a: S[t]["a"], x: Pow.Lazy.Diagram<S[t]["n"], X>) => Y };
type CaseOf = <S extends Schema, X, Y>(when: When<S, X, Y>) => (poly: Diagram<S, X>) => Y;
export const caseOf: CaseOf = f => ({ i, a, x }) => f[i](a, x);
export type Fix<S extends Schema> = { [i in keyof S]: Readonly<{ i: i & string, a: S[i]["a"], x: Pow.Lazy.Diagram<S[i]["n"], Fix<S>> }> }[keyof S];
type Cata = <S extends Schema, X>(algebra: Algebra<S, X>) => (fix: Fix<S>) => X;
export const cata: Cata = a => x => a(map(cata(a))(x));
export namespace Cata {
export type When<S extends Schema, X> = Poly.Lazy.When<S, X, X>;
type CaseOf = <S extends Schema, X>(when: When<S, X>) => (fix: Fix<S>) => X;
export const caseOf: CataOf = then(caseOf, cata);
}
export type Positions<S extends Poly.Schema> = { readonly [t in keyof S]: Pow.Lazy.Positions<S[t]["n"]> };
export type Table<S extends Poly.Schema, X> = { [t in keyof S]?: Pow.Lazy.Table<S[t]["n"], X> };
type Strict = <S extends Poly.Schema>(positions: Positions<S>) => <X>(poly: Diagram<S, X>) => Poly.Diagram<S, X>;
export const strict: Strict = p => ({ i, a, x }) => ({ i, a, x: Pow.Lazy.strict(p[i])(x) });
type Lazy = <S extends Poly.Schema, X>(poly: Poly.Diagram<S, X>) => Diagram<S, X>;
export const lazy: Lazy = ({ i, a, x }) => ({ i, a, x: Pow.Lazy.lazy(x) });
type Memoize = <S extends Poly.Schema, X>(poly: Diagram<S, X>, table?: Table<S, X>) => Diagram<S, X>;
export const memoize: Memoize = ({ i, a, x }, t = {}) => ({ i, a, x: Pow.Lazy.memoize(x, i in t ? t[i] : (t[i] = {})) });
}
export namespace Cata {
type Lazy = <S extends Schema, X>(algebra: Poly.Lazy.Algebra<S, X>) => (fix: Fix<S>) => X;
export const lazy: Lazy = a => x => a(Poly.Lazy.map(lazy(a))(Poly.Lazy.lazy(x)));
type LazyOf = <S extends Schema, X>(when: Poly.Lazy.Cata.When<S, X>) => (fix: Fix<S>) => X
export const lazyOf: LazyOf = then(Poly.Lazy.caseOf, lazy);
}
}
お問合せはお気軽に
https://service.shiftinc.jp/contact/
SHIFTについて(コーポレートサイト)
https://www.shiftinc.jp/
SHIFTのサービスについて(サービスサイト)
https://service.shiftinc.jp/
SHIFTの導入事例
https://service.shiftinc.jp/case/
お役立ち資料はこちら
https://service.shiftinc.jp/resources/
SHIFTの採用情報はこちら
https://recruit.shiftinc.jp/career/
PHOTO:UnsplashのVystralith