比較モナド
前回は「ソート順(order by句)の情報から、特定レコードの上界／下界を求めるクエリ(where句)を自動生成する」というのをやった。
その時のwhere句の形
... AND ((t0.pub_date < t2.pub_date) OR ((t0.pub_date = t2.pub_date) AND (t0.id > t2.id))))
を見ていて気が付いたんだけど、ソート順の合成って実は「一つ前の比較までで大小が判別されていない場合だけ、その比較条件を使用する」という形になっている。
SQLだったらorder by句にカンマ区切りで繋いで行けば良いのだけど、Javaのプログラム中で同じようなことをする場合どう書けば良いだろう。
一般的に
- 同じような種類の処理を合成して大きな処理を組み立てたい
- 前処理の結果によって次処理の適用方法が変わる
的な処理の合成はモナドで自然に書けるかも。ということでその線で書いてみた。
ただ、処理系がモナドをサポートしてくれる言語でなければ、見た目が幾分すっきりするという以外はあんまり意味は無い気もする。
まあ勉強用ということで。
ちなみにApache Commons LangにCompareToBuilderというクラスがあって、もっと簡単に同じようなことが出来るので使うと良いと思う。
(6/18 追記)
準備: 普通にComparatorを書く
日記の各記事を表すWeblogEntriesってクラスがあったとする。
package sample.comparator; import java.util.Date; public class WeblogEntries { private final Integer id; private final Integer weblogId; private final String title; private final String content; private final Date pubDate; public WeblogEntries(Integer id, Integer weblogId, String title, String content, Date pubDate) { // nullは許可しない方向で。 if (id == null || pubDate == null) { throw new IllegalArgumentException("id or pubDate is null"); } this.id = id; this.weblogId = weblogId; this.title = title; this.content = content; this.pubDate = pubDate; } public Integer getId() { return id; } ...(以下getterメソッド)
これに対して、(1)pubDateの降順、(2)idの昇順、という順序でソートする時のComparatorを普通に書き下してみる。
public class WeblogEntriesComparator implements Comparator<WeblogEntries> { @Override public int compare(WeblogEntries entry1, WeblogEntries entry2) { // pubDateを比較 Date pubDate1 = entry1.getPubDate(); Date pubDate2 = entry2.getPubDate(); int comparison = pubDate1.compareTo(pubDate2); if (comparison != 0) { // 降順なので逆にする return -1 * comparison; } // pubDateが等しい場合のみ、idを比較 Integer id1 = entry1.getId(); Integer id2 = entry2.getId(); // IDの昇順 return id1.compareTo(id2); } }
テストデータをソートしてみる。
// テストデータ List<WeblogEntries> entries = Arrays.asList( new WeblogEntries(6, 2, "iPad2欲しいですか？", "...", fmt.parse("2011-03-03")), new WeblogEntries(5, 2, "今年の抱負", "...", fmt.parse("2011-01-06")), new WeblogEntries(4, 2, "ブログと私", "...", fmt.parse("2011-03-10")), new WeblogEntries(3, 2, "これはモナドですか？", "...", fmt.parse("2011-02-18")), new WeblogEntries(2, 2, "ついつい集めてしまうもの", "...", fmt.parse("2011-02-18")), new WeblogEntries(1, 1, "ついつい集めてしまうもの", "...", fmt.parse("2011-02-18"))); // ソートして表示してみる ArrayList<WeblogEntries> target = new ArrayList<WeblogEntries>(entries); Collections.sort(target, new WeblogEntriesComparator()); for (WeblogEntries entry : target) { System.out.printf("id=%d, pubDate = %s, title=%s\n", entry.getId(), entry.getPubDate(), entry.getTitle()); }
結果
id=4, pubDate = Thu Mar 10 00:00:00 JST 2011, title=ブログと私 id=6, pubDate = Thu Mar 03 00:00:00 JST 2011, title=iPad2欲しいですか？ id=1, pubDate = Fri Feb 18 00:00:00 JST 2011, title=ついつい集めてしまうもの id=2, pubDate = Fri Feb 18 00:00:00 JST 2011, title=ついつい集めてしまうもの id=3, pubDate = Fri Feb 18 00:00:00 JST 2011, title=これはモナドですか？ id=5, pubDate = Thu Jan 06 00:00:00 JST 2011, title=今年の抱負
これをベースに、compare()の内容を整理していく
方針
pubDateで比較している部分と、idで比較している部分を分割し、全体をその合成として表せるようにしたい。
上で書き下したComparatorを見ると、一つ目の比較(pubDate)で大小の決着が着かない場合のみ、次のIDの比較を行っている。つまり、一つ目の比較の結果(comparison)が"0"であるのは、「等しい」ことを表しているのではなく、「結果が未確定」であることを表していると考える。
そこで、比較結果を表現するインタフェース ComparisonResult を作り、その実装クラスとして決着済み SettledResult と未決着 UnsettledResult を実装する。また、ComparisonResultを戻す比較クラスMComparatorを定義し、MComparatorを合成していけるようにする。
実装その1 基本的なクラスの関係を定義
package sample.comparator; /** * 比較結果を表すインタフェース。 * @param <T>比較対象の型 */ public interface ComparisonResult<T> { // 結果を数値で表現したもの。左側が小さい場合負の整数、左側が大きい場合正の整数、 // 等しいまたは不定の場合に0を戻す int sign(); }
Tは比較対象の型で、今回の場合WeblogEntriesクラスがその型になる。javaのComparatorとの協調が取れるようにsign()メソッドを用意しておく。
コンパレータはjava.util.Comparatorと紛らわしくないようにMComparatorという名前にしておく
package sample.comparator; /** * 比較結果をComparisonResultで戻すコンパレータ。 * @param <T>比較対象の型 */ public interface MComparator<T> { ComparisonResult<T> compare(T left, T right); }
UnsettledResultは未決着の状態を表すクラス。比較対象の情報を保持する。
package sample.comparator; final class UnsettledResult<T> implements ComparisonResult<T> { private final T left; private final T right; UnsettledResult(T left, T right) { this.left = left; this.right = right; } // 未決着だが、最後まで未決着=等しいと考えられるので、0を戻す。 public int sign() { return 0; } }
SettledResultは大小の決着がついている状態を表すクラス。決着済みの場合、比較対象についての情報を保持する必要はもう無い。決着状態だけを保持する。
package sample.comparator; final class SettledResult<T> implements ComparisonResult<T> { // 決着状態を表す数値 private final int sign; SettledResult(int sign) { this.sign = sign; } // コンストラクタで指定したsignを戻す。 public int sign() { return this.sign; } }
SettledResultやUnsettledResultを生成する為のユーティリティクラスを作る。
package sample.comparator; @SuppressWarnings({"unchecked", "rawtypes"}) public final class Comparisons { private static final int SIGN_MINUS = -1; private static final int SIGN_PLUS = 1; private static final int SIGN_ZERO = 0; private static SettledResult SMALLER = new SettledResult(SIGN_MINUS); // 「左側が小さい」という結果を取得 public static <T> ComparisonResult<T> smaller() { return (ComparisonResult<T>) SMALLER; } private static SettledResult LARGER = new SettledResult(SIGN_PLUS); // 「左側が大きい」という結果を取得 public static <T> ComparisonResult<T> larger() { return (ComparisonResult<T>) LARGER; } private static SettledResult IDENTICAL = new SettledResult(SIGN_ZERO); // 「左側と右側が等しい」という結果を取得 ※後で説明 public static <T> ComparisonResult<T> identical() { return (ComparisonResult<T>) IDENTICAL; } // 未決着状態を生成して戻す public static <T> ComparisonResult<T> unsettled(T left, T right) { return new UnsettledResult<T>(left, right); } }
これらを使って、例えばpubDateを比較するMComparatorは次のように書ける。
MComparator<WeblogEntries> pubDateComparator =
new MComparator<WeblogEntries>() {
public ComparisonResult<WeblogEntries> compare(WeblogEntries left, WeblogEntries right) {
int sign = left.getPubDate().compareTo(right.getPubDate());
return sign < 0 ? Comparisons.<WeblogEntries>smaller()
: sign > 0 ? Comparisons.<WeblogEntries>larger()
: Comparisons.unsettled(left, right);
}
};
結果のComparisonResultの内容を知るには、smaller()、larger()と==比較するか、sign()メソッドの結果の正負 or 0で確認する。
java.util.Comparatorと組み合わせて使いやすいように、アダプターを用意しても良いかも。
public static <T> MComparator<T> toMComparator(final Comparator<T> comparator) { return new MComparator<T>() { public ComparisonResult<T> compare(T left, T right) { int sign = comparator.compare(left, right); return sign < 0 ? Comparisons.<T>smaller() : sign > 0 ? Comparisons.<T>larger() : unsettled(left, right); } }; } public static <T> Comparator<T> toComparator(final MComparator<T> comparator) { return new Comparator<T>() { public int compare(T left, T right) { return comparator.compare(left, right).sign(); } }; } ... MComparator<WeblogEntries> pubDateComparator = toMComparator( new Comparator<WeblogEntries>(){ public int compare(WeblogEntries left, WeblogEntries right) { return left.getPubDate().compareTo(right.getPubDate()); } });
実装その2 比較モナドを作る
まず、unit(またはreturn)だけど、これはunsettledをそのまま使えば良いかも。
Comparisonsに追加する。
package sample.comparator; @SuppressWarnings({"unchecked", "rawtypes"}) public final class Comparisons { ... public static <T> ComparisonResult<T> unit(T left, T right) { return unsettled(left, right); } }
bindは「ComparisonResultとMComparatorからComparisonResultを戻す」形になる。
ComparisonResultに「MComparatorを受け取ってComparisonResultを戻す」メソッドとして定義する。
public interface ComparisonResult<T> { // 結果を数値で表現したもの。左側が小さい場合-1、左側が大きい場合1 // 等しいまたは不定の場合に0を戻す int sign(); // ↓ NEW!! // ComparisonResultとMComparatorからComparisonResultを自然な感じで戻す。 ComparisonResult<T> bind(MComparator<T> comparator); }
bindの内容は「前回の比較結果で大小が確定していればその結果を、そうでなければ新しいMComparatorの適用結果を戻す」という処理になる。
関数型言語ならvariantとmatchingで書くところかもしれないけど、ここはJavaなのでそれぞれのクラスに実装を書いて多態で処理の切り分けをしたい。
SettledResultでは、既に結果は決着済みであり、comparatorの内容に関わらずthisを戻す。
package sample.comparator; final class SettledResult<T> implements ComparisonResult<T> { // 決着状態を表す数値 private final int sign; SettledResult(int sign) { this.sign = sign; } // コンストラクタで指定したsignを戻す。 public int sign() { return this.sign; } // NEW!! bindの定義 // もう決着済みなのでcomparatorに関係なくthisを戻す public ComparisonResult<T> bind(MComparator<T> comparator) { return this; } }
UnsettledResultでは、comparatorのcompare()を呼び出してその結果を戻す。
package sample.comparator; final class UnsettledResult<T> implements ComparisonResult<T> { private final T left; private final T right; UnsettledResult(T left, T right) { this.left = left; this.right = right; } // 未決着だが、最後まで未決着=等しいと考えられるので、0を戻す。 public int sign() { return 0; } // NEW!! bindの定義 // comparatorのcompare()を呼び出してその結果を戻す。 public ComparisonResult<T> bind(MComparator<T> comparator) { return comparator.compare(left, right); } }
使用例1: WeblogEntriesのComparatorを書き直す。
上のtoMComparatorを使ってpubDateComparatorとidComparatorを定義。pubDateComparatorは降順なので符号を入れ替えている。
public class WeblogEntriesComparator implements Comparator<WeblogEntries> { private MComparator<WeblogEntries> pubDateComparator = Comparisons.toMComparator( new Comparator<WeblogEntries>(){ public int compare(WeblogEntries left, WeblogEntries right) { return -1 * left.getPubDate().compareTo(right.getPubDate()); } }); private MComparator<WeblogEntries> idComparator = Comparisons.toMComparator( new Comparator<WeblogEntries>(){ public int compare(WeblogEntries left, WeblogEntries right) { return left.getId().compareTo(right.getId()); } }); /*
これを使ってWeblogEntriesComparatorのcompareを書き直すとこうなる。
*/
public int compare(WeblogEntries entry1, WeblogEntries entry2) {
return Comparisons.unit(entry1, entry2)
.bind(pubDateComparator)
.bind(idComparator)
.sign();
}
}動かしてみる。(テストデータとソートするコードは上のものと同じ)
id=4, pubDate = Thu Mar 10 00:00:00 JST 2011, title=ブログと私 id=6, pubDate = Thu Mar 03 00:00:00 JST 2011, title=iPad2欲しいですか？ id=1, pubDate = Fri Feb 18 00:00:00 JST 2011, title=ついつい集めてしまうもの id=2, pubDate = Fri Feb 18 00:00:00 JST 2011, title=ついつい集めてしまうもの id=3, pubDate = Fri Feb 18 00:00:00 JST 2011, title=これはモナドですか？ id=5, pubDate = Thu Jan 06 00:00:00 JST 2011, title=今年の抱負
日付が降順で、日付が同じものについてはid順になっている
ソート順序を入れ替えたり、ソート条件を増やしたい場合等も、bindする順番を変えるだけで良い。SQLのorder by句並に気軽に書ける。
使用例2: 『Java: The Good Parts』の打率ソートの例を書き直す。
『Java: The Good Parts』
には、選手を打率順にソートするサンプルが載っている。(P.118)
package org.orielly.javaGoodParts.examples.impl; import java.util.Comparator; ... public class BattingComparator implements Comparator<Player> { @Override public int compare(Player o1, Player o2) { float o1A, o2A; int retVal; if (o1.getId() == o2.getId()) return 0; if (o1.hasRole(Player.Roles.Batter)) { try { o1A = o1.asBatter().getAverage(); } catch (NotEnoughAtBatsException e) { o1A = 0.0f; } } else o1A = 0.0f; if (o2.hasRole(Player.Roles.Batter)) { try { o2A = o2.asBatter().getAverage(); } catch (NotEnoughAtBatsException e) { o2A = 0.0f; } } else o2A = 0.0f; if (o1A < o2A) retVal = -1; else if (o2A < o1A) retVal = 1; else if (o1.getId() < o2.getId()) retVal = -1; else retVal = 1; return retVal; } }
ちょっと長いしごちゃごちゃしてるので書き直すよ。
方針としては、仕様コンパチを目指さずにコードの意図するところを再現することにしたい。コードではBatterロールを持たない場合と、打数が規定値に達しない場合(その場合NotEnoughAtBatsExceptionが投げられる)については打率を0.0fにしている。これでソートすると「打数規定値以上だが安打=0のバッター」「打数が規定値に達しないバッター」「バッター以外」がリストの最後に混在して出力されるが、多分「打数規定値以上だが安打=0のバッター」＞「打数が規定値に達しないバッター」＞「バッター以外」で整列してる方が良いだろう。
まず、最初にidを比較して同一選手の場合は即座に0を戻している。
if (o1.getId() == o2.getId()) return 0;
この部分を再現するMComparatorを実装する。
Comparisons.identical()は「左側と右側が等しい」という「決着済み結果」を戻す。これを使うことでそれ以降の余分な比較を行わなくする。
private MComparator<Player> identicalComparator = new MComparator<Player>() { public ComparisonResult<Player> compare(Player o1, Player o2) { return o1.getId() == o2.getId() ? Comparisons.<Player>identical() : Comparisons.unsettled(o1, o2); } };
次に、PlayerがBatterロールを持つかどうかをチェックしている。
if (o1.hasRole(Player.Roles.Batter)) { ... } else o1A = 0.0f; if (o2.hasRole(Player.Roles.Batter)) { ... } else o2A = 0.0f;
この部分を再現するMComparatorを実装する。
「ロールを持っている」＞「ロールを持っていない」という順序を用意する。両方ともロールを持っている場合、または両方とも持っていない場合はunsettledとする。
private MComparator<Player> roleComparator = new MComparator<Player>() { public ComparisonResult<Player> compare(Player o1, Player o2) { return o1.hasRole(Player.Roles.Batter) ? o2.hasRole(Player.Roles.Batter) ? Comparisons.unsettled(o1, o2) // 両方バッター : Comparisons.<Player>larger() // 左側だけバッター : o2.hasRole(Player.Roles.Batter) ? Comparisons.<Player>smaller() // 右側だけバッター : Comparisons.unsettled(o1, o2); // 両方バッターでない } };
次に、打率を取得するついでに打数が規定値に達しているかを見ている。
try { o1A = o1.asBatter().getAverage(); } catch (NotEnoughAtBatsException e) { o1A = 0.0f; } ... try { o2A = o2.asBatter().getAverage(); } catch (NotEnoughAtBatsException e) { o2A = 0.0f; }
この部分を再現するMComparatorを実装する。
「打率が取得出来る」＞「打率が取得出来ない(NotEnoughAtBatsExceptionをcatch)」という順序を用意する。両方とも取得出来る、または両方とも取得できない場合はunsettledとする。
private MComparator<Player> enoughAtBatsComparator = new MComparator<Player>() { public ComparisonResult<Player> compare(Player o1, Player o2) { if (!o1.hasRole(Roles.Batter) || !o2.hasRole(Roles.Batter)) { return Comparisons.unsettled(o1, o2); } // 打席数十分かを比較 try { o1.asBatter().getAverage(); try { o2.asBatter().getAverage(); return Comparisons.unsettled(o1, o2); // 両方とも例外無し } catch (NotEnoughAtBatsException e) { return Comparisons.larger(); // 右側だけ例外 } } catch (NotEnoughAtBatsException e) { try { o2.asBatter().getAverage(); return Comparisons.smaller(); // 左側だけ例外 } catch (NotEnoughAtBatsException e2) { return Comparisons.unsettled(o1, o2); // 両方とも例外 } } } };
打席数の判定の前にロールのチェックをおこない、両方がBatterロールを持っている場合のみ打席数が足りているかの判定をおこなう。どちらかがBatterロールを持っていない場合はこのコンパレータの関知するところではないので、unsettledを戻す。
次に、打率を比較している。
if (o1A < o2A) retVal = -1; else if (o2A < o1A) retVal = 1;
この部分を再現するMComparatorを実装する。
private MComparator<Player> averageComparator = new MComparator<Player>() { public ComparisonResult<Player> compare(Player o1, Player o2) { if (!o1.hasRole(Roles.Batter) || !o2.hasRole(Roles.Batter)) { return Comparisons.unsettled(o1, o2); } float o1A; float o2A; try { o1A = o1.asBatter().getAverage(); o2A = o2.asBatter().getAverage(); } catch (NotEnoughAtBatsException e2) { return Comparisons.unsettled(o1, o2); } // 打率を比較 return o1A < o2A ? Comparisons.<Player>smaller() : o1A > o2A ? Comparisons.<Player>larger() : Comparisons.unsettled(o1, o2); } };
打率の比較の前にロールとNotEnoughAtBatsException例外のチェックをおこない、両方がBatterロールを持っていて規定打数に達している場合のみ、打率の比較をおこなう。どちらかがBatterロールを持っていないか、規定打数に達していなければ、このコンパレータの関知するところではないので、unsettledを戻す。
最後に、idを比較している。
... else if (o1.getId() < o2.getId()) retVal = -1; else retVal = 1; return retVal;
この部分を再現するMComparatorを実装する。
private MComparator<Player> idComparator = new MComparator<Player>() { public ComparisonResult<Player> compare(Player o1, Player o2) { return o1.getId() < o2.getId() ? Comparisons.<Player>smaller() : o1.getId() > o2.getId() ? Comparisons.<Player>larger() : Comparisons.unsettled(o1, o2); } };
これらのMComparatorを使って、BattingComparatorのcompare()を実装する。
public int compare(Player o1, Player o2) { return Comparisons.unit(o1, o2) .bind(identicalComparator) .bind(roleComparator) .bind(enoughAtBatsComparator) .bind(averageComparator) .bind(idComparator) .sign(); }
一旦この形にしてしまえば、他の統計値でソートしたい時にも同じ形でcompare()をすっきり書けて良いと思う。
しかし今回の例だと前段でチェックしている内容を後段でも実施したりしているのであんまりおいしくないかも……
「ルールは大事よね」
WeblogEntriesComparatorで作ったpubDateComparatorとidComparatorとテストデータでモナド則(axioms)の確認をする。
関数が等しいということは直接テストできないけど、とりあえず同じ入力に対する出力が一致することを確認する。
その1.「(return x) >>= f ≡ f x」
public void testRule1() { ArrayList<WeblogEntries> target1 = new ArrayList<WeblogEntries>(entries); ArrayList<WeblogEntries> target2 = new ArrayList<WeblogEntries>(entries); Collections.sort(target1, new Comparator<WeblogEntries>() { public int compare(WeblogEntries entry1, WeblogEntries entry2) { return Comparisons.unit(entry1, entry2) .bind(pubDateComparator) .sign(); } }); Collections.sort(target2, new Comparator<WeblogEntries>() { public int compare(WeblogEntries entry1, WeblogEntries entry2) { return pubDateComparator.compare(entry1, entry2) .sign(); } }); assertEquals(target1, target2); }
その2. 「m >>= return ≡ m」
private MComparator<WeblogEntries> unit = new MComparator<WeblogEntries>() { public ComparisonResult<WeblogEntries> compare(WeblogEntries left, WeblogEntries right) { return Comparisons.<WeblogEntries>unit(left, right); } }; public void testRule2() { ArrayList<WeblogEntries> target1 = new ArrayList<WeblogEntries>(entries); ArrayList<WeblogEntries> target2 = new ArrayList<WeblogEntries>(entries); Collections.sort(target1, new Comparator<WeblogEntries>() { public int compare(WeblogEntries entry1, WeblogEntries entry2) { return pubDateComparator.compare(entry1, entry2) .bind(idComparator) .bind(unit) .sign(); } }); Collections.sort(target2, new Comparator<WeblogEntries>() { public int compare(WeblogEntries entry1, WeblogEntries entry2) { return pubDateComparator.compare(entry1, entry2) .bind(idComparator) .sign(); } }); assertEquals(target1, target2); }
その3. 「(m >>= f) >>= g ≡ m >>= ( \x -> (f x >>= g) )」
public void testRule3() { ArrayList<WeblogEntries> target1 = new ArrayList<WeblogEntries>(entries); ArrayList<WeblogEntries> target2 = new ArrayList<WeblogEntries>(entries); Collections.sort(target1, new Comparator<WeblogEntries>() { public int compare(WeblogEntries entry1, WeblogEntries entry2) { return Comparisons.unit(entry1, entry2) .bind(pubDateComparator) .bind(idComparator) .sign(); } }); Collections.sort(target2, new Comparator<WeblogEntries>() { public int compare(WeblogEntries entry1, WeblogEntries entry2) { return Comparisons.unit(entry1, entry2) .bind(new MComparator<WeblogEntries>() { public ComparisonResult<WeblogEntries> compare(WeblogEntries left, WeblogEntries right) { return pubDateComparator.compare(left, right).bind(idComparator); } }).sign(); } }); assertEquals(target1, target2); }
