檜山正幸のキマイラ飼育記

TypeScriptと関手やモナドなど

雑記／備忘 | 18:30 |

2008年に書いた記事「CPS（継続渡し方式）変換をJavaScriptで説明してみるべ、ナーニ、たいしたことねーべよ」はCPSの説明にJavaScriptを使っています。しかし、JavaScriptでは型宣言や型総称（ジェネリックス）が使えないので、「未来のJavaScript」という最初の節で架空のJavaScript方言を定義しました。最近のAltJSのなかには、当時の「架空のJavaScript方言」の機能を実現したものがあります。そのなかでも、TypeScritは強力な型システムを持っています。2015年に現存するJavaScript風言語であるTypeScriptで、関手やモナドがうまく書けるかどうか探ってみます。

内容：

1. 圏論とプログラミング言語
2. TypeScriptの型の書き方
3. お題はリストモナド
4. モナドの乗法と単位、全体のまとまり

圏論とプログラミング言語

圏論の概念と対応するプログラミング言語機能を表にしましょう。ただし注意事項があるので、それを表の直後で述べます。

このような対応は、圏論の概念をプログラミング言語で素直に表現したいときの願望です。現実の計算現象を圏論でモデル化するときは話が別で、この表のような素朴な対応は期待すべきではありません。「カテゴリカル・モデリングに向けて」の一節を引用します。

データ型は対象で、計算は射でモデル化できます -- そう言っていいでしょう。しかしこれは、データ型が集合で、射が写像だと言ってるんじゃありません。仮に射が写像であったとしても、その写像の集合論的な始域／終域が、射の域／余域を与えるとは限りません。写像とみなして同じ計算でも、計算そのものとしては異なるかもしれないし、その逆のケースもあるでしょう。

ましてや、特定のプログラミング言語のなかで「関数」とか「メソッド」とか呼ばれているものが、素直に射に対応しているなんてことは滅多にありません。もちろん、プログラミング言語の計算単位が射に対応してくれれば美しいし、嬉しいですが、世の中そんなにうまくいかんのよ。

仮に、とあるプログラミング言語の関数が射でモデル化できるとしても、引数の型が域で、戻り値の型が余域か？ というと、そんなことも滅多にありません。その関数と呼ばれる計算単位が、非ローカル変数を参照／更新しているかもしれません。ファイルIOやデータベースアクセスやネットワーク通信もしているかもしれません。また、後述するように、引数の一部は入力じゃなくてインデックスかもしれません。

以上のような断りを入れた上で、今回は、できるだけ「素直に表現したいときの願望」をかなえる方法を探します。

圏論の場合は、暗黙の習慣、記号の乱用、文脈による省略、オーバーロードが極度に発達した結果、非常に単純な記法で抽象概念を表現できます。例えば、関手F上のモナドを (F, μ, η) とするとき、モナドの単位律と結合律は次の形に書けます。（自然変換の縦結合を「;」で示しています、僕は「|」もよく使います。）

• Fη;μ = ηF;μ = F
• Fμ;μ = μF;μ

現存するプログラミング言語で、ここまで簡素に書けるものはないと思います。そもそも、モナドやモナド法則を書きようがない言語が多いのですが、TypeScriptはどうでしょうか。

TypeScriptの型の書き方

次の簡単なJavaScript関数からスタート。

function id0(x) {return x;}

TypeScriptでは次のようにも書けます。

var id1 = (x)=>{return x;};

(x)=>{return x;} は、アロー関数と呼ばれたりしますが、ラムダ式 λx.x と同じです。矢印記号 => が関数抽象を作る中置演算子になっていて、lambdaとかfunとかの前置キーワードなしに関数抽象が書けるのはいいですね。

id関数の引数xに型宣言（型アノテーション）を付けましょう。

function id2(x:string) {return x;}

アロー関数の形式なら、

var id3 = (x:string)=>{return x;}

これは、λx:string.x という型付きラムダ計算の式（項）に対応する書き方です。戻り値の型は型推論されますが、明示的に戻り値の型を書くなら、

function id4(x:string) : string {return x;}

アロー形式だと戻り値型を書くことが出来ないようなので（たぶん）、関数名の型宣言として「引数の型=>戻り値の型」という関数型（高階の型、指数型）を宣言します。

var id5 : (x:string)=>string = (x)=>{return x;};

「stringからstringへの関数の型」を string=>string と書いたほうがスッキリしていると思うのですが、丸括弧が必須のようです（この場合は引数名は省略可能、なぜか省略できないこともある）。

具体的な型stringを、型パラメータXに一般化すると：

function id6<X> (x:X) : X {return x;}

関数名の直後に型パラメータを付けます。アロー関数として書く時は、

var id7 = <X>(x:X)=>{return x;};

<X>(x:X)=>{return x;} が名無しの総称関数です。戻り値の型も宣言したいときは次のようです。

var id8 : <X>(x:X)=>X = (x)=>{return x;};

名無しの総称関数に戻り値型をアノテートする方法があったら教えて下さいな、ご存知のかた。

お題はリストモナド

お約束のリストモナドを題材にします。ジェネリックスを備えた言語では、List<X> のような書き方がサポートされています。TypeScriptでも Array<X> と書けます。これで、リストモナドの型構成子部分はOKです。

ちなみに、新しい総称型を定義したいときは型パラメータ付きのクラスを使うようです。

class Pair<X, Y> {
    x: X;
    y: Y;
    constructor(x: X, y: Y) {
	this.x = x;
	this.y = y;
    }
}

var p = new Pair<string, number>("hello", 3);

さて、Arrayを関手と考えた場合、その射部分を同じ名前Arrayを使って Array(f) と書けたらいいのですが、それは無理そうなんで、大域関数 Array_fmap を定義します。

function Array_fmap<X, Y> (f: (x:X)=>Y) : (ax:Array<X>)=>Array<Y> {
	return (ax)=>{return ax.map(f);};
}

Array_fmapを使う時は、Array_fmap<string, number> のように手で型を具体化してもいいですが、引数である関数fの型からX, Yを推論して埋めてくれるようです（型推論がいつでもうまくいくとは限りませんが）。

function len(s:String) : number {return s.length};

var lens = Array_fmap(len)(["Hello", "world"]);
console.log(lens);

とりあえず、型構成子Arrayと総称関数Array_fmapの組合せでリスト関手（配列関手）は表現できました。モナドは、関手の上に乗法と単位を載せたものです。乗法と単位を次節で。

モナドの乗法と単位、全体のまとまり

モナド乗法であるflattenとモナド単位であるsingleは次のように書けるでしょう。

function Array_flatten<X> (aax:Array<Array<X>>) : Array<X> {
    var result:Array<X> = [];
    for (var i = 0; i < aax.length; i++) {
	result = result.concat(aax[i]);
    }
    return result;
}

function Array_single<X> (x:X): Array<X> {
    return [x];
}

型パラメータ付きのクラスにすると少しだけ記述が楽です。

class ArrayMonad<X> {
    flatten (aax:Array<Array<X>>) : Array<X> {
	var result:Array<X> = [];
	for (var i = 0; i < aax.length; i++) {
	    result = result.concat(aax[i]);
	}
	return result;
    }

    single (x:X) : Array<X> {
	return [x];
    }
}

この場合、型パラメータの具体化はクラスのインスタンス生成時になります。

var amn = new ArrayMonad<number>();

amn.flattenとamn.singleは、配列の要素が数値のときに限定されるわけで、ウーン？ インスタンス化必要だし、使い勝手悪そう。

型構成子と型パラメータを持つ関数があれば、とりあえずモナドは定義できるのですが、モナドを構成する型構成子と総称関数達をうまくまとめる機構が欠けている感じはします。型パラメータを持つクラスでは不十分で、型構成子をパラメータにする型クラス（と型インスタンス）のような容れ物が必要なんでしょうが、AltJSにそこまで要求するのも酷な気はします。Array* という名前による気分的なまとまりでも、まーいいかな。

Array, Array_fmap, Array_flatten, Array_single を使ってモナドの単位律と結合律を書いてみましょう。

• Array_flatten(Array_single(ax)) = ax
• Array_flatten(Array_fmap(Array_single)(ax)) = ax
• Array_flatten(Array_flatten(aaax)) = Array_flatten(Array_fmap(Array_flatten)(aaax))

総称の型を明示的に書いてみると …… グチャグチャになるからやめとこ。次の記事なんかにグチャグチャの処理の仕方が書いてあります。

• 僕が使っている計算法：絵算と図式順記法
• 僕は嫌いなのだが、バイダイレクショナルな自然変換計算はこうする