続・Javaで複合モナド

Java

前回の自分用宿題

・ 拡張スタイルの関数(というかbind)の導出

これをやってみる。あと逆に拡張スタイルから代数スタイルの導出もやる。

  • unit, flatten, mapからのbindの導出
  • unit, bindからのflatten, mapの導出
  • e_unit, e_bind, l_unit, l_bind, combinationsから el_bindの導出

unit, flatten, mapからのbindの導出

bind(m, f) = flatten(map(f, m))であった。※bindは引数の順序を変えてる

public class Enum<T> {
...
    // extension style
    public static <X, Y> Enum<Y> e_bind(Enum<X> e, Function<X, Enum<Y>> f) {
        return e_flatten(e_map(f, e));
     }
    // Function version (= e_ext)
    public static <X, Y> Function<Enum<X>, Enum<Y>> e_bind(final Function<X, Enum<Y>> f) {
        return new Function<Enum<X>, Enum<Y>>() {
            public Enum<Y> apply(Enum<X> e) {
                return e_bind(e, f);
            }
        };
    }
}

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

    // サンプル関数1. 1を加えてEnum<Long>で戻す
    Function<Long, Enum<Long>> sum1 = new Function<Long, Enum<Long>>() {
        public Enum<Long> apply(Long x) {
            return e_unit(Long.valueOf(x.longValue() + 1));
        }
    };
    // サンプル関数2. nの素因数をEnum<Long>で戻す
    Function<Long, Enum<Long>> factors = new Function<Long, Enum<Long>>() {
        public Enum<Long> apply(Long n) {
            if (n < 1) {
                throw new IllegalArgumentException("arg should be positive.");
            }
            if (n == 1) {
                return new Enum<Long>(1L);
            }
            Set<Long> result = new HashSet<Long>();
            long k = n;
            for (long i = 2, r = Math.round(Math.sqrt(k)); i <= r; i ++) {
                while (k % i == 0) {
                    result.add(i);
                    k /= i;
                    r = (int) Math.round(Math.sqrt(k));
                }
            }
            if (k != 1) {
                result.add(k);
            }
            return new Enum<Long>(result);
        }
    };
    
    // 拡張スタイルのモナド則
    // (return x) >>= f ≡ f x
    @Test
    public void testRule1() {
        assertEquals(
            e_bind(e_unit(195955200000000L), factors),
            factors.apply(195955200000000L)
        );
    }
    
    // m >>= return ≡ m
    @Test
    public void testRule2() {
        Enum<Integer> m = new Enum<Integer>(0, 1, -3, 7, 2);
        assertEquals(
            e_bind(m, Enum.<Integer>e_unit()),
            m
        );
    }
    // (m >>= f) >>= g ≡ m >>= ( \x -> (f x >>= g) )
    @Test
    public void testRule3() {
        Enum<Long> m = new Enum<Long>(81L, 82L, 83L, 84L, 85L);
        assertEquals(
            e_bind(e_bind(m, factors), sum1),
            e_bind(m, new Function<Long, Enum<Long>>() {
                public Enum<Long> apply(Long l) {
                    return e_bind(factors.apply(l), sum1);
                }
            })
        );
    }

ちなみに最後のe_bind(e_bind(m, factors), sum1)は81, 82, 83, 84, 85の素因数の和集合のそれぞれに1を足す処理で、結果は{84, 18, 3, 4, 6, 42, 8}とかになります。特に使い途は無い。


l_*やel_*についても同じようにl_bind、el_bindを作れる。

unit, bindからのflatten, mapの導出

今度は逆に、e_unitとe_bindを使ってe_flattenとe_mapを定義してみる。
まずe_map。名前が元のe_mapと被らないようにe_map_by_extにしています。

public class Enum<T> {
...
    // mapをunitとbindで書いてみる
    public static <X, Y> Enum<Y> e_map_by_ext(final Function<X, Y> f, Enum<X> e) {
        return e_bind(e, new Function<X, Enum<Y>>() {
            public Enum<Y> apply(X x) {
                return e_unit(f.apply(x));
            }
        });
    }
*/

bindが取る関数はf:X→Enumなので、f:X→Yにe_unit:Y→Enumを後結合してやればよい。


次にe_flatten。unitとbindでネスト数を減らすのは無理な気もしたけどそうでもなかった。

 */
    // flattenをunitとbindで書いてみる
    public static <X> Enum<X> e_flatten_by_ext(Enum<Enum<X>> ee) {
        return e_bind(ee, e_bind(Enum.<X>e_unit()));
    }
}

e_bind(Enum.e_unit())はid:Enum→Enumです。自分で「new Function, Enum>() {public Enum apply(Enum x) {return x}}」と書いても良い。*1


l_*についても同じようにl_unit, l_bindからl_map, l_flattenを作れる。


e_unit, e_bind, l_unit, l_bind, combinationsから複合モナドの関数の導出

el_unit, el_map, el_flattenがe_unit, e_map, e_flatten, l_unit, l_map, l_flattenとcombinationsから導出できるということは、e_unit, e_bind, l_unit, l_bind, combinationsからも導出できるはず。ということはそれらからel_bindも導出できるはず。


まずel_unitはe_unit(l_unit)なので前回と同じ。

el_map(f, el) := e_map(l_map(f), el)なのでe_mapとl_mapを展開する。

    public static <X, Y> EnumOfList<Y> el_map(Function<X, Y> f, EnumOfList<X> el) {
        return new EnumOfList<Y>(e_map(l_map(f), el));
    }
// ↓↓↓
    public static <X, Y> EnumOfList<Y> el_map_by_ext(final Function<X, Y> f, EnumOfList<X> el) {
        return new EnumOfList<Y>(
                e_bind(el, new Function<List<X>, Enum<List<Y>>>() {
                    public Enum<List<Y>> apply(List<X> x) {
                        return e_unit(l_bind(x, new Function<X, List<Y>>() {
                                public List<Y> apply(X x) {
                                    return l_unit(f.apply(x));
                                }
                            }));
                    }
                })
         );
    }

もうちょっと整理できそうな気もする。


el_flatten(elel) := e_flatten(e_map(e_map(l_flatten), e_map(combinations, elel)))を展開する。

    public static <X> EnumOfList<X> el_flatten(EnumOfList<EnumOfList<X>> elel) {
        return new EnumOfList<X>(
              e_flatten(
                  e_map(
                      e_map(List.<X>l_flatten()), 
                      e_map(Util.<List<X>, EnumOfList<X>>combinations(), elel)
        )));
    }
// ↓↓↓
    public static <X> EnumOfList<X> el_flatten_by_ext(EnumOfList<EnumOfList<X>> elel) {
        return new EnumOfList<X>(
              e_bind(
                  e_bind(elel, new Function<List<EnumOfList<X>>, Enum<Enum<List<List<X>>>>>() {
                      public Enum<Enum<List<List<X>>>> apply(List<EnumOfList<X>> x) {
                          return e_unit(Util.<List<X>, EnumOfList<X>>combinations().apply(x));
                      }
                  }),
                  e_bind(new Function<List<List<X>>, Enum<List<X>>>() {
                      public Enum<List<X>> apply(List<List<X>> x) {
                          return e_unit(l_bind(x, l_bind(List.<X>l_unit())));
                      }
                  }))
                      
        );
    }

e_flatten(e_map)はe_bindなのでそのまま置き換えて、それ以外のところはごりごり変換している。
もうちょっと整理できそうな気もする。


el_bindはel_flatten(el_map)なので、ええと…

    public static <X, Y> EnumOfList<Y> el_bind(EnumOfList<X> el, Function<X, EnumOfList<Y>> f) {
        return el_flatten(el_map(f, el));
    }
// ↓↓↓
    public static <X, Y> EnumOfList<Y> el_bind_by_ext(EnumOfList<X> el, final Function<X, EnumOfList<Y>> f) {
       return new EnumOfList<Y>(
            e_bind(
                e_bind(
                    e_bind(el, new Function<List<X>, Enum<List<EnumOfList<Y>>>>() {
                        public Enum<List<EnumOfList<Y>>> apply(List<X> x) {
                            return e_unit(l_bind(x, new Function<X, List<EnumOfList<Y>>>() {
                                public List<EnumOfList<Y>> apply(X x) {
                                    return l_unit(f.apply(x));
                                }
                            }));
                        }
                    }),
                    new Function<List<EnumOfList<Y>>, Enum<Enum<List<List<Y>>>>>() {
                        public Enum<Enum<List<List<Y>>>> apply(List<EnumOfList<Y>> l) {
                            return e_unit(Util.<List<Y>, EnumOfList<Y>>combinations().apply(l));
                        }
                    }),
                e_bind(new Function<List<List<Y>>, Enum<List<Y>>>() {
                    public Enum<List<Y>> apply(List<List<Y>> x) {
                        return e_unit(l_bind(x, l_bind(List.<Y>l_unit())));
                    }
                })
          ));
    }

型はあってる……
もうちょっと整理できそうな気もするけど、とりあえずunitとbindとcombinationsでも複合モナドが導き出せることが分かった。

*1:検索したら「join = bind id」って結構出てますね