Javaで状態モナド - terazzoの日記

そろそろモナド変換子のことを覚えたいなーと思ったものの、見つけたサンプルが状態モナドを例にとっていたので、学習の準備としてひとまず状態モナドの実装を写経してみることにした。Javaで。

参考にするページ:

ソースコード

例によって「モナドのすべて」から写経するよ。

// libraryDependencies += "org.apache.commons" % "commons-lang3" % "3.0.1"
// libraryDependencies += "com.google.guava" % "guava" % "10.0.1"
import org.apache.commons.lang3.builder.ToStringBuilder;
import com.google.common.base.Function;

/**
 * 状態モナド
 *
 * @param <S> 状態の型
 * @param <A> 値の型
 */
// newtype State s a = State { runState :: (s -> (a,s)) } 
public class State<S, A> {
    /** 状態を渡すと、値と状態を戻す処理 */
    private final Function<S, StatePair<A, S>> runState;

    public State(Function<S, StatePair<A, S>> runState) {
        this.runState = runState;
    }
    // 状態を渡して、値と状態を取り出す
    public StatePair<A, S> runState(S s) {
        return runState.apply(s);
    }
    // 状態を渡して、状態を取り出す
    public S execState(S s) {
        return runState(s).state;
    }
    // 状態を渡して、値を取り出す
    public A evalState(S s) {
        return runState(s).value;
    }
    // 型省略用のファクトリメソッド
    public static <S, A> State<S, A> state(Function<S, StatePair<A, S>> runState) {
        return new State<S, A>(runState);
    }
    // return a        = State $ \s -> (a,s)
    public static <S, A> State<S, A> unit(final A a) {
        return state(new Function<S, StatePair<A, S>>() {
            public StatePair<A, S> apply(S s) {
                return StatePair.pair(a, s);
            }
        });
    }
    // (State x) >>= f = State $ \s -> let (v,s') = x s in runState (f v) s' 
    public <B> State<S, B> bind(final Function<A, State<S, B>> f) {
        return state(new Function<S, StatePair<B,S>>() {
            public StatePair<B, S> apply(S s) {
                StatePair<A, S> ret = runState(s);
                return f.apply(ret.value).runState(ret.state);
            }
        });
    }
    // get   = State $ \s -> (s,s) 
    public static <S>State<S, S> get() {
        return state(new Function<S, StatePair<S,S>>() {
            public StatePair<S, S> apply(S s) {
                return StatePair.pair(s, s);
            }
        });
    }
    // put s = State $ \_ -> ((),s)
    public static <S> State<S, Void> put(final S s) {
        return state(new Function<S, StatePair<Void, S>>() {
            public StatePair<Void, S> apply(S dummy) {
                return StatePair.pair(null, s);
            }
        });
    }
    /**
     *  Stateから中身を取り出すための、値と状態のペア
     *
     * @param <A> 値の型
     * @param <S> 状態の型
     */
    public static final class StatePair<A, S> {
        public final A value;
        public final S state;

        private StatePair(A a, S s) {
            this.value = a;
            this.state = s;
        }
        /** ペアを生成する */
        private static <A, S> StatePair<A, S> pair(A a, S s) {
            return new StatePair<A, S>(a, s);
        }
        public String toString() {
            return ToStringBuilder.reflectionToString(this);
        }
    }
}

関数は例によってGoogle GuavaのFunctionを借りている。
タプルが無いので、StatePairという値と状態の組をあらわすクラスを用意した。また、空のタプルもないので、Void(値としてはnull)で代用した。

解説

モナドと言うのは、何かを包んで、組み合わせて使用しやすいようにしたコンテナ、と考えればよいと思う。
状態モナドも、やはり何かを包んでいる。名前から想像するに……「状態」を保持？と考えるとハマるので止めましょう。
「状態を受け取って値と状態を返す“処理”」を包んだものと考えるのが分かりやすいと思う。

例えば、(上に挙げたサイトで出てきたサンプルにあるような、) スタックの実装をイメージすると分かりやすい。

push(n)という状態モナド → スタックを状態として与えると、それにnを積んだ状態を戻す「処理」
popという状態モナド → スタックを状態として与えると、値としてスタックのトップを、状態としてスタックの残りを、戻す「処理」

ちょっとReaderモナドに似ているけど、Readerモナドの中身は「環境を与えると値を戻す処理」なのに対して、Stateモナドの中身は「状態を与えると値と状態を戻す処理」という感じで高機能になっている。

使い方の例: スタック

「Stateモナドとモナドトランスフォーマー - yunomuのブログ」にあるスタックの例(モナド変換子じゃない版)を写経してみる。
まずは、スタックを実現するデータ型として連結リストのクラスを定義。

/**
 * 連結リスト
 *
 * @param <A> 値の型
 */
public class List<A> {
    public final A head;
    public final List<A> tail;

    private List(A head, List<A> tail){
        this.head = head;
        this.tail = tail;
    }
    private static List EMPTY = new List(null, null) {
        @Override
        public String toString() {
            return "Nil";
        }
    };
    /** 空のリストを戻す。いわゆるNil。 */
    public static <A> List<A> empty() {
        return (List<A>) EMPTY;
    }
    /** リストが空かどうかを戻す */
    public boolean isEmpty() {
        return this == EMPTY;
    }
    /** リストの先頭に要素を追加したリストを戻す。 */
    public static <A> List<A> cons(A a, List<A> as) {
        return new List<A>(a, as);
    }
    @Override
    public String toString() {
        return "List(" + head.toString() + ", " + tail.toString() + ")";
    }
}

使い方は、empty()か既存のリストにcons()で要素を追加する

// 整数のリスト。配列風に書けば、[2, 1]
List<Integer> list = List.cons(2, List.cons(1, List.<Integer>empty()));
// -> List(2, List(1, Nil))

ではスタックの実装。push/popをstaticメソッドで実装する。

/**
 * 連結リストListで表現されたスタックを状態と見立てて、
 * それを操作するStateモナドを生成するユーティリティ。
 */
public class StackUtils {
    /**
     *  スタックを状態として渡すと、値aをそれに積んだスタックを戻すStateを生成する
     * @param <A> 値の型
     * @param a スタックに積む値
     */
    public static <A> State<List<A>, Void> push(final A a) {
        return State.<List<A>> get().bind(new Function<List<A>, State<List<A>, Void>>() {
            public State<List<A>, Void> apply(List<A> as) {
                return State.put(List.cons(a, as));
            }
        });
    }

    /**
     *  スタックを状態として渡すと、スタックのトップを値に、トップを取り除いた残りを状態として戻すStateを生成する
     * @param <A> 値の型
     */
    public static <A> State<List<A>, A> pop() {
        return State.<List<A>> get().bind(new Function<List<A>, State<List<A>, A>>() {
            public State<List<A>, A> apply(final List<A> as) {
                if (as.isEmpty()) {
                    throw new RuntimeException("stack empty");
                }
                return State.put(as.tail).bind(new Function<Void, State<List<A>, A>>() {
                    public State<List<A>, A> apply(Void dummy) {
                        return State.unit(as.head);
                    }
                });
            }
        });
    }
}

使ってみる。

        /* 空のスタックに、"aaa"を積むサンプル */
        // "aaa"を積むState
        State<List<String>, Void> push_aaa = StackUtils.push("aaa");

        // 空のスタック
        List<String> sampleStack1 = List.empty();

        // 空のスタックに、"aaa"を積んだスタックを取得
        List<String> result1 = push_aaa.execState(sampleStack1);
        System.out.println(result1);    // -> List(aaa, Nil)

        /* スタックから、値を取り出すサンプル */
        // スタックのトップの値を取り除いて取得するState
        State<List<Integer>, Integer> pop1 = StackUtils.pop();
 
        // 1, 2が積まれたスタック(トップは2)
        List<Integer> sampleStack2 = List.cons(2, List.cons(1, List.<Integer>empty()));
        System.out.println(sampleStack2);               // -> List(2, List(1, Nil))

        // 値を一つとり出す
        StatePair<Integer, List<Integer>> result2 = pop1.runState(sampleStack2);
        System.out.println("value = " + result2.value); // -> value = 2
        System.out.println("state = " + result2.state); // -> state = List(1, Nil)

pushとpopを組み合わせて使う例として、「スタックの先頭を複製する処理」を書いてみる。

    /** スタックの先頭を複製するStateを生成する */
    <A> State<List<A>, Void> dup() {
        return
            // popして値を取り出し、
            StackUtils.<A>pop()
            .bind(new Function<A, State<List<A>, Void>>() {
                public State<List<A>, Void> apply(final A value) {

                    return
                        // 取り出した値をpushし、
                        StackUtils.push(value)
                        .bind(new Function<Void, State<List<A>, Void>>() {
                            public State<List<A>, Void> apply(Void dummy) {

                                // さらに同じ値をpushする。
                                return StackUtils.push(value);
                            }
                        });
                }
            });
    }

        /* スタックのトップを複製するサンプル */
        // スタックのトップを複製するState
        State<List<Integer>, Void> dupState = dup();

        // 123が積まれたスタック
        List<Integer> sampleStack3 = List.cons(123, List.<Integer>empty());
        System.out.println(sampleStack3);   // -> List(123, Nil)

        // トップを複製する
        List<Integer> ret3 = dupState.execState(sampleStack3);
        System.out.println(ret3);           // -> List(123, List(123, Nil))

こんな感じで、状態を渡すと値と状態を戻す処理が書け、それらを組み合して使うこともできる。