続・続・比較モナド〜復讐編〜

Java

もういい加減飽きてるだろうけど続けるよ。今日は比較モナドについて復讐するよ。
ソースコードは抜粋なので全部を見たかったらここ見てください。

事のいきさつ

◆ 「http://d.hatena.ne.jp/terazzo/20110526/1306434704」で「比較条件」のチェーンってモナド的に書けね？と思いついて実装する。

↓
◆「続・比較モナド - terazzoの日記」では、比較条件をチェーンするだけなら、Option( or Maybe)にplusを定義して、比較結果未定=none、比較結果確定=someOf(結果)と考えれば良いと考えてそれで実装してみた。
↓
◆しかし元の設計では比較対象はモナドの中に入れて引き回すようになっていたので、それを維持した形にしつつ、かつ、ネスト出来ない問題に対応したい。

型の整理

比較対象となるデータの対を中に入れて保持するのであれば、Option(or Maybe)というより、Eitherを使ったErrorモナドに近い構造であると思う。両方とも、つまりErrorモナドも比較モナド(自称)も、「特定の状態になるまで処理を続けて行き、その特定の状態になった際に値をセットして処理を中止する(残りの処理をバイパスする)」という同じような動きになっている。例えばパース処理用のErrorモナドで言えば、パース中にエラーが起こったらパースを中止し、パース結果の代わりに行数とメッセージを戻す、というような処理が考えられる。。


対応付けるとすると以下のようになるかな。

　 Errorモナド 比較モナド(自称)
Rightに当たる型 Right Unsettled
Rightの状態の意味 正常に処理を継続中 比較結果が未確定
Rightへのbind 関数を呼び出して戻り値を使用 コンパレータを呼び出して戻り値を使用
Rightのフィールドの中身 パースの結果得られた非エラー値(正しい値) 比較対照となる値の対
Leftに当たる型 Left Settled
Leftの状態の意味 エラー 比較結果が確定
Leftへのbind 関数は呼ばずにLeftを使用 関数は呼ばずにSettledを使用
Leftのフィールドの中身 エラーメッセージや発生箇所などのエラー情報 大・小・等しいなどの比較結果


OOPerになら「Chain of Responsibilityを組み立てるための部品」と言った方が通じるかと思う。
OOPだと「デザインパターンの構造を表現するだけの汎用のクラス」というのはあまり作らず、なんらかの実際の応用にあわせてクラスを作ることが多いと思うけど、関数型言語だと制御構造と具体的なデータや処理の内容を別々に実装して貼りあわせやすいという違いはあるのかもしれない。

処理の流れと内容の分離

比較モナドと言っていたComparisonResultだけど、上記のような処理の流れは、処理の内容が「比較」の時だけに限らないので、処理の内容や対象と、処理の制御部分を分離し、独立して利用できるようにする。

ComparisonResultに該当する部分(モナドとして考えようとしている部分)として、処理状態 ProcessStatusというクラスを定義する。面倒なのでSettle/Unsettleは統合して一つのクラス内で状態を保持するように変えている。

/**
 * 現在の処理状態を表し、処理の続行・中止を制御するためのクラス。
 * 未確定状態の場合、保持している処理対象targetをbind() or map()で渡された関数に渡し、結果を取得する。
 * 確定状態の場合、bind() or map()で渡された関数はバイパスして、resultを最終結果とする。
 * EitherをもとにしたErrorモナドと同じような動きになる。(決着済み=Left、未決着=Right)
 * 
 * @param <R> 処理結果の型
 * @param <T> 処理対象(引数)の型
 */
public final class ProcessStatus<R, T> {
    // 処理対象
    private final T target;
    // 処理結果
    private final R result;
    // 決着がついたかどうかのフラグ
    private final boolean isSettled;
    
    // コンストラクタはプライベート
    private ProcessStatus(T target, R result, boolean isSettled) {
        this.target = target;
        this.result = result;
        this.isSettled = isSettled;
    }
    /* ファクトリメソッド */
    // 決着状態を生成して戻す
    public static <R, T> ProcessStatus<R, T> settled(R result) {
        return new ProcessStatus<R, T>(null, result, true);
    }
    // 未決着状態を生成して戻す
    public static <R, T> ProcessStatus<R, T> unsettled(T target) {
        return new ProcessStatus<R, T>(target, null, false);
    }
    /* 結果を取り出すためのメソッド */
    // 決着がついたかどうかのフラグを戻す
    public boolean isSettled() {
        return isSettled;
    }
    // 結果が確定していればその値を、未確定ならdefaultValueを戻す。
    public R getResult(R defaultValue) {
        return isSettled ? result : defaultValue;
    }
...
}

具体的に「比較処理のチェーンを実装したい」という場合には、処理対象の型Tに比較対象となる値のペアを、処理結果の型Rに比較結果の値を当てはめて使用すればよい。

/**
 * 比較対象となるデータの対を保持するクラス。
 * @param <T> 比較対象となるデータの型
 */
public class Comparatee<T> {
    public final T left;
    public final T right;
    public Comparatee(T left, T right) {
        super();
        this.left = left;
        this.right = right;
    }
    public static <T> Comparatee<T> of(T left, T right) {
        return new Comparatee<T>(left, right);
    }
...
}

/**
 * 比較結果をあらわすEnum
 */
public enum ComparisonResult {
    // 「左側が小さい」という結果
    SMALLER(-1),
    // 「左側と右側が等しい」という結果 
    IDENTICAL(0),
    // 「左側が大きい」という結果
    LARGER(1);

    // 比較結果を負の数、ゼロ、正の数で表したもの
    public final int sign;

    ComparisonResult(int sign) {
        this.sign = sign;
    }
    // ComparableやComparatorと協同しやすいように変換メソッドを定義
    public static ComparisonResult valueOf(int sign) {
        return sign < 0 ? SMALLER
             : sign > 0 ? LARGER
             :            IDENTICAL;
    }
}

これで、例えばEntryというクラスのインスタンスを比較したいときは、ProcessStatus>のように定義して使えばよい。


ProcessStatusのbind()は次のような実装になる。bindする処理は比較処理とは限らないので一般的にFunctionに対して定義している。

public final class ProcessStatus<R, T> {
//... さっきの続き
    /* 拡張スタイル */
    /**
     * ProcessStatusとFunctionからProcessStatusを自然な感じで戻す。
     * 具体的には、決着済みの場合は関数呼び出しを行わずthisを、
     * 未決着の場合にはhandlerにtargetを渡して得た結果を戻す。
     * @param handler bindする関数
     * @param <S> 戻り値のtargetの型
     */
    public <S> ProcessStatus<R, S> bind(Function<T, ProcessStatus<R, S>> handler) {
        if (isSettled) {
            // もう決着済みなのでcomparatorに関係なくthisを戻す。
            // JavaにはNothingとか無いので残念だがキャストでごまかす。
            return (ProcessStatus<R, S>) this;
        } else {
            // 未決着なので関数を呼び出してその結果を使用する。
            return handler.apply(target);
        }
    }
...
}

キャストが残念だがScalaのNothingにあたるようなものが無いので仕方が無い。
isSettled==trueの時は必ずresult==nullなので実行時には型はイレーズされて何も問題ないはず。


これで前回と同じようにソートの処理の合成を書くことができる。

public class ComparisonsTest {
    private List<Entry> entries;
    @Before
    public void initSamples() throws Exception {
        SimpleDateFormat fmt = new SimpleDateFormat("yyyy-MM-dd");
        entries = Arrays.asList(
            new Entry(6, 2, fmt.parse("2011-03-03"), "iPad2欲しいですか？","..."),
            new Entry(5, 2, fmt.parse("2011-01-06"), "今年の抱負","..."),
            new Entry(4, 2, fmt.parse("2011-03-10"), "ブログと私","..."),
            new Entry(3, 2, fmt.parse("2011-02-18"), "これはモナドですか？","..."),
            new Entry(2, 2, fmt.parse("2011-02-18"), "ついつい集めてしまうもの","..."),
            new Entry(1, 1, fmt.parse("2011-02-18"), "ついつい集めてしまうもの","..."));
    }
    // pubDateの降順でソートする時のコンパレータ
    private MComparator<Entry> pubDateComparator = toMComparator(
        new Comparator<Entry>(){
            public int compare(Entry first, Entry second) {
                return -1 * first.getPubDate().compareTo(second.getPubDate());
            }
        });
    // idの昇順でソートする時のコンパレータ
    private MComparator<Entry> idComparator = toMComparator(
        new Comparator<Entry>(){
           public int compare(Entry first, Entry second) {
                return first.getId().compareTo(second.getId());
            }
        });

    @Test
    public void testComparison() {
        //(1)pubDateの降順、(2)idの昇順、という順序でソートする時のComparator
        Comparator<Entry> composedComparator = toComparator(new MComparator<Entry>() {
            protected ProcessStatus<ComparisonResult, Comparatee<Entry>> compare(Entry left, Entry right) {
                return
                    unsettled(left, right)
                    .bind(pubDateComparator)	// (1)pubDateの降順
                    .bind(idComparator);	// (2)idの昇順
            }
        });

        ArrayList<Entry> sorted = new ArrayList<Entry>(entries);
        Collections.sort(sorted, composedComparator);

        // 順番になっているか確認。一つ前と比べると、日付が古い(before)か、日付が等しいならIDが大きいはず。
        Entry last = null;
        for (Entry entry : sorted) {
            assertTrue(
                last == null ||
                entry.getPubDate().before(last.getPubDate()) ||		// 一つ前より日付が古いか、
                (last.getPubDate().equals(entry.getPubDate()) &&
                        entry.getId() > last.getId())			// 日付が等しくIDが大きい
            );
            last = entry;
            System.out.printf("id=%d, pubDate = %s, title=%s\n",
                    entry.getId(), entry.getPubDate(), entry.getTitle());
        }
    }
}

MComparatorはFunction, ProcessStatus>>を実装した抽象スーパークラスとして定義している。定義はこちら

代数スタイルの関数の実装と確認

中で保持する型を型パラメータでとれるようになったので、入れ子になった状態が扱えるようになっている。

public final class ProcessStatus<R, T> {
...
    /* 代数スタイルを拡張スタイルで定義 */
    // flatten = bind(id) = bind(ext(unit))
    public static <R, T> ProcessStatus<R, T> flatten(ProcessStatus<R, ProcessStatus<R, T>> ss) {
        return bind(ss, ext(ProcessStatus.<R, T>unit()));
    }
    // map(f, m) = bind(m, ( \x -> unit (f x) ))
    public static <R, T, S> ProcessStatus<R, S> map(final Function<T, S> f, ProcessStatus<R, T> status) {
        return status.bind(new Function<T, ProcessStatus<R, S>>() {
            public ProcessStatus<R, S> apply(T x) {
                return unit(f.apply(x));
            }
        });
    }
    public static <R, T> Function<ProcessStatus<R, ProcessStatus<R, T>>, ProcessStatus<R, T>> flatten() {
        return new Function<ProcessStatus<R, ProcessStatus<R, T>>, ProcessStatus<R, T>>() {
            public ProcessStatus<R, T> apply(
                    ProcessStatus<R, ProcessStatus<R, T>> status) {
                return flatten(status);
            }
        };
    }

総称型の表記が大変面倒くさいことになってる。
少しでも減らすため比較処理用にショートカットを用意してやる。

package sample.comparator;

import com.google.common.base.Function;

public class Comparisons {
    // 決着状態を生成して戻す(結果の型固定版)
    public static <T> ProcessStatus<ComparisonResult, T> settled(ComparisonResult result) {
        return ProcessStatus.settled(result);
    }
    // 未決着状態を生成して戻す(結果の型固定版)
    public static <T> ProcessStatus<ComparisonResult, T> unsettled(T target) {
        return ProcessStatus.unsettled(target);
    }
    public static <T> ProcessStatus<ComparisonResult, Comparatee<T>> unsettled(T left, T right) {
        return ProcessStatus.unsettled(Comparatee.of(left, right));
    }

    public static <T> ProcessStatus<ComparisonResult, T> unit(T target) {
        return ProcessStatus.unit(target);
    }
    public static <T> Function<T, ProcessStatus<ComparisonResult, T>> unit() {
        return new Function<T, ProcessStatus<ComparisonResult, T>>() {
            public ProcessStatus<ComparisonResult, T> apply(T target) {
                return unit(target);
            }
        };
    }

    public static <T> ProcessStatus<ComparisonResult, T>
    flatten(ProcessStatus<ComparisonResult, ProcessStatus<ComparisonResult, T>> target) {
        return ProcessStatus.flatten(target);
    }

    public static <T, S> ProcessStatus<ComparisonResult, S>
    map(final Function<T, S> f, ProcessStatus<ComparisonResult, T> status) {
        return ProcessStatus.map(f, status);
    }

    public static <T> Function<ProcessStatus<ComparisonResult, ProcessStatus<ComparisonResult, T>>,
                               ProcessStatus<ComparisonResult, T>> flatten() {
        return new Function<ProcessStatus<ComparisonResult,ProcessStatus<ComparisonResult,T>>,
                            ProcessStatus<ComparisonResult,T>>() {
                public ProcessStatus<ComparisonResult, T>
                apply(ProcessStatus<ComparisonResult, ProcessStatus<ComparisonResult, T>> status) {
                    return ProcessStatus.flatten(status);
                }
            };
    }
}


代数スタイルのモナド則を満たしているか。
関数が等しいということは直接テストできないけど、とりあえず同じ入力に対する出力が一致することを確認する。

public class ComparisonsTest {
    // 代数スタイルのモナド則
    @Test
    public void testMonad1() {
        ProcessStatus<ComparisonResult, Comparatee<String>> status = unsettled("left", "right");

        // モナド則(1) flatten(unit(m)) = m
        assertEquals(
                flatten(unit(status)),
                status);
    }
    @Test
    public void testMonad2() {
        ProcessStatus<ComparisonResult, Comparatee<String>> status = unsettled("left", "right");

        // モナド則(2) flatten(map(unit, m)) = m
        assertEquals(
                flatten(map(Comparisons.<Comparatee<String>>unit(), status)),
                status);
    }

    @Test
    public void testMonad3() {
        ProcessStatus<ComparisonResult,
            ProcessStatus<ComparisonResult,
                ProcessStatus<ComparisonResult, Comparatee<String>>>>
            sss = unsettled(unsettled(Comparisons.unsettled("left", "right")));

        // モナド則(3) flatten(flatten(mmm)) = flatten(map(flatten, mmm))
        assertEquals(
                flatten(flatten(sss)),
                flatten(map(Comparisons.<Comparatee<String>>flatten(), sss)));

        System.out.println("sss = " + sss);
        System.out.println("flatten(flatten(sss)) = " + flatten(ProcessStatus.flatten(sss)));
    }
}

最後のprintlnの結果: *1

sss = unsettled(unsettled(unsettled(left, right)))
flatten(flatten(sss)) = unsettled(left, right)


ProcessStatusに対するflattenは、(1)外側が確定状態なら外側を中身の型にキャストして戻す (2) 未確定なら中身を取り出して戻す。という処理になっている。上のflattenの定義を展開すると次のようになるので。

    public static <R, T> ProcessStatus<R, T> flatten(ProcessStatus<R, ProcessStatus<R, T>> ss) {
        // return bind(ss, id)を展開すると
        if (ss.isSettled) {
            return (ProcessStatus<R, T>) ss;
        } else {
            return ss.target;
        }
    }


一応確認

    @Test
    public void testFlattenWhenOutsideIsUnsettle() {
        ProcessStatus<ComparisonResult, ProcessStatus<ComparisonResult, Comparatee<String>>>
            inner = unsettled(Comparisons.unsettled("left", "right"));

        ProcessStatus<ComparisonResult,
            ProcessStatus<ComparisonResult,
                ProcessStatus<ComparisonResult, Comparatee<String>>>>
            outer = unsettled(inner);

        assertEquals(inner, flatten(outer));
    }   
    @Test
    public void testFlattenWhenOutsideIsSettle() {
        ProcessStatus<ComparisonResult,
            ProcessStatus<ComparisonResult,
                ProcessStatus<ComparisonResult, Comparatee<String>>>>
            outer = settled(ComparisonResult.SMALLER);
 
       assertEquals(outer, flatten(outer));
    }

*1:各クラスのtoString()はいい感じに実装してあります。リポジトリ参照。