2017年度「プログラミング言語」配布資料 (12)
五十嵐 淳 (京都大学大学院情報学研究科 通信情報システム専攻)
2017年12月15日
[ 前の資料 | 講義ホームページ・トップ ]
多相的2分探索木
本稿では配布資料(10)と配布資料(11)で学んだことを総合して,多相的な2分探索木の実装を示す.さらに,map や fold といった操作を多相的な2分木に加える際の新しい課題をみる.
要素の比較操作の表現
既に配布資料(10)冒頭でも述べたように,2分探索木に格納できるデータには全順序が与えられていて大小比較ができることが必要である.実際,整数の2分探索木においては随所で比較演算子 ==
(OCaml なら =
),や比較演算子 <
が使われている.こういった比較演算子がどんな種類の値の比較に適用できるかは言語によって様々であるが,比較できるものが限られているか,言語がデフォルトで用意した比較方式に従うため(特に,プログラマが定義したデータについては)必ずしもプログラマの思う順序と合致しないこともある.そのため,比較演算はプログラマが何らかの形で2分探索木に与えることが必要となる.これは,高階関数が使える言語であれば比較演算をパラメータ化することで問題なく実現できるだろう.
必要なのは「等しさ」と「小さいかどうか」を判定する操作だが,このような「比較演算でパラメータ化されている処理」は,「以下」「未満」などの比較演算を全て用意するのではなく,以下のような関数(仮に名前を \(compare\) とする)をひとつだけ考えることが多い.
- \(compare(x,y)\) は整数を返す.
- 「\(x\) が \(y\) より小さい」ならば \(compare(x,y)\) は何らかの負整数を返す(つまり \(compare(x,y) < 0\)).
- 「\(x\) が \(y\) と等しい」ならば \(compare(x,y)\) は \(0\) を返す(つまり \(compare(x,y) = 0\)).
- 「\(x\) が \(y\) より大きい」ならば \(compare(x,y)\) は何らかの正整数を返す(つまり \(compare(x,y) > 0\)).
括弧書き内にあるように \(compare\) の結果は通常 \(0\) と比較(ここで使う不等号の向きは \(x\), \(y\) の大小関係と一致している)することになる.
比較をこのように整数を返す関数ひとつで表現する技法は,言語を問わず,幅広く使われており,以下で見るように,データ型によっては,この仕様に沿った比較関数が最初から提供されていることがある.
OCaml の場合 (ocaml/polyBST)
まずは OCaml で多相的2分探索木を記述してみよう.木構造自体は,単なる2分木であるから既に見た通りである.
1 2 3 4 5 6 7 |
|
find
などの関数は木や探索・追加・削除対象のデータだけでなく,比較関数もパラメータ(名前を cmp
とする)として取ることになる.代表例として find
を見てみよう.
1 2 3 4 5 6 7 8 |
|
整数の場合と比べると,n = v
が cmp n v = 0
に,n < v
が cmp n v < 0
に置き換わっただけである.insert
や delete
も比較部分が変わるだけで特に説明するところはない.これらの操作が,比較以外,格納されるデータの種類に依存していないことの現れである.
実は,min
だけがもう少し説明が必要である.それは,引数 t
が(想定していない入力である) leaf であった場合にダミーの値 -255
を返していた処理についてである.min
は2分探索木中の最小の 要素 を返すわけで,これが -255
でよかったのは,整数が要素だったからである.今や,t
に格納されるデータの型は抽象的な型パラメータになってしまって正体がわからないので,-255
はもちろんのこと,何も返せない.
このような場合に対処するのが 例外(exception) の機構である.例外は,その名の通りプログラム実行中に発生する例外的な状況である.プログラマは例外機構を使って,例外的な状況でのプログラム実行の中断や,中断からの回復処理を記述することができる.例外機構の本格的な紹介はここでは行わないが,OCaml では,いくつか例外によってプログラムの実行を中断(回復処理をしないので,実質的には強制終了)させるための関数が用意されている.invalid_arg 〈文字列〉
という,引数が不正であることを示す Invalid_argument
例外を発生させる関数があるのでそれを使うことにしよう.
1 2 3 4 5 6 7 |
|
invalid_arg
関数の型は string -> 'a
となっていて,文字列を与えると任意の型の(!)式として使えることを表している.これは不思議に思えるかもしれないが,ここが実行されるとプログラムが強制終了してしまい値が返ってこないことと対応しているのである.実際,min
に Lf
を与えると
# min Lf;;
Exception: Invalid_argument "Input can't be a leaf!".
#
と,値が返らずに,発生した例外がメッセージとして表示されて,入力プロンプトに戻ってくる.
さて,このように定義した関数の型を見てみよう.find
,insert
,delete
の型は以下のように推論される.
val find : ('a -> 'b -> int) -> 'b tree -> 'a -> bool = <fun>
val insert : ('a -> 'a -> int) -> 'a tree -> 'a -> 'a tree = <fun>
val delete : ('a -> 'a -> int) -> 'a tree -> 'a -> 'a tree = <fun>
insert
と delete
の ('a -> 'a -> int)
が cmp
の型,'a tree
が t
の型,'a
が n
の型に対応している.返値は新しい('a
を要素とした)木なので 'a tree
である.一方,find
は,ちょっと違う型が推論されている.ふたつの型変数 'a
と 'b
が現れるので,cmp
は,int
を返すならどんな(カリー化された)2引数関数でもよいことになっている.よくよく find
の定義を見てみると,(cmp
に与えられる実際の関数は int -> int -> int
など2引数の型が一致しているものではあるものの,)確かに n
と t
の要素型が一致している 必要はない ことがわかる.前にも述べたように,OCaml の型推論は最も多相的な型(主要型)を推論するので,この場合のように,想定していたよりも多相的な型が推論される場合もある.
ちなみに,insert
については,n
が Br {...; value = n; ...}
と使われているので,n
の型と t
の要素型が一致している必要がある.また delete
については,min
で得られた m
を使って delete
を呼び出すことから,芋蔓式に n
も m
と型が一致していることが要請されて,上のような型が推論される.
さて,最後に,これらの使用例として,整数と文字列の2分探索木を示す.整数の比較は単に差を取ればよいので,cmp
として fun x y -> x - y
という匿名関数を返している.(が,何度も使っているので,部分適用した insert (fun x y -> x - y)
などに名前をつけて,使いまわした方がすっきりしたコードになるだろう.)文字列については,OCaml のライブラリが String.compare
という上の \(compare\) の仕様を満たした関数を提供してくれている.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
|
Java の場合 (java/polyBST)
関数オブジェクトを用いた手法
Java でも OCaml と同様なアイデアを用いれば多相的な2分探索木のインターフェース・クラスを記述することができる.比較関数の返り値型を(Integer
ではなく)プリミティブ型の int
にする場合,ライブラリに「T
型と U
型から int
型への関数」を表すインターフェース ToIntBiFunction
があるので,これを使うと,ジェネリック・インターフェース BinarySearchTree<Elm>
は以下のように記述できるだろう.
1 2 3 4 5 6 |
|
find
の型のみ示しているが,検索する要素だけでなく,比較関数を表す引数を追加している.ToIntBiFunction
は java.util.function
というパッケージ(ライブラリ)に属しているので,上のような import
宣言をしておくとよい.1 ToIntBiFunction
がどのようなインターフェースかは以下に示す.関数を呼ぶためのメソッド名が,返値型を含んだ applyAsInt
になっていることに注意してほしい.
1 2 3 4 |
|
実は,Java には,比較関数を表すための特別なジェネリック・インターフェース Comparator<T>
が用意されている2ので,これを使う方がより Java らしい.
1 2 3 4 |
|
1 2 3 4 5 |
|
Comparator
を使った場合,find
などのメソッド定義はほとんど OCaml と同様になることもあり,ここでは,この方法にはこれ以上踏み込まない.
メソッドとしての比較処理と制限付型パラメータ
ここで詳しく紹介するのは,比較の処理を Comparator
を implements
した関数オブジェクトではなく,2分探索木に格納されるオブジェクトのメソッドとして定義する方法である.実は,Java ライブラリにあるクラスの多くには compareTo
という int
を返すメソッドが実装されていて,これによって比較を行うことができる.
Integer i1 = new Integer(10);
Integer i2 = new Integer(20);
System.out.println(i1.compareTo(i2)); // displays some negative int
String s1 = "hoge";
String s2 = "fuga";
System.out.print(s1.compareTo(s2)); // displays some (perhaps positive) int
比較には,このメソッドを使うことにすれば,find
などに比較関数オブジェクトの引数を追加することなくクラスを記述することができる.
バージョン1
この方針に従って書いたインターフェース・クラスが以下である.ここでは find
のみ定義を示している.
1 2 3 4 5 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
しかし,残念ながらこのクラス定義は(Branch
クラスの)コンパイル時に以下のようなエラーが発生する.
Branch.java:45: エラー: シンボルを見つけられません
if (e.compareTo(v) == 0) { return true; }
^
シンボル: メソッド compareTo(Elm)
場所: タイプElmの変数 e
Elmが型変数の場合:
クラス Branchで宣言されているElmはObjectを拡張します
他のエラーも compareTo
を呼出すところで発生しているようだ.これは一体どういうことだろうか.このエラーは,e
の型が(型変数) Elm
なのだけれども,Elm
型のオブジェクトに compareTo
メソッドがない(かもよ),といっているのである.今,Elm
は任意のオブジェクト型(これがメッセージ中の「Objectを拡張します」のだいたいの意味である)を表しうる---使う側は任意のオブジェクト型を Elm
に割り当てて使う可能性がある---のだが,compareTo
メソッドは全てのオブジェクトが持っているわけではないのでまずいのである.配布資料(10) で2分木の toString
メソッドを定義した時,Elm
型の変数に対して toString
メソッドを(暗黙に)呼んでいたが,あれは, 型に関わらず全てのオブジェクトは toString
を持っている おかげで呼んでよかったのである.
バージョン2
このような状況に対処するために,Javaでは型変数が表す型の範囲を,インターフェースを使って,特定のメソッドを持つクラスに制限することができる.この時に鍵になるのは,インターフェース I
を implements
したクラスのオブジェクトは全て I
に書かれたメソッドを持つ,という性質である.具体的には,型変数 X
に extends I
という修飾をつけ public class C<X extends I> {...}
のように書いて宣言する.3 すると,
C
を使う箇所ではX
をI
をimplements
したクラスでしか具体化できなくなる,が,同時にX
型の変数に対して,I
に書かれたメソッドがC
内で呼べるようになる.
具体例を見てみよう.まず,Java では Integer
や String
などの比較メソッド compareTo
を持つクラスは Comparable<T>
というジェネリック・インターフェースを implements
している.Comparable<T>
は以下のように定義されている.
public interface Comparable<T> {
int compareTo(T o);
}
ここで compareTo
の引数の型が,具体的な型ではなく型変数になっているのは,オブジェクト毎に何と比較できるかが異なるためである.実際,Integer
の compareTo
メソッドは Integer
を引数にとるし,String
の compareTo
メソッドは String
を引数にとるので,Integer
の場合 T
を Integer
にしなければいけないし,String
の場合 T
を String
にしなければならない.以下は,いくらか単純化した,Integer
と String
クラスの定義である.
public class Integer implements Comparable<Integer> {
...
int compareTo(Integer i) {
....
};
...
}
public class String implements Comparable<String> {
...
int compareTo(String i) {
....
};
}
つまり,比較メソッドを提供するクラス C
は
public class C implements Comparable<C> {
というヘッダで定義がされるのである.
これに対応して「型変数 Elm
は compareTo
メソッドを持つ」ということを表現するためには,
public interface BinarySearchTree<Elm extends Comparable<Elm>> {
...
}
public class Leaf<Elm extends Comparable<Elm>> implements BinarySearchTree<Elm> {
...
}
public class Branch<Elm extends Comparable<Elm>> implements BinarySearchTree<Elm> {
...
}
という定義をする.extends Comparable<Elm>
の部分が追加された部分で,いわば int compareTo(Elm o);
というメソッドを持つ,ということを表現している.4 このおかげで,e.compareTo(v)
というメソッド呼出しが適正なものと認識されるようになる(e
と v
の型はともに Elm
でることに注意せよ.)
このような「型変数の動く範囲」の指定は,しばしば,境界(bound) と呼ばれる.また,bound を指定することができるような多相性の概念の拡張を bounded polymorphism (もしくは constrained polymorphism) と呼ぶ.
min
の実装(例外を投げる)
OCaml の min
の実装を変更する必要があったのと同様,Java でも Elm
を返り値とするメソッドで return -255;
ができるわけではないので,例外を発生させて実行中断をする.
1 2 3 |
|
(今回の講義では例外について説明する時間が全く取れなかったので,上はおまじないだと思ってください.)
使用例
ここまでできてしまえば,使用例は,2分木の時と大して変わらない.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
|
上で述べたように,Integer
, String
ともに Comparable
インターフェースを実装(implements
)しているため,BinarySearchTree
, Leaf
, Branch
の型引数として適当だが,Comparable
を実装していないクラスを書くことはできない.例えば,
BinarySearchTree<Object> t;
という変数宣言をすると,以下のような「型引数が境界内にない」というエラーになる.
Main.java:9: エラー: 型引数Objectは型変数Elmの境界内にありません
BinarySearchTree<Object> t;
^
Elmが型変数の場合:
インタフェース BinarySearchTreeで宣言されているElmはComparable<Elm>を拡張します
エラー1個
Comparable
vs Comparator
C の場合 (C/polyBST)
多相性 + 高階関数
多相的2分木上で map や fold を定義してみよう.基本的な計算の方法は多相的であろうとなかろうと変わらない.主な興味の対象は,これらの型がどのように表現されるか,というところである.
OCaml の場合 (polyTree/tree.ml)
まず,OCaml の場合,treemap
treefold
の定義は配布資料(11)で示したものと 全く 変わらない.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
このふたつの関数に対して,型推論によって,以下のような型が推論される.
val treemap : ('a -> 'b) -> 'a tree -> 'b tree
val treefold : 'a -> ('a -> 'b -> 'a -> 'a) -> 'b tree -> 'a
treemap
の型が我々に教えてくれるのは,木に格納されたデータを変換するための関数の型は 'a -> 'b
となっていて,引数と返値の型は同じでなくてもよい,ということである.渡した関数の型に応じて入力と出力の木の型が決まる.例えば,以下のように,整数の2分木から文字列の2分木へ,または,その逆の変換に使うことができる.
let t26 = treemap (fun i -> string_of_int i ^ " yen") t6
let t36 = treemap String.length t16
treefold
の 'a
は畳み込みの最終結果の型,'b
は2分木に格納されたデータの型を表す.関数引数 f
の型 ('a -> 'b -> 'a -> 'a
) は,f
が左の部分木を再帰的に畳み込んだ結果('a
)と branch のデータ ('b
)と右の部分木を再帰的に畳み込んだ結果('a
) に適用されることを表している.例えば,以下のような呼出しで,文字列の2分木から,全文字列の長さの合計を計算することができる.(ここで 'a
と 'b
は何にあたるか考えてみよ.)
let s = treefold 0 (fun l v r -> l + String.length v + r) t16
Java の場合 (java/polyTree)
Java の場合もメソッドの定義の本体は,配布資料(11) で示したものと(型宣言を除いて)ほとんど変わらないが,実は,OCaml と同レベルの柔軟性(多相性)を得るには少し工夫が必要である.まずは map
について紹介する.
map メソッド,バージョン1
まず,以下は素朴に多相的2分木のインターフェースに map
を追加したものである.f
の型で少し悩むが,使えそうな型が Elm
くらいしかないので,Function<Elm,Elm>
とした.(Function<T,R>
は java.util.function
で定義されているジェネリック・インターフェースで T
から R
への関数(オブジェクト)を表す.)
1 2 3 4 5 |
|
しかし,これでは,同じ型の木への変換しかできず,上の OCaml の例でみたような,整数の2分木から文字列の2分木へといった変換ができない.
map メソッド,バージョン2
バージョン1の欠点を修正しようとしたのが次のバージョン2である.OCaml の treemap
の型スキームに 'a
(変換元の2分木の要素型)と 'b
(変換先の2分木の要素型)が現れていたのと同様に,クラスをふたつの型変数でパラメータ化してみた.
1 2 3 4 5 |
|
これで,うまく行きそうに思えるが,実は不十分である.まず,map
の返り値型の Tree
の型引数の数が足りない.これを適当に決めたとして(Elm
として,返り値型は Tree<Elm2,Elm>
としておこう)も,まだ問題がある.このインターフェース(と対応する Leaf
Branch
クラス)は,
Tree<Integer,String> t = new Branch<Integer,String>(new Leaf<Integer,String>(), 11, new Leaf<Integer,String>());
のように使うことになるが,オブジェクトを作った時点で map
の変換先の要素型も指定しなければいけないので,t
から map
を使って得られる2分木は常に文字列の2分木になってしまう.しかも,map
の返り値型を (いい加減に) Tree<Elm2,Elm>
と定義したので,t.map(...)
の型は Tree<String,Integer>
つまり,もう一度 map
する場合の変換先が今度は整数の2分木に固定されてしまう.
我々は,要素変換関数に応じて,変換後の2分木の要素型を決められるようにしたい.クラス定義に型パラメータ Elm2
を追加するのでは,2分木オブジェクトを作る時に map
時の変換先の型をひとつに定めなければならないわけで,これでは早すぎるのである.
map メソッド,バージョン3(完成版)
Java には,ジェネリック・クラス,ジェネリック・インターフェースだけではなく,ジェネリック・メソッドといって,メソッドに型引数を指定することができる.これを map
の定義に使えば,map
の呼出し毎に変換後の2分木の要素型を指定することができる.ジェネリック・メソッドを使った Tree
の定義が以下である.
1 2 3 4 5 |
|
このように,ジェネリック・メソッドはメソッドの先頭(public
の後)に型変数の宣言(ここでは <Elm2>
)をつける.これをつけると,そのメソッドの返り値型,引数型,本体の中で宣言された型変数(Elm2
)をふつうの型と同じように使うことができる.5 以下が Leaf
, Branch
クラスの map
の定義である.
1 2 3 4 |
|
1 2 3 4 5 6 7 |
|
両メソッド内で2分木を作る時には Leaf<Elm2>
, Branch<Elm2>
と,ジェネリック・メソッドの型変数 Elm2
を使って作っていることに注目しよう.
ジェネリック・メソッドを呼出す時は,以下のように,ドットとメソッド名の間に型引数を指定することができるが,多くの場合,省略することができる.これも一種の型推論である.ここでは,文字列の2分木から,各文字列の長さを格納した整数の2分木を得ている.Elm2
として結果の2分木の要素型 Integer
を指定し,Function<String,Integer>
型のラムダ式を渡している.
1 2 3 4 |
|
fold メソッド
fold も基本的なアイデアは同じである.fold の結果の型は,木が格納している要素の型 Elm
とは独立に呼出し毎に指定したいので,(型パラメータ Result
をとる)ジェネリック・メソッドとして定義する.この時,fold に与える引数を考えると,まず Leaf
の場合を表す引数は Result
型になる.そして,Branch
の場合に使われる関数引数は Result
と Elm
と Result
から Result
を返すものになる.3引数関数オブジェクトのためのインターフェースはライブラリに用意されていないので,以下のように自分で定義をする.
1 2 3 4 |
|
この上で,fold
メソッドは以下のように定義できる.
1 2 3 4 |
|
1 2 3 4 5 6 |
|
例えば,Tree<Integer>
に対して,格納されている整数の和を計算するには,
TriFunction<Integer,Integer,Integer,Integer> f = (n, m, p) -> n + m + p;
System.out.println(t6.fold(0, f));
などとする.fold
の型パラメータ Result
に対して渡される型は fold した結果の Integer
であるが,Java が推論してくれるので書く必要はない.また,Tree<String>
に対して,格納されている文字列の長さの和を計算したければ,
TriFunction<Integer,String,Integer,Integer> f = (l, v, r) -> l + v.length() + r;
// Computes the sum of the lengths of the strings in t18
Integer i = t18.fold(0, f);
などとする.
[ 前の資料 | 講義ホームページ・トップ ]
この宣言は必須ではないが,その場合,
java.util.function.ToIntBiFunction
という名前で参照する必要がでてくる.↩このインターフェースもメソッドは
compare
ひとつ(正確にはオブジェクトが持つべきインスタンス・メソッドがひとつ.他に static メソッドと呼ばれるものが定義されている)なので,ラムダ式を使うことができる.↩意味的には「
implements
していること」という条件なのにextends
を使うのには,いくつか事情があるがここでは説明しない.↩これは実は少し不正確である.実際には,
compareTo
メソッドを持つクラスをComparable
インターフェースをimplements
せずに定義することもできるので,Comparable
をimplements
しているならば,compareTo
を持つ,は正しいが,その逆(compareTo
があるクラスはComparable
をimplements
している)は必ずしも成り立たない.ただし,Java ライブラリで提供しているクラスについては,比較メソッドを持つならばComparable
をimplements
するように設計されている.↩ジェネリック・クラスのようになぜ,メソッドの名前の直後に型変数宣言が来ないのか不思議に思うかもしれない.これは返り値型に型変数が含まれる場合に,型変数の宣言に先行して,型変数の使用箇所が現れるのを防ぐためだと思われる.↩
Copyright 五十嵐 淳, 2016, 2017