JavaでモナドでFizzBuzz〜復讐編〜(Re:数値のFizz、Buzz等への変換を、Javaで通常より直感的に表現したい)

以前作った「数値のFizz、Buzz等への変換を、Javaで通常より直感的に表現したい - terazzoの日記」の焼き直しですよ。

事のいきさつ

◆ id:sumim様が、「数値のFizz、Buzz等への変換を、Smalltalk（とRuby）で通常より直感的に表現したい - Smalltalkのtは小文字です」において、FizzBuzzをDSL的に(流れるように自然に)書き下せる方法を発見なさる。

↓

◆ id:terazzo(アタシです)が、↑のエントリのプログラム上での型の動き(Int→Association, Association→Association)を見て、これってモナドじゃね？と思い付く。

↓

◆ 「数値のFizz、Buzz等への変換を、Javaで通常より直感的に表現したい - terazzoの日記」でAsscoiationに対するunit/bindでFizzBuzzをモナド的に書いて満足する。

↓

◆ 「http://d.hatena.ne.jp/terazzo/20110608/1307559510」で代数スタイルのモナド(unit/map/flatten)を知り、特にflattenの型がM(M(a))→M(a)なのを見て、「あれ？ひょっとしてモナドの中にモナドを入れられない限りモナドを名乗ってはダメなのかな？」と疑問がわく。(cf: 「モナドではない - terazzoの日記」)

↓

◆ 「bindの実装は実質的にflattenの内容を含んでおり、flattenは実装されて無いだけでみんなの心の中にある」という理屈を思い付き、それを確認しようとする。 ←いまここ

ということで、FizzBuzzをもう一度実装しなおしつつ、bindとflattenの関係について学んで行きたいと思う(主に自分が。)

↓

◆ (2011/9/15追記)よく見たらWriterモナドだったのでそういう感じで書き直してみた

FizzBuzzを再実装: コメント可能データ型の定義

前回の実装では、コンテナ的な型Associationを用意したまでは良かったが、中に入れるものとしては数値しか考えていなかったので、入れ子にすることが出来なかった。そこで、今回は総称型を使って何でも入れられるようにする。*1

まず、T型のデータに対して、「コメントを付加することができる」入れ物を考える。これをCommentableとして定義する。

package sample.fizzbuzz;

import org.apache.commons.lang.builder.EqualsBuilder;
import org.apache.commons.lang.builder.HashCodeBuilder;
import com.google.common.base.Function;

public final class Commentable<T> {
    /** コメント対象となるデータ */
    private final T data;
    /** コメント */
    private final String comment;

    // コンストラクタはプライベート
    private Commentable(T data, String comment) {
        if (data == null) {
            throw new IllegalArgumentException("data should not be null.");
        }
        this.data = data;
        this.comment = comment;
    }
    // コメントなしデータを生成するファクトリメソッド
    public static <T> Commentable<T> noncommented(T data) {
        return new Commentable<T>(data, null);
    }
    // コメントありデータを生成するファクトリメソッド
    public static <T> Commentable<T> commented(T data, String comment) {
        return new Commentable<T>(data, comment);
    }
/*

例えば、3という数値に対して"Fizz"というコメントを付けたかったら、Commentable.commented(3, "Fizz")のように書くとコメント付きデータが得られる。

最終的に値を取り出す際に、コメントがついてない場合は中身のデータを、コメントがついている場合はコメントが取り出されるようにする。

 */
    // 最終的な値を取り出す
    public Object value() {
        return isCommented() ? comment : data;
    }
    // コメントがついているかどうかを戻す
    public boolean isCommented() {
        return comment != null;
    }
/*

あと、equals(), hashCode(), toString()を適当にオーバーライドする。(Apache Commons Langを使っています。)

 */
    @Override
    public boolean equals(Object other) {
        return EqualsBuilder.reflectionEquals(this, other);
    }
    @Override
    public int hashCode() {
        return HashCodeBuilder.reflectionHashCode(this);
    }
    @Override
    public String toString() {
        return isCommented()
            ? String.format("commented(%s, \"%s\")", data.toString(), comment)
            : String.format("noncommented(%s)", data.toString());
    }
/*

それでは、二つのCommentableを合成できるようにbind()を定義する。Functionは例によってGoogle guavaの奴です。

 */
    public <S> Commentable<S> bind(Function<T, Commentable<S>> f) {
        Commentable<S> that = f.apply(data);

        if (this.isCommented() || that.isCommented()) {
            String merged =
                  (this.isCommented() ? this.comment : "")
                + (that.isCommented() ? that.comment : "");
            return commented(that.data, merged);
        } else {
            // どちらもコメントなしなのでnoncommented()
            return noncommented(that.data);
        }
    }
/*

fにdataを渡してCommentable<S>を取得する。自分自身のコメント(すでにコメントがついていれば)と取得したCommentable<S>のコメントと連結して新たなコメントとし、中身のデータについてはCommentable<S>のものをそのまま使用する。両方にコメントがついていない場合はnoncommented()、どちらかについていればマージしたコメントを使ってcommented()で戻り値を作成する。

TからCommentableを作るunit()も定義する。どこに定義しても良いけど、Commentableクラスのstaticメソッドにする。noncommentedをそのまま呼ぶだけで良いだろう。

 */
    public static <T> Commentable<T> unit(T data) {
        return noncommented(data);
    }
/*

あとunitとbindの関数バージョンも用意する。bindの方はextという名前にしている。

 */
    public static <T> Function<T, Commentable<T>> unit() {
        return new Function<T, Commentable<T>>() {
            public Commentable<T> apply(T data) {
                return unit(data);
            }
        };
    }
    public static <S,T> Commentable<S> bind(
            Commentable<T> c, Function<T, Commentable<S>> f) {
        return c.bind(f);
    }
    public static <S,T> Function<Commentable<T>, Commentable<S>> ext(
            final Function<T, Commentable<S>> f) {
        return new Function<Commentable<T>, Commentable<S>>() {
            public Commentable<S> apply(Commentable<T> c) {
                return c.bind(f);
            }
        };
    }
}

FizzBuzzを再実装: コメンターの実装

流れてきた数値を見て「これはFizzい」とか「これはBuzzい」とかコメントを付ける人を定義する。

package sample.fizzbuzz;

import com.google.common.base.Function;

public final class Commentor implements Function<Integer, Commentable<Integer>> {
    private final int divider;
    private final String comment;
    public Commentor(int divider, String comment) {
        if (divider == 0) {
            throw new IllegalArgumentException("divider should not be zero.");
        }
        this.divider = divider;
        this.comment = comment;
    }
    // dividerで割り切れる時にcommentedなCommentableDataを返す
    // それ以外の時はnoncommentedなCommentableDataを戻す
    public Commentable<Integer> apply(Integer number) {
        return number % divider == 0
            ? Commentable.commented(number, comment)
            : Commentable.noncommented(number);
    }
}

例えば、3の倍数を見たら「これはFizzい」とコメントする人はnew Commentor(3, "これはFizzい")で作成できる。

FizzBuzzを再実装: FizzBuzzの実装

CommentableとCommentorを使ってFizzBuzzを実装する。

package sample.fizzbuzz;

import static org.junit.Assert.assertEquals;
import static sample.fizzbuzz.Commentable.unit;

import org.junit.Test;
import com.google.common.base.Function;

public class FizzBuzzTest {
    // Commentorのfizzとbuzzを作成
    final Function<Integer, Commentable<Integer>> fizz = new Commentor(3, "Fizz");
    final Function<Integer, Commentable<Integer>> buzz = new Commentor(5, "Buzz");
    // メソッドfizzBuzzを定義
    public Object fizzBuzz(Integer n) {
        return unit(n).bind(fizz).bind(buzz).value();  // ←通常より直感的に表現！
    }
    @Test
    public void testFizzBuzz() {
        assertEquals(1, fizzBuzz(1));
        assertEquals(2, fizzBuzz(2));
        assertEquals("Fizz", fizzBuzz(3));
        assertEquals(4, fizzBuzz(4));
        assertEquals("Buzz", fizzBuzz(5));
        assertEquals(7, fizzBuzz(7));
        assertEquals("FizzBuzz", fizzBuzz(15));

        // 表示してみる
        for (int n = 1; n <= 100; n++) {
            System.out.printf("%s\n", fizzBuzz(n));
        }
    }
}

代数スタイルの関数定義とテスト

flattenとmapと実装する。どこに定義しても良いけど、Commentableクラスのstaticメソッドにする。

public final class Commentable<T> {
...
// さっきのコードの後ろに追加

    // flatten = bind(id) = bind(ext(unit))
    public static <T> Commentable<T> flatten(Commentable<Commentable<T>> cc) {
        return bind(cc, ext(Commentable.<T>unit()));
    }
    // map(f, m) = bind(m, ( \x -> unit (f x) ))
    public static <S, T> Commentable<S> map(final Function<T, S> f, Commentable<T> c) {
        return c.bind(new Function<T, Commentable<S>>() {
            public Commentable<S> apply(T x) {
                return unit(f.apply(x));
            }
        });
    }
    // flattenの関数バージョンも用意しておく
    public static <T> Function<Commentable<Commentable<T>>, Commentable<T>>
            flatten() {
        return new Function<Commentable<Commentable<T>>, Commentable<T>>() {
            public Commentable<T> apply(Commentable<Commentable<T>> cc) {
                return flatten(cc);
            }
        };
    }
}

テスト。
等しいということは直接テストできないけど、とりあえず同じ入力に対する出力が一致することを確認する。

package sample.fizzbuzz;

import static org.junit.Assert.assertEquals;
import static sample.fizzbuzz.Commentable.*;

import org.junit.Test;

public class CommentableTest {
    // 代数スタイルのモナド則
    // モナド則(1) flatten(unit(m)) = m
    @Test
    public void testMonad1() {
        Commentable<Integer> c = commented(1, "hoge");

        assertEquals(
            flatten(unit(c)),
            c);
    }

    // モナド則(2) flatten(map(unit, m)) = m
    @Test
    public void testMonad2() {
        Commentable<Integer> c = commented(1, "hoge");

        assertEquals(
            flatten(map(Commentable.<Integer>unit(), c)),
            c);
    }

    // モナド則(3) flatten(flatten(mmm)) = flatten(map(flatten, mmm))
    @Test
    public void testMonad3() {
        Commentable<Commentable<Commentable<Integer>>> ccc = 
            commented(commented(commented(999, "hoge"), "fuga"), "piyo");

        assertEquals(
                flatten(flatten(ccc)),
                flatten(map(Commentable.<Integer>flatten(), ccc)));

        System.out.println("flatten(flatten(ccc)) = " + flatten(flatten(ccc)));
        // 「flatten(flatten(ccc)) = commented(999, "piyofugahoge")」と出力される！
    }
}

ちゃんと定義できた＆テスト通った。

flattenの動きを見る。

flattenは入れ子になったモナドを、入れ子の数を一段下げるような関数である。

        Commentable<Commentable<Integer>> cc = commented(commented(999, "hoge"), "piyo");
        Commentable<Integer> c = flatten(cc);
        System.out.println("nested commentable:\n\t" + cc);
        System.out.println("flattened:\n\t" + c);

出力:

nested commentable:
	commented(commented(999, "hoge"), "piyo")
flattened:
	commented(999, "piyohoge")

特にflattenを意識してコードを書いたわけでなく、bindを使って機械的に作ったのだが、なんとなくネストを下げてそれっぽく繋げたような出力になっている。中ではどういう動きになっているのだろう？

上のとおり、flattenはbindを使って書いている。
ext(unit)はidなので、もっとべたに書くと、

    public static <T> Commentable<T> flatten(Commentable<Commentable<T>> cc) {
        Function<Commentable<T>, Commentable<T>> id =
            new Function<Commentable<T>, Commentable<T>>() {
                public Commentable<T> apply(Commentable<T> c) {
                    return c; // 引数をそのまま戻す
                }
            };
        return bind(cc, id);
    }

一方bindの中身は、fの戻り値のCommentableに注目すると、以下のように書き換えられる。

    public <S> Commentable<S> bind(Function<T, Commentable<S>> f) {
        return mergeContents(this, f.apply(this.data));
    }
    private static <S, T> Commentable<S> mergeContents(Commentable<T> t, Commentable<S> s) {
        if (t.isCommented() || s.isCommented()) {
            String merged =
                  (t.isCommented() ? t.comment : "")
                + (s.isCommented() ? s.comment : "");
            return commented(s.data, merged);
        } else {
            return noncommented(s.data);
        }
    }

flattenに戻って「return bind(cc, id)」の部分のbindを上のbindに置き換えると、、

    public static <T> Commentable<T> flatten(Commentable<Commentable<T>> cc) {
        Function<Commentable<T>, Commentable<T>> id =
            new Function<Commentable<T>, Commentable<T>>() {
                public Commentable<T> apply(Commentable<T> c) {
                    return c; // 引数をそのまま戻す
                }
            };
        return mergeContents(cc, id.apply(cc.data));
    }

id.apply(cc.data)は定義よりcc.dataなので、

    public static <T> Commentable<T> flatten(Commentable<Commentable<T>> cc) {
        return mergeContents(cc, cc.data);
    }

このcc.dataが何かというと、Commentable>の中身であるところのCommentableに他ならない。
ということで、今回実装したbindに基づいて定義したflattenは「自分自身(Commentable>)と、自分の中身(Commentable)をマージして、中身の方の型で戻す」という動きになっていることが分かった。

結論？

やっぱり、「bindの実装は実質的にflattenの内容を含んでおり、flattenは実装されて無いだけでみんなの心の中にある」ってことで良いのではないかなあ……

*1:あと状態をクラスで表したり条件分岐を多態で処理したりとかの凝った事はやめて1クラスで平易に実装した