異なる型のオブジェクトの順序比較が今回のテーマ。
Javaの場合、オブジェクトの順序を比較する王道はふたつある。
ひとつはjava.lang.Comparable *1（こんぺあらぶる）を実装する「自然順序付け」と呼ばれる方法。
public class A implements Comparable<A> { int a; @Override public int compareTo(A o) { return this.a - o.a; } }
もうひとつはjava.util.Comparator （こんぱれーたー）を用いる方法。*2
public class MyComparator implements Comparator<A> { @Override public int compare(A o1, A o2) { return o1.a - o2.a; } }
見て分かるように、Compar - able のほうは比較をするクラス自身にimplementsするが、Compar - ator のほうはクラスAとは無関係なクラスとして実装し、ふたつのオブジェクトを比較する。
継承と比較
先ほど作ったクラスAを継承したクラスBを作る。クラスAはフィールドaをもっていた。クラスBは追加でフィールドbをもち、フィールドaが同じ場合はフィールドbの値で前後を決める。つまり、フィールドaが第一ソートキー、bが第二ソートキーとなるわけだ。
この継承関係はあるにせよ、異種の型を順番に並べたいというシチュエーションが今回のテーマである。まあ業務システムとかでもありそうな感じのシチュエーションでしょ。
まず単純に継承したクラスBでcompareToをオーバーライドしてみる。
public class B extends A { int b; @Override public int compareTo(A o) { int r = super.compareTo(o); if (r != 0) return r; if (o instanceof B) { B ob = (B) o; return this.b - ob.b; } return 1; } }
これはうまく動作しない。クラスB同士の比較であれば大丈夫だが、クラスAとクラスBを比較した場合にa.compareTo(b)とした場合とb.compareTo(a)とした場合とで結果が非対称になることがある。フィールドaの値が同じだった場合、クラスAのcompareTo実装は同値と判断して0を返す。クラスBのcompareTo実装はフィールドbの値の比較を試みる。
そもそもinstanceofがある時点であまり美しくない。クラスBなのにimplements Comparator<A>である点がネックだ。じゃあ、implements Comparable<B>にすればいいのか？
public class B extends A implements Comparable<B>{ ... }
The interface Comparable cannot be implemented more than once with different arguments:
Comparable<A> and Comparable<B>
Javaは型変数違いなだけのinterfaceを二重にimplementsできない。自然順序付けは継承階層のどこかでimplementsすると、その子の階層のクラスではソートキーの追加がうまくおこなえない。
再帰的ジェネリクスの試み
どうにかクラスBをimplements Comparable<B>にできないのか。
子のクラスで自分自身の型を用いたい場合は再帰的ジェネリクスを使うのが王道だ。*3当blogを購読している奇特な人達にはもうお馴染みだね。
public class A<T extends A<T>> implements Comparable<T>{ int a; @Override public int compareTo(T o) { return this.a - o.a; } } public class B extends A<B>{ int b; @Override public int compareTo(B o) { int r = super.compareTo(o); if (r != 0) return r; return this.b - o.b; } }
これでinstanceofが除外できたが、こうなるとAはA同士、BはB同士でしか比較できない。というか、この再帰的ジェネリクス使うとA型が型安全にnewできない…。
というわけで、Compar-ableのほうは継承関係のあるクラス間での比較というのは無理筋っぽい。compareToは実質的にはオーバーライドできないメソッドと考えるべきことのようだ。
Compar-ator での比較
「こんぺあらぶる」は諦めて「こんぱれーたー」の方で考えてみよう。
interface Comparator<T>の宣言を見ると
int compare(T o1, T o2);
となっている。そもそも、compareは比較対象のふたつの型が同じであることをまず前提としている。もう、なんていうか無謀な感じがこのへんでぷんぷんする。
まず、この型変数Tに何をバインドするかという話だが、これはもう、対象となるクラス継承階層の一番上位のものを指定するより仕方がない。今の場合だとクラスAだ。
public class MyComparator2 implements Comparator<A> { @Override public int compare(A o1, A o2) { int r = o1.a - o2.a; if (r != 0) { return r; } if (o1 instanceof B) { if (o2 instanceof B) { B b1 = (B)o1; B b2 = (B)o2; return b1.b - b2.b; } else { return -1; } } else { if (o2 instanceof B) { return 1; } } // B 以外のインスタンスの場合 return 0; } }
と、ここまで書いてわずかAとBの2階層でしかないのにinstanceofの山となるのを見て筋の悪さを実感する。
実装型をinstanceofで処理するぐらいならいっそAとかBに比較処理を書いてポリモーフィズムで処理するか。ところがこれがまたイマイチなのだ。
例えばクラスBに比較メソッドを書いてみよう。
public int compare(A a) { // ... }
比較するためにこのメソッドを呼ぶ場合、呼び出し側は例えば以下のようになる
A a1 = new B(); A a2 = new B(); a1.compare(a2);
んで、a1は宣言型はクラスAだけど、実体がクラスBなのでポリモフィズムによって先程のcompareメソッドに行き着く。compareメソッド内ではthisがクラスBであることは分かるが、比較対象のa2の具象型が何かは分からない。ただA型か、A型を継承した何かであるということだけが分かる。
しょうがないから、
public int compare(A a) { return a.compare(this); }
などとすると、a2の具象型であるクラスBのcompareが呼び出され、今度はa1が何型だったか分からなくなる。そして無限ループに陥るわけである。
ダブルディスパッチ、Visitorパターン
ここでVisitorパターンを応用する。VisitorパターンというといわゆるダブルディスパッチのC++型オブジェクト指向言語*4での解法とされる。ダブルディスパッチってなんなのって言われると僕も自信があまりないのだが、ポリモフィズムが単一のオブジェクトの具象型による分岐だとすれば、ふたつの型の具象型の組み合わせによって分岐をするのがダブルディスパッチということなんだろうか。WikipediaによるとCommon Lispだとできるとかなんとか。勉強不足ですいません。
んで、Visitorパターンなのだけど、GoFデザインパターンでもっとも複雑怪奇とよく言われる。
これを簡単に説明すると、ポリモフィズムで分岐をして、具象型で実処理をするというケースがあったとして、
このままだと、具象型ごとに処理が分散してしまうし、処理そのものをStrategyパターン的に切り替えたいんだよねってなるとちょっと難しい。そこで、それぞれの具象型での処理をStrategyパターンにして以下の図のように処理の流れを作る。
具象型はVisitorへの中継だけを行うようにするわけだ。
このとき、ポリモフィズムによる分岐で具象型のメソッドに処理が流れている最中は、自分が何型かを知ることができる。知ることができるのでStrategyの型別に用意したメソッドのうち、自分の型が処理されるべきメソッドを呼び出すことができる。
んで、Strategyは適当な名前でもいいんだけど、メソッド名は慣習にならってacceptにしてやれ、型ごとに処理は分けるけど引数の型が違うのでオーバーロードでいいや、ってするとVisitorパターンの格好になる。
抽象から具象へ
そんなVisitorパターンでは具象型別に処理を書き分けることができるわけだ。これは、プログラム言語の構文解析のようなシチュエーションでよく用いられる。構文要素を型で表現し、どの要素が出てきたらどういう処理をする、というコンパイラの動作をVisitorパターンで記述するというのがよくあるパターンだ。
このVisitorパターン、要素の方の具象型に何があるかを予め網羅しておく必要があるため要素を追加するのが容易ではない。Strategyパターン同様に処理を追加するのは容易だ。
ともかく、この手法によって抽象型を具象型に変えることが出来るというのがミソなのだ。
さて、ここではCompiler Tree APIのVisitorパターンをお手本にしてみよう。
抽象構文木のノードを表現するTreeインターフェースとTreeVisitorインターフェースである。
古典的にはVisitorパターンのacceptの引数はvisitorの実体ひとつだが、拡張して追加の引数と戻り型を加える。この型変数DとRは必要に応じて好きにデータを投入して良い。*5
public interface Visitor<D, R> { R visit(A a, D data); R visit(B b, D data); } public interface Accepter { <D, R> R accept(Visitor<D, R> visitor, D data); }
このように、Visitorパターンそのものを抽象化しておく。
まずはクラスAとBのAccepterの実装をみてみよう
public class A implements Accepter { @Override public <D, R> R accept(Visitor<D, R> visitor, D data) { return visitor.visit(this, data); } } public class B extends A { @Override public <D, R> R accept(Visitor<D,R> visitor, D data) { return visitor.visit(this, data); } }
A型のacceptメソッドを呼び出すとポリモフィズムでクラスAのaccept, クラスBのacceptへと処理が分岐する。それぞれの実装はVisitorのvisit(A,D)とvisit(B,D)を呼び出す。具象型によってVisitorのメソッドが呼び分けられるわけだ。acceptメソッドにはメソッドをスコープとする型変数D,Rがあり、一連の呼び出しの型の整合性を保証する。
しかし、今回は異種型のオブジェクトの比較であった。Visitorによって抽象型から具象型の分岐に変えることが出来たのは１つのオブジェクト（ここではAとかBとか）だけだ。比較にはふたつオブジェクトが出てくる。どうするのか？
二重Visitor
ウォッカにクラマトジュース（ハマグリの出汁で味付けされたトマトジュース）を混ぜて一杯引っ掛けながら呟く。
「ひとつのVisitorでひとつのオブジェクトを具象型にすることしか出来ないなら二回Visitorを通せばいいじゃない。 by マリー・アントワネット :-P」
Visitorには与えられた抽象型をinstanceofを使わずに具象型別の分岐に変える力がある。それが一度にひとつだけというだけのことだ。
まず、最初のVisitorでは比較対象となるa1, a2のうち、a1を具象化させる。
int ret = a1.<A, Integer>accept(new FirstVisitor(), a2);
そのため、a1のacceptを呼び出し、このときの追加データにa2を渡しておく。返り値は「こんぺあらぶる」「こんぱれーたー」に準じてintとしよう。
このFirstVisitorの実装は以下のようになる。
public class FirstVisitor implements Visitor<A, Integer>{ @Override public Integer visit(A a1, A a2) { return a2.accept(new AVisitor(), a1); } @Override public Integer visit(B b1, A a2) { return a2.accept(new BVisitor(), b1); } }
注目すべきはvisitの引数が(A, A)と(B, A)となっている点である。ここでまずa1がA型かB型か分岐できているということだ。ここで、a1がA型のときとB型のときで二種類のVisitorに処理を委譲しよう。a2のacceptを呼び出してa2を具象型にする。
public class AVisitor implements Visitor<A, Integer>{ @Override public Integer visit(A a2, A a1) { // A-Aの比較 return a1.a - a2.a; } @Override public Integer visit(B b2, A a1) { // A-Bの比較 return -1; } } public class BVisitor implements Visitor<B, Integer> { @Override public Integer visit(A a2, B b1) { // B-Aの比較 return 1; } @Override public Integer visit(B b2, B b1) { // B-Bの比較 int ret = b1.a - b2.a; if (ret != 0) return ret; return b1.b - b2.b; } }
今度はvisitの引数が(A,A) (A,B) (B,A) (B,B)になっている点に注目。これによって型の組み合わせごとに比較処理を記述することができるようになったわけだ。
おいしいブラッディ・シーザーで乾杯！*6
まとめ
異種型の比較という分かりやすいテーマだが、Javaの型システムの盲点か、非常に難儀することを指摘した。
Comparable「こんぺあらぶる」は異種型で用いるとa1.compareTo(a2)とa2.compareTo(a1)で
整合性がとれなくなる場合があり、異種型の比較には使えない。このcompareToメソッドはオーバーライド不可であると考えるべきもののようだ。
Comparator「こんぱれーたー」の場合、異種型での比較を安直に実装しようとするとinstanceofの山となってしまう。instanceofはJavaの型システムの中では邪道であまりinstanceofの分岐をするべきものではない。
そこで、Visitorパターンで使われるテクニックを応用することで渡された抽象型から具象型の分岐をすることができることを示した。
オブジェクトの比較に際しては抽象型ふたつを渡されてその組み合わせが必要になるのでこのテクニックを二重に用いることで対応できることを示した。
このひとつずつ解決する手法はカリー化に着想を得たものだ。当初のソースではAVisitorはコンストラクタでa1を受け取って保持するようにしていた。まさにカリー化の様相だったが、acceptの追加データ部に渡せることに気付いて書き直した。最終的にはカリー化の風情はなくなっているが、着想的にはVisitorを多重にかけてカリー化を行うという方向性だったことを記しておこう。
型システムの妙はひょんなところに隠れている。
補足 ソートするには
でこれを使ってsortするのは？
上記の設計手法でComparatorを実装したら、もはや好きにソートできる状態にあるわけだが、JavaのAPIをよく知らない人のために補足しておこう。
単にjava.util.List(というかjava.util.Collectionの派生)をソートしたいならCollections#sortメソッドを用いる。配列をソートしたいならArrays#sortメソッドを用いる。
Setをソートされた状態に保ちたければTreeSetを使用する。Mapのキーをソートされた状態に保つならTreeMapを使用する。
このようにComparatorの実装さえできてしまえば、多様なライブラリを活用することができる。Comparatorの使いどころを知りたければjavadocのインタフェース java.util.Comparator の使用のページを参照するとよい。
*1:このjavadocは日本語版なのだが、なぜかこのComparableのページは英語になってしまっている。ダウンロード版だと日本語なのでなにか取り違えたのだろう
*2:ひらがな表記したのは英語表記の場合に字面が紛らわしいため
*3:再帰的ジェネリクスの代入互換性 - プログラマーの脳みそは難解なのでJavaジェネリクス再入門 - プログラマーの脳みそあたりを参照
*4:JavaやC#はこの系譜だ。そもそもオブジェクト指向とは論はここではやらない
*5:このようなシチュエーションの型変数で使用する必要がなければjava.lang.Voidをバインドしておいて潰しておく
*6:トマトジュースの代わりにクラマトジュースを使ったバリエーションはブラッディ・シーザー。ウォッカ+トマトジュースのブラッディ・マリーではない:-P
