檜山正幸のキマイラ飼育記 このページをアンテナに追加 RSSフィード Twitter

キマイラ・サイトは http://www.chimaira.org/です。
トラックバック/コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
このブログの更新は、Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama
ところで、アーカイブってけっこう便利ですよ。

2015-03-22 (日)

TypeScriptと関手やモナドなど

| 18:30 | TypeScriptと関手やモナドなどを含むブックマーク

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

内容:

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

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

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

圏論 プログラミング言語
対象
関数
関手の対象部分 1パラメータの型構成子
関手の射部分 2パラメータの総称高階関数
自然変換 1パラメータの総称関数

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

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

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

仮に、とあるプログラミング言語の関数が射でモデル化できるとしても、引数の型が域で、戻り値の型が余域か? というと、そんなことも滅多にありません。その関数と呼ばれる計算単位が、非ローカル変数を参照/更新しているかもしれません。ファイル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))

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


[追記]

TypeScriptに関する補足説明

コメント欄で、id:vvakame さんに教えていただきました。

まず、「stringからstringへの関数の型」は (x:string)=>string のように書きますが、引数名xを省略できることは僕の誤解です。(string)=>string と書いてもコンパイルできたので、いいのかと思ったのですが、これは引数名xが省略されたのではなくて、型指定が省略された (string:any)=>string と解釈されたのです。ヒエーッ。

TypeScriptでは、boolean, number, stringなどの基本型を使えますが、型の名前は予約されてなくて、通常の名前にも使えるようです。次は問題なくコンパイルされます。

function boolean(number, string) {return number + string;}

これに次のような型付けをしてもOKです。カンベンしてくれ

function boolean(number:string, string:number) :string {return number + string;}

アロー形式の関数に戻り値型を指定するには、(x:string):number => x.length のようにするとのこと。(x:string):number の部分が、function文/式の宣言部と同じ形なんですね。総称の型パラメータも付けられるので、var id = <X>(x:X)=>x; のように書けます。素晴らしい。

アロー関数(ラムダ抽象のこと)で、ボディが式ならブレイスとreturnが要らないのも素晴らしい。僕は余分なreturnをとても嫌ってました。

9年経って、やっとreturnを書かないで済む状況が実現されました。

実はnewも書きたくなくて、

「JavaScriptでnewが不要なコンストラクタ」という記事で、

5年前の不満が今ごろ解消されました。

と書きましたが、これは言語仕様ではなくてユーザー側のトリックを使うものなので、ほんとの意味でnewが不要になっているわけじゃないです。あと何年かしたらnewも不要になるのかなぁ。

[/追記]

vvakamevvakame 2015/03/23 00:01 アロー形式だと戻り値型を書くことが出来ない
(x: string): string => "foo"; のように書くことができます。

この場合は引数名は省略可能
省略可能ではありません。(string) => string は (string: any) => string と解釈されています。

アロー関数で引数が1つだけの場合、カッコは省略できます。bodyが1つの式だけの場合、本体部分のカッコも省略できます。
var fn = x => x; は本文中だと var fn = (x) => {return x;}; としていますね。

m-hiyamam-hiyama 2015/03/23 10:11 vvakameさん、ありがとうございます。

> (x: string): string => "foo"; のように書くことができます。
あー、なるほど。<X>(x:X):X => x; というのも書けました。
> 省略可能ではありません。(string) => string は (string: any) => string と解釈されています。
ヒエーッ! 恐ろしい。基本型名は予約されてないんですね。
> アロー関数で引数が1つだけの場合、カッコは省略できます。bodyが1つの式だけの場合、本体部分のカッコも省略できます。
x => x、これは素敵! returnが不要なのはありがたい。http://d.hatena.ne.jp/m-hiyama/20060322/1142987185 function式への不満が解決されました。

後で本文を修正します。

vvakamevvakame 2015/03/23 15:36 お役に立ちましたら幸いです :)
書き忘れましたが、 --noImplicitAny オプションを併用すると型推論にミスってる(string: anyのような)場合にコンパイラがエラーにしてくれるので安心です。是非併用していただきたく。

m-hiyamam-hiyama 2015/03/23 17:46 vvakameさん、
> --noImplicitAny オプションを併用すると型推論にミスってる(string: anyのような)場合にコンパイラがエラーにしてくれる
おおー、それ、すごくいい。けっこうイイかも>TypeScript 。