cafelier@SRM

『純粋関数型データ構造』のためだけの超いい加減な Standard ML 入門

23:26 |

こういう本を翻訳しました。発売中です。よろしくお願いします。

この本は名前にある通りデータ構造の本なんですが、中でも、「永続データ構造」と言われる種類のデータ構造に特化して、それだけを丸々一冊扱っています。Topcoderなどで永続データ構造が活躍する問題というのは、まだまだ中々マイナーですが、これから流行るといいなあと思っておりいます。qnighyさんの記事

http://qnighy.hatenablog.com/entry/2012/12/02/032851

でいくつか例題が紹介されていました。

さて、この本、面白いんですが、本の中のサンプルコードは全て Standard ML というプログラミング言語で書かれています。正直なところ馴染みのない方も多いのではないでしょうか。というわけでこの記事では、C++ や Java に慣れている人向けに、ものすごく大雑把に Standard ML を紹介します。

データ構造に興味はあるけど知らないプログラミング言語で書いてあると読めるかどうかわからない･･･という方が読んでみる助けになれば幸いです。擬似コードを読むような気分で本のサンプルコードを違和感なく読めるいうところが目標です。この記事を読んでも Standard ML を書けるようにはならないと思います。

実行環境

「読めればよい」が目標なので実行する必要はない気もしますが、一応。

• SML/NJ http://www.smlnj.org/
• SML# http://www.pllab.riec.tohoku.ac.jp/smlsharp/ja/

などが人気のある処理系です。

関数定義と呼び出し

例として

fun norm x y = x*x + y*y

これがC言語でいうところの

int norm(int x, int y) {
  return x*x + y*y;
}

に当たります。つまり、fun というキーワードを使って

fun 関数名 引数1 引数2 引数3 ... = 関数本体

と書いてあるのが関数宣言です。引数の周りに括弧やコンマがないのが特徴的ですね。関数を呼び出すときも同じく括弧やコンマはつけずに

norm 1 2

とかやれば 5 になります。普通の演算子よりも関数呼び出しの方が結合が強いので、

norm 1 2 + 3

は (norm 1 2) + 3 と同じ意味で、8 です。26にしたい時は足し算の方に括弧をつけて norm 1 (2 + 3) とします。

こういう構文になっているのには「カリー化」などの理由があるんですが、純粋関数型データ構造の本を読む分には特に関係がないので、そういう風習なのだと割り切って読むとよいと思います。

変数/定数定義

val というキーワードで宣言します。

val pi = 3.14

関数の中でローカル変数を定義するときは let ～ in ～ end と書きます。

fun average x y z =
  let val s = x + y + z in
    s div 3 
  end

"let val s = ... in ～" というのは、 "～ という式の中では s を ... とする" みたいな英語的気分です。

この本は永続データ構造の本なので、一度作った値は絶対に壊しません。つまり、一度宣言した変数に別の値を後から再代入したりしません。なので、変数は val で初期値を指定して宣言するだけで、代入をする構文とかは出てきません。

型の定義（ツリー構造の定義）

こういうことを言うともしかしたら Standard ML 好きな人に怒られたりするかもしれないんですが、私の中では(Standard) MLというのは、ツリー構造の操作に特化した最強ツリー処理専用言語です。大抵の強まったデータ構造というのは工夫して構築されたツリー構造なわけで、だからこそデータ構造の解説書である本書では、最強のツリー処理言語であるMLが選ばれているわけです。

たとえば、整数値を格納する赤黒木の定義はこんな感じ。

datatype Rbtree = E
                | R of Rbtree * int * Rbtree
                | B of Rbtree * int * Rbtree

datatype というキーワードで新しい型を定義するんですが、新しい型というのは要するに、新しい種類の木を定義しています。ここで定義されている木にはEとRとBという三種類のノードがあると言っています。

Eノードには子供がない、つまり葉ノードですね。RやBノードには左の子と、格納しているint値と、右の子があります。こういう三種類のノードでできているツリー構造というのに Rbtree という名前をつけて定義しているわけです。

datatype 型の名前 = ノードのラベル1 of (そのノードの持つ情報(子ノードとか) * ... )
                  | ノードのラベル2 of (そのノードの持つ情報(子ノードとか) * ... )
                  | ...

という形で、何種類かノードがあるツリー構造の型を宣言します。この型の具体的な値を作るときには、こんな風に、今度は括弧とコンマで子などの情報を指定して

R (B (E,12,E), 34, E)

こうします。R や B や E のことを構築子（コンストラクタ）と呼びます。C++やJavaのコンストラクタとある意味同じで、ツリーのノードというオブジェクトを作る関数というわけです。

パターンマッチ（ツリー構造の操作）

ツリー構造を走査して操作する関数というのは大抵、ノードの種類ごとに場合が分かれて処理しつつ再帰していくことになります。この時に、「どのラベルのノードなのかの判定・分岐」と、「分岐したあとのノードの内部情報を変数におく」を一度に書ける構文が、パターンマッチです。

fun count_red E = 0
  | count_red (B (left, _, right)) = count_red left + count_red right
  | count_red (R (left, _, right)) = 1 + count_red left + count_red right

これは赤黒木の中の赤のノードの個数を数える関数。Eの場合、Bの場合、Rの場合に分岐しつつ、左の子や右の子を表すフィールドを変数にしてから関数本体へ突入しています。ノードの中でも要らない情報（この場合ノードに入っているint値）のところは _ と書いておくと無視できます。

パターンは多段に重ねることもできて

fun foo (R (R (_, _, _), _, _)) = ...
  | foo _ = ...

とすれば、「左の子もRであるようなRノードとそれ以外」 という分岐になります。このパターンマッチによって、ツリーで作るデータ構造の操作がとても簡潔に表現できます。

http://shuns.sblo.jp/article/28490553.html

という記事に赤黒木の再平衡の実装の例があります。（こちらの記事は Haskell という言語を使っているのですが、まあだいたい Standard ML でも同じです。）

asパターン

パターンマッチで分解して中のノードのラベルとかは調べたいんだけど、変数におくのは分解しないでそのノードを指したい、といった時に出てくるのが as パターンです。

fun foo (R (left as R (_, _, _), _, right)) = ...
  | foo _ = ...

「左の子もRであるようなRノード」が渡されたときに最初の分岐に行くのは先程の例と変わりませんが、同時に、そのRであるような左の子をleftという変数で指しています。

多相型

さっきの赤黒木だとintしかツリーに持たせられませんでしたが、場合によって格納する型を変えたいですよね。C++でいうtemplate、JavaでいうGenericsです。Standard ML では多相型といいます。C++やJavaだとRbtree<T>みたいな、型名の後に<>という尖った括弧でパラメタ型Tを書きますが、Standard ML だと、型名の前にポンとパラメタ型を書きます。

datatype 'a Rbtree = E
                   | R of 'a Rbtree * 'a * 'a Rbtree
                   | B of 'a Rbtree * 'a * 'a Rbtree

'a という ' のついたのがパラメタ型で、"int Rbtree" ならintが入る赤黒木に、"string Rbtree"なら文字列が入る赤黒木の型になるわけですね。

'a という表記はASCIIの範囲でソースコードを記述するための仮の姿で、実は、Standard ML使いにはこれはギリシャ文字の α という文字に見えています。というわけで本に書くときは全部こういうのは

datatype α Rbtree = E
                   | R of α Rbtree * α * α Rbtree
                   | B of α Rbtree * α * α Rbtree

と書いてあります。

リスト

リストというのは子が１つしかないノードが繋がっているツリーと考えることができます。CやJavaでは配列が言語に組み込みのデータ型として基本となっていますが、Standard ML では、リストが標準に用意されていて、基本的なデータ型としてあらゆる場面で使われます。

空のリストを表す [] が葉ノードで、格納した値と次のノードの二つの要素を持つノード :: が、標準のリストの構築子です。

::は便利さを考えて、中置演算子として書けるようになっています。

1 :: 2 :: 3 :: []

と書くと1,2,3というリストになります。

長いリストを書くのに便利なような専用の略記法も用意されていて

[1,2,3]

と書いても同じ意味になります。もちろんのこのリストを表したツリーを処理するときにはパターンマッチが使えて、例えばintのリストの値の総和を取るには

fun sum [] = 0
  | sum (x :: next) = x + sum next

こんな感じ。

シグネチャ・ストラクチャ・ファンクタ

この本、一番最初に出てくるサンプルコードが signature と structure というものをいきなり使っていて仰々しいのですが、あまり身構えずに適当に雰囲気で読み飛ばしましょう。誤解を恐れずにいうと、

• シグネチャはC++でいうとヘッダファイル(hogehoge.h)みたいなもので、型とか関数とかの宣言だけを集めたもの
• ストラクチャはhogehoge.ccファイルみたいなものでシグネチャで宣言したものの具体的な実装

くらいの理解で最初はなんとなく雰囲気で読めると思います。

いや、「ヘッダファイルみたいなもの」は実のところ流石にちょっと適当に言い過ぎました。C++のヘッダで宣言した関数に対して実装は一つしかありませんが、シグネチャに対しては何個も違う実装をすることができます。

• シグネチャはJavaでいうインターフェイスみたいなもの、関数の型の宣言だけ集めたもの
• ストラクチャは具体的なクラスみたいなもので、インターフェイスで宣言した関数の具体的な実装

の方が近いかな。Javaの標準ライブラリにある名前を借りると、Listシグネチャを実装するArrayListストラクチャやLinkedListストラクチャ、みたいな。ただし、Javaのインターフェイスやクラスは一つの型とその複数のメソッドを宣言/定義する物ですが、Standard ML のシグネチャやストラクチャは、複数の型と複数の関数のまとまりを宣言/定義します。

C++でいうとhttp://en.cppreference.com/w/cpp/container/priority_queue:priority_queueが実装にどんなコンテナを使うのか指定できるような感じで、「別のストラクチャをパラメタとして受け取って使うストラクチャ」が作れると便利です。こういうことをするのが functor というキーワードで定義される「ファンクタ」です。

たぶんこの辺りは本の具体的な例を読んでいただいた方が理解しやすそうです。

質問など

ありましたらなんでも http://twitter.com/kinaba まで気軽に投げつけてください。