Java 8： Supplier を使った遅延評価で「たらい回し関数」を書いてみる

『ふつうの Haskellプログラミング』って本の５．３章、遅延評価について説明している部分で、「たらい回し関数」が紹介されている。

こんなコード。

main = print (tarai 20 10 5)

tarai :: Int -> Int -> Int -> Int
tarai x y z = if x <= y then y
                        else tarai (tarai (x-1) y z)
                                   (tarai (y-1) z x)
                                   (tarai (z-1) x y)

で実行時間は、Java コードでは約１３秒かかっているのに対し、遅延評価によって必要最小限の計算しかやらない Haskell では 0.002 秒と、6千倍以上速くなっている。

今回は、これを Java 8で試してみたい。


まず、上記 Haskell コードをそっくり置き換えた、オーソドックスなスタイルのタライ回し。

  static int tarai(int x, int y, int z) {
    return x <= y ? y : tarai(tarai(x - 1, y, z),
                              tarai(y - 1, z, x),
                              tarai(z - 1, x, y));
  }

Haskell と違って、不要な計算も全部評価してしまう。うちのマシンでは、だいたい４秒かかった。

以下が遅延評価的な手法を取り入れたバージョン。

  static IntSupplier taraiLazy(int x, int y, int z) {
    return tarai(() -> x, () -> y, () -> z);
  }
  static IntSupplier tarai(
      IntSupplier x, IntSupplier y, IntSupplier z) {
    return () -> { 
      int yv = y.getAsInt();
      return x.getAsInt() <= yv
             ? yv 
             : tarai(tarai(() -> x.getAsInt() - 1, y, z),
                     tarai(() -> y.getAsInt() - 1, z, x),
                     tarai(() -> z.getAsInt() - 1, x, y)).getAsInt();
    };
  }

ここでは Java 8 の IntSupplier を使ってみた。
これは、保持している値がプリミティブの int である、Supplier の特殊な形のクラス。

こんな感じで比較してみた。

  public static void main(final String[] args) {
    measureTimeElapsed(() -> tarai(20, 10, 5));
    measureTimeElapsed(taraiLazy(20, 10, 5));
  }
  public static void measureTimeElapsed(IntSupplier s) {
    long start = System.currentTimeMillis();

    System.out.printf("計算結果:%d, 経過時間:%.3f秒%n",
      s.getAsInt(),
      (System.currentTimeMillis() - start) / 1000.0);
  }

結果は以下

  [java] 計算結果:20, 経過時間:4.389秒
  [java] 計算結果:20, 経過時間:0.004秒

６千倍とまでは行かないが、千倍くらいにはなっている。

まあ言語レベルで遅延評価になったわけでもなく、やろうと思えば Java 7 以前でもできた事ではあるけど、こういう遅延評価っぽいアプローチが少しだけ簡単になったのは、まあ良いことだとは思う。

Java8 の Optionalを Haskellの Maybeモナドっぽく使ってみる

Haskell wiki のこのページに Maybe モナドを使ったサンプルがある。

Java 8 では Maybe にあたる Optional というクラスがあるので、これを用いてモナドっぽくコーディングしてみる。

■ お題の説明

以下のサンプル Haskell コードを実装する。

father :: Person -> Maybe Person
mother :: Person -> Maybe Person

bothGrandfathers p =
    father p >>=
        (\f -> father f >>=
             (\gf -> mother p >>=
                  (\m -> father m >>=
                       (\gm -> return (gf,gm) ))))

father と mother は、架空のデータベースから与えられた人物の父／母を検索し、該当があれば Just でくるんで、なければ Nothing を返す関数。

bothGrandfathers は、与えられた人物の祖父を検索し、両祖父が登録されていたらそれを Just で、なければ Nothing を返す。

Haskell ではさらに do 構文を用いて、簡潔なコードにできるが、Java では無理なので、ここまでをお題としてみたい。

■ サンプルデータの説明

とりあえず、聖徳太子とその尊属を部分的に用いた、下記のようなデータでやってみる。

継体天皇
　　 ├─── 欽明天皇
　　　　 　　　 ├─── 用明天皇
蘇我稲目　　　　│　　　　　 │
　　 │　　┌ 蘇我堅塩媛　　 ├──── 聖徳太子      
　　 ├──┤　　　　　　　　│
　　　　　 └ 蘇我小姉君   　│
　　　　   　　 ├─── 穴穂部間人皇女
   　　　　 (欽明天皇)

この中で両祖父が共に登録されているのは用明天皇と聖徳太子だけなので、彼らの両祖父が Just で取れて、他は Nothing になればいい。

■ 擬似データベース

以下のような擬似データベースを書いてみた。もとの Haskell コードの father / mother は、このクラスの fatherOf(), motherOf() として実装した。

ここでは、せっかくの Java 8 ということで、EDSL への応用をちょっと試してみた。

class ParentChildDatabase {
  static class Relation {
    private final String child;
    private final ParentType type;

    Relation(String child, ParentType type) {...略...}
    public boolean equals(Object obj) {...略...}
    public int hashCode() {...略...}
  }
  private static final Map<Relation, String> database = new HashMap<>();

  private static void put(String child, ParentType type, String parent) {
     database.put(new Relation(child, type), parent);
  }
  static interface Register { As   as(ParentType type); }
  static interface As       { void of(String child); }
  static Register register(String parent) {
    return type -> child -> put(child, type, parent);
  }

  private static Optional<String> get(String child, ParentType type) {
    final Relation key = new Relation(child, type);
    return database.containsKey(key) ? Optional.of(database.get(key))
                                     : Optional.empty();
  }
  static Optional<String> fatherOf(String child) {
    return get(child, ParentType.FATHER);
  }
  static Optional<String> motherOf(String child) {
    return get(child, ParentType.MOTHER);
  }
}

Register と As は関数インターフェイスで、register() と共に用いて、EDSL を形成するためのもの。

等価なコードを仮に Java 8 の標準APIで書くとしたら、

Function<ParentType, Consumer<String>> register(String parent)

みたいなシグネーチャになる。

以下のように使う。

  register("用明天皇").as(FATHER).of("聖徳太子");
  register("穴穂部間人皇女").as(MOTHER).of("聖徳太子");

  register("欽明天皇").as(FATHER).of("用明天皇");
  register("蘇我堅塩媛").as(MOTHER).of("用明天皇");

  register("欽明天皇").as(FATHER).of("穴穂部間人皇女");
  register("蘇我小姉君").as(MOTHER).of("穴穂部間人皇女");

  register("継体天皇").as(FATHER).of("欽明天皇");
  register("蘇我稲目").as(FATHER).of("蘇我堅塩媛");

上記のように、register が 入れ子になった 関数インターフェイス を返すので、一個ずつ適用していく。

ちなみに、この例とはちょっと違うが、同じ要領で応用すれば、名前付きパラメータみたいことも実装できるだろう（順序は固定だけど）。

■ bothGrandfathers の実装

Haskell のモナドの >>=、いわゆる bind は、Java 8 の Optional では flatMap() が、どうやらこれに相当する。

ちなみに Haskell の fmap は、Optional の map() に対応しているように見え、さらに、Stream にも同じようなシグネーチャの対応がみられる。
↓ Haskell の fmap と bind

fmap   :: (a -> b) -> f a -> f b
(>>=)  :: m a -> (a -> m b) -> m b

↓ Java 8 の Optional と Stream の、それぞれの map と flatMap

// Optional の map と flatMap
interface Optional<T>
  Optional<U>  map(Function<T, U> mapper)
  Optional<U>  flatMap(Function< T,Optional<U>> mapper)

// Stream の map と flatMap
interface Stream<T> 
  Stream<R>  map(Function<T, R> mapper)
  Stream<R>  flatMap(Function<T, Stream<R>> mapper)

というわけで、サンプルの Haskell コード の (>>=) 部分を flatMap を用いて以下のように書き換えてみた（もとの Haskell コードでは変数名が省略されていてさすがに分かりにくかったので、ここでは英単語を省略せずに使った）。

  private static Optional<List<String>> bothGrandfathers(String person) {
    return fatherOf(person).flatMap(
             father -> fatherOf(father).flatMap(
               fatherOfFather -> motherOf(person).flatMap(
                 mother -> fatherOf(mother).flatMap(
                   fatherOfMother -> Optional.of(Arrays.asList(
                       new String[] {fatherOfFather, fatherOfMother}))))));
  }

割と Haskell のサンプルコードと似た感じにできたんじゃないかと思う。

で、こんな感じで動かすと,,,

    System.out.println(bothGrandfathers("聖徳太子"));
    System.out.println(bothGrandfathers("用明天皇"));
    System.out.println(bothGrandfathers("欽明天皇"));

こんな出力が得られる

     [java] Optional[[欽明天皇, 欽明天皇]]
     [java] Optional[[継体天皇, 蘇我稲目]]
     [java] Optional.empty

====
聖徳太子って両祖父が同じなんだね。へえ。

Java 8 で アプリカティブファンクターを考えてみる

この Haskell の wikiページの解説を元に、Java 8 でアプリカティブを書いてみる。

■ Maybe の定義
いろんなアプリカティブファンクターがあるけど、とりあえず簡単な Maybeで やってみる。

こんなふうに定義してみた。

abstract class Maybe<A> {
  abstract boolean isNothing();
  public   A       just() { throw new AssertionError(); }

  public static <A> Maybe<A> just(A a) {
    return new Maybe<A>() {
      public boolean isNothing() { return false; }
      public A       just()      { return a; }
      public String  toString()  { return format("Just(%s)", a); }
    };
  }
  private static final Maybe<?> NOTHING = new Maybe() {
      public boolean isNothing() { return true; }
      public String  toString()  { return "Nothing"; }
    };
  public static <A> Maybe<A> nothing() {
    @SuppressWarnings("unchecked")
    Maybe<A> result = (Maybe<A>) NOTHING;
    return result;
  }
}

まあ Java 8 の Optional が、実質 Maybe なんだけど、ここでは後の作業の見通しを良くするためと、Haskellっぽい識別子にするために、あえて定義しなおした。簡単だし。

■ Applicative Maybe の定義
次に Applicative Maybe の定義だけど、前回の投稿で Functor を interface として定義したので、それを extends する形で書いてみたくもなるが、ちょっとやってみたら余りうまく行かなそうな予感がしたので、ここでは ApplicativeFunctor をユーティリティクラスとして定義し、クラスメソッドで pure と <*> を実装することにした。

class MaybeApplicative<A, B> {
  // fmap :: (a -> b) -> f a -> f b
  public static <A, B> Function<Maybe<A>, Maybe<B>> 
　    fmap(Function<A, B> f) {
    return maybe -> maybe.isNothing() ? nothing()
                                      : just(f.apply(maybe.just()));
  }
  // pure :: a -> f a
  public static <T> Maybe<T> pure(T t) { 
    return just(t); 
  }
  // (<*>) :: f (a -> b) -> f a -> f b
  public static <A, B> Function<Maybe<A>, Maybe<B>> 
      amap(Maybe<Function<A, B>> mf) {
    return mf.isNothing()
           ? ma -> nothing()
           : ma -> ma.isNothing()
                   ? nothing()
                   : just(mf.just().apply(ma.just()));
  }
}

• 「ApplicativeFunctor ならば Functor でもある」ので、fmap も定義。
• <*> みたいな、かっちょいい記号が使えないので、amap() ってメソッドにした。

一応、ここまでで動かしてみると、こんな感じ。

  Maybe<String> m1 = just("m1");
  Maybe<String> m2 = nothing();
  Maybe<Function<String, Integer>> mf1 = just(String::length);
  Maybe<Function<String, Integer>> mf2 = nothing();

  println(amap(mf1).apply(m1));// Just(2)
  println(amap(mf1).apply(m2));// Nothing
  println(amap(mf2).apply(m1));// Nothing
  println(amap(mf2).apply(m2));// Nothing

■ アプリカティブ則
以下、４つのアプリカティブ則と、fmap に関連するもう一個のルールを試してみる。というか、これを確かめるコードを Java で書いたらどんな感じになるかやってみる。

 pure id <*> v = v                            -- Identity
 pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- Composition
 pure f <*> pure x = pure (f x)               -- Homomorphism
 u <*> pure y = pure ($ y) <*> u              -- Interchange
 fmap f x = pure f <*> x                      -- Fmap

● Identity

  // pure id <*> v = v
  static void checkIdentity(Maybe<String> v) {
    Function<String, String> id = s -> s;
    Object o1 = amap(pure(id)).apply(v);
    printAssertion(o1, v);
  }

こんな感じになる。

  checkIdentity(just("hello")); // Just(hello) == Just(hello)
  checkIdentity(nothing());     // Nothing == Nothing

ちなみに printAssertion()は以下のようなヘルパ。敢えて標準出力目視確認。

  static void printAssertion(Object o1, Object o2) {
    println(format("%s == %s", o1, o2));
  }
  static void println(Object obj) {
    System.out.println(obj.toString());
  }

● Composition

  // pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
  static void checkComposition(
      Maybe<Function<Integer, String>> u,
      Maybe<Function<String, Integer>> v,
      Maybe<String> w) {

    Function<
        Function<Integer, String>,
        Function<Function<String, Integer>,
                 Function<String, String>>>
      compose = f -> g -> f.compose(g);

    Object o1 = amap(amap(amap(pure(compose)).apply(u)).apply(v)).apply(w);
    Object o2 = amap(u).apply(amap(v).apply(w));
    printAssertion(o1, o2);
  }

Function::compose() をカリー化して、パラメータを一個一個適用しているので大分ややこしくなったが、実際どんな計算になっているか、かえってはっきり分かるようになった。

以下のように動かしてみたが、just と nothing の組み合わせを網羅しきってはいないけど(面倒くさくなってきたので)、大体あってる感じだ。

  checkComposition( // Just(7) == Just(7)
      just(Object::toString), just(String::length), just("1234567"));
  checkComposition( // Nothing == Nothing
      nothing(), just(String::length), just("1234567"));
  checkComposition( // Nothing == Nothing
      just(Object::toString), nothing(), just("1234567"));
  checkComposition( // Nothing == Nothing
      just(Object::toString), just(String::length), nothing());
  checkComposition( // Nothing == Nothing
      nothing(), nothing(), nothing());

● Homomorphism

  // pure f <*> pure x = pure (f x)
  static void checkHomomorphism(Function<String, Integer> f, String x) {
    Object o1 = amap(pure(f)).apply(pure(x));
    Object o2 = pure(f.apply(x));
    printAssertion(o1, o2);
  }

  // Just(6) == Just(6)
  checkHomomorphism(String::length, "123456");

● Interchange

  // u <*> pure y = pure ($ y) <*> u
  static void checkInterchange(
      Maybe<Function<String, Integer>> u, String y) {
    Function<Function<String, Integer>, Integer> $y = f -> f.apply(y);
    Object o1 = amap(u).apply(pure(y));
    Object o2 = amap(pure($y)).apply(u);
    printAssertion(o1, o2);
  }

  // Just(5) == Just(5)
  checkInterchange(just(String::length), "12345");
  // Nothing == Nothing
  checkInterchange(nothing(), "12345");

● Fmap

  // fmap f x = pure f <*> x
  static void checkFmap(Function<String, Integer> f, Maybe<String> x) {
    Object o1 = fmap(f).apply(x);
    Object o2 = amap(pure(f)).apply(x);
    printAssertion(o1, o2);
  }

  // Just(4) == Just(4)
  checkFmap(String::length, just("1234"));
  // Nothing == Nothing
  checkFmap(String::length, nothing());

疲れた・・・

■ リフト関数 liftA2
ついでに Haskell の Control.Applicative にある liftA2 も、amap() を使って実装してみる。

 Prelude Control.Applicative> :t liftA2
 liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c

以下のメソッドを ApplicativeFunctor クラスに追加した。

  public static <A, B> Maybe<B> amap(Maybe<Function<A, B>> mf, Maybe<A> a) {
    return amap(mf).apply(a);
  }
  public static <A, B, C> Function<Maybe<A>, Function<Maybe<B>, Maybe<C>>>
      liftA2(Maybe<Function<A, Function<B, C>>> mf) {
    return a -> b -> amap(amap(mf, a), b);
  }

この liftA2 もカリー化した関数を返すようにしてみた (新しく追加した amap(Maybe, Maybe) は apply() 呼び出しの重複を取り除くため)。

以下のように使える。

  Function<String, Function<Integer, Character>> charAt =
      s -> index -> s.charAt(index);
  // Just(d)
  println(liftA2(pure(charAt)).apply(just("abcde")).apply(just(3)));

関数と２つのパラメータを同時に受け取るシグネーチャでも書けるけど、自明なので省略。

あと、Java 8 には BiFunction ってのもあるので、これを用いた liftA2 も書いてみた。

  public static <A, B, C> BiFunction<Maybe<A>, Maybe<B>, Maybe<C>>
      liftBiFunctionA2(Maybe<BiFunction<A, B, C>> mbf) {
    Maybe<Function<A, Function<B, C>>> mf = mbf.isNothing()
      ? nothing()
      : just( a -> b -> mbf.just().apply(a,b));
    return (a, b) -> liftA2(mf).apply(a).apply(b);
  }

こうなる。

  BiFunction<String, Integer, Character> charAt2 =
      (s, index) -> s.charAt(index);
// Just(a)
  println(liftBiFunctionA2(pure(charAt2)).apply(just("abcde"), just(0)));

====
しかし、Haskell みたいに<*> とか <$> とか使えたら、いかにもアプリカティブ・スタイルって感じでかっちょいいんだけど、Java だときついな。

まあ、あえて無理やりやってみることで、いろいろ腑に落ちたり、体感できたりする事もあるので良しとしよう。

Java 8 で Tree と fmap を書いてみる

Haskell の Functor を紹介しているこのページにある、Tree と fmap のサンプルを Java で書いてみる。

■ まずは Treeから
もともとの Haskellコードが以下。

data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving (Show)

Java で書き直したコードが以下。

abstract class Tree<A> {
  abstract boolean isLeaf();
  public A       leaf()  { throw new AssertionError(); }
  public Tree<A> left()  { throw new AssertionError(); }
  public Tree<A> right() { throw new AssertionError(); }
  public static <A> Tree<A> of(A a) {
    return new Tree<A>() {
      public boolean isLeaf() { return true; }
      public A       leaf()   { return a; }
      public String  toString() { return a.toString(); }
    };
  }
  public static <A> Tree<A> of(Tree<A> left, Tree<A> right) {
    return new Tree<A>() {
      public boolean isLeaf() { return false; }
      public Tree<A> left()   { return left; }
      public Tree<A> right()  { return right; }
      public String  toString() {
        return String.format("(%s, %s)", left, right);
      }
    };
  }
}

うーん、長い。Haskell で1行なのが Javaだとたくさん書かなきゃならないが、まあ簡単っちゃ簡単。てか、引数の final いらなくなったんだね。

試してみるとこうなる。

  Tree<Integer> intTree =
    Tree.of(
      Tree.of(
        Tree.of(1),
        Tree.of(2)),
      Tree.of(3));
  System.out.println(intTree); // ((1, 2) ,3)

■ 次に fmap
ようするに (a -> b) -> f a -> f b という型のメソッドを Java で表現できればよくて、素朴でシンプルな実装は、f a を自オブジェクト this とし、（a -> b）を引数で取る形でこうなる。

abstract class Tree<A> {
  ...
  public <B> Tree<B> fmap(Function<A, B> f) {
    return isLeaf() ? Tree.of(f.apply(leaf()))
                    : Tree.of(left().fmap(f), right().fmap(f));
  }
  ...

上で使った intTree に適当な関数を適用してみると、一応期待通り動く。

  System.out.println(
      intTree.fmap(n -> "S" + n.toString())); // ((S1, S2) ,S3)

■ あと Functor
ところで fmap は Haskell では Functor として定義されていて、こんな感じになってる。

class  Functor f  where
    fmap        :: (a -> b) -> f a -> f b

で、Tree の fmap はこんな感じ。

instance  Functor Tree  where
    fmap f (Leaf x) = Leaf (f x)
    fmap f (Branch left right) = Branch (fmap f left) (fmap f right)

これも一応 Java で書いてみよう（以下、ファンクター則とかとりあえず置いとく）。

まず Functor。

interface Functor<A, B, FA, FB> {
  Function<FA, FB> fmap(Function<A, B> f);
}

ここでは (a -> b) -> f a -> f b を (a -> b) -> (f a -> f b) と解釈して（Haskellでは普通だけど）、関数を返すようなシグネーチャにした。

ちなみに Java だと以下のように書けないので嫌な感じだが、まあしょうがない。

interface Functor<A, B, F> {// こうは書けない
  Function<F<A>, F<B>> fmap(Function<A, B> f);
}

次に Tree の Functor。

class TreeFunctor<A, B> implements Functor<A, B, Tree<A>, Tree<B>> {
  static <A, B> Tree<B> fmap(Function<A, B> f, Tree<A> a) {
    return a.isLeaf() ? Tree.of(f.apply(a.leaf()))
                      : Tree.of(fmap(f, a.left()), fmap(f, a.right()));
  }
  public Function<Tree<A>, Tree<B>> fmap(Function<A, B> f) {
    return a -> fmap(f, a);
  }
}

fmap(Function) が本体というか、Functor インターフェイスの実装で、fmap(Function, Tree) はヘルパ用の再帰関数。

Tree に fmap を書いたやつよりも大分コードが増えたけど、Tree の責務として fmap を持つのが妥当かというとかなり疑問なので、別にしておくのが正しい気がする。

この時点では fmap を Tree から切り離して Functor に切り出したことで複雑度が増しているけど、たいていの場合、開発が進むに連れて結局は逆転して、小さくてたくさんのクラスを書くアプローチの方が楽になってくる。

動かすとこんな感じになる。

TreeFunctor<Integer, String> tf = new TreeFunctor<Integer, String>();
    
// ((S1, S2), S3)
println(tf.fmap(f).apply(intTree));

// 部分適用
Function<Tree<Integer>, Tree<String>> f2 =
      tf.fmap(n -> "No." + n.toString());

// (No.1000)
println(f2.apply(Tree.of(1000)));
// (No.5, No.6)
println(f2.apply(Tree.of(Tree.of(5), Tree.of(6))));

直接 new TreeFunctor() でインスタンスを作らずに、どっか他の所にファクトリメソッドを作ったりすると、レガシーコード改善ガイドでいうSeamができてテスタビリティが上がったりするが、ここでは省略した。

====
しかし、SE 8 で若干マシになったものの、Java という言語はちょっとの事をやるのにも書かなきゃならないコードが多い。とはいえ最近では、こういう言語でいろいろ工夫するのも、割と面白いんじゃないかとも思える心境になってきていたりする。

Java8 で Monoid を 書いてみた

春といえば Monoid。

前回までで、Java8 で関数の部分適用とカリー化を書いた。
今度は Monoidでも書いてみるか。春だからな。

import java.util.stream.Stream;
import java.util.function.BinaryOperator;

interface Monoid<A> {
  A empty();
  BinaryOperator<A> append();
  default A concat(Stream<A> s) {
    return s.reduce(empty(), append());
  }

  default A append(A p1, A p2) {
    return append().apply(p1, p2);
  }
  static <A> Monoid<A> of(A empty, BinaryOperator<A> append) {
    return new Monoid<A>() {
      public A empty() { return empty; }
      public BinaryOperator<A> append() { return append; }
    };
  }
}

• empty（） は 単位元。Haskell の mempty。
• append（） は 二項演算で、Haskell の mappend。
• append（A, A）は、いちいち apply()を呼ばなくてもすむようにしただけ。
• concat() は Haskell の mconcat で、受け取る型は配列でもコレクションでもよかったけど、ここでは Stream にしてみた。
• of() はファクトリメソッド。

まずは単純に文字列の結合で試してみる。モノイドはこんな感じ。

  private static final Monoid<String> stringMonoid =
      Monoid.of("", (s1, s2) -> s1 + s2);

で、こうなる。

    Stream<String> s = Stream.of("ab", null, "cd");
    System.out.println(stringMonoid.concat(s));// "abnullcd"

次に、Haskellの Ordering を試してみよう。

元ネタは Learn You a Haskell の Monoid の 『The Ordering monoid』のとこ。
とりあえず Ordering はこんな感じの列挙子にしてみた。

enum Ordering {
  LT, EQ, GT; 
  public static Ordering fromInt(int n) {
    return n < 0 ? Ordering.LT :
           n > 0 ? Ordering.GT : Ordering.EQ;
  }
}

で、Monoid はこう書いてみた。

  private static final Monoid<Ordering> orderingMonoid =
    Monoid.of(EQ, (a, b) -> EQ.equals(a) ? b :
                            LT.equals(a) ? LT: GT);

この Monoidを使うコードが、元ネタにも載ってるこんなメソッド。

  private static Ordering lengthCompare(String s1, String s2) {
    return orderingMonoid.append(
      compareByLength(s1, s2), compareAlphabetically(s1, s2));  
  }

まあ、どうでもいいけど compareByLength() と compareAlphabetically() は一応こんな感じ。（簡単のため、null チェックとか省略）

  private static Ordering compareByLength(String s1, String s2) {
    return fromInt(s1.length() - s2.length());
  }
  private static Ordering compareAlphabetically(String s1, String s2) {
    return fromInt(s1.compareTo(s2));   
  }

実行すると期待通りに動く

    System.out.println(lengthCompare("zen", "ants")); // LT
    System.out.println(lengthCompare("zen", "ant")); // GT
    System.out.println(lengthCompare("zen", "zen")); // EQ

実際に使うとしたら、Monoids クラスみたいなやつに、主だったモノイドオブジェクトを置いておく事になるかもしれない。

Java8でカリー化を書いてみた

部分適用を実装した前の投稿に続いて、Java8でカリー化を書いてみた。 前回書いた F2とF3に、2引数の関数の入れ子を返す curry() を追加した。こんな感じ。

package c2;
import java.util.function.Function;
import java.util.function.BiFunction;

interface F1<T, R> extends Function<T, R> {
}
interface F2<T, U, R> extends BiFunction<T, U, R> {
  default F1<U, R> apply(T p1) {
    return p2 -> apply(p1, p2);
  }
  default F1<T, F1<U, R>> curry() {
    return p1 -> p2 -> apply(p1, p2);
  }
}
interface F3<T, U, V, R> {
  R apply(T t, U u, V v);
  default F2<U, V, R> apply(T p1) {
    return (p2, p3) -> apply(p1, p2, p3);
  }
  default F1<T, F1<U, F1<V, R>>> curry() {
    return p1 -> p2 -> p3 -> apply(p1, p2, p3);
  }
}
public final class CurryTest {
  public static void main(final String[] args) {
    F3<Integer, String, Integer, Integer> f = 
      (n, s, i) -> String.format("%d%s", n, s).length() + i;
    F1<Integer, F1<String, F1<Integer, Integer>>> f3 = f.curry();

    F1<String, F1<Integer, Integer>> f2 = f3.apply(77);
    F1<Integer, Integer> f1 = f2.apply("ab");
    Integer rf = f1.apply(1230);

    System.out.println(rf);// 1234
    System.out.println(f.curry().apply(77).apply("ab").apply(1231));// 1235

    F2<String, Integer, Integer> g = f.apply(77);
    F1<String, F1<Integer, Integer>> g2 = g.curry();

    F1<Integer, Integer> g1 = g2.apply("ab");
    Integer rg = g1.apply(1232);

    System.out.println(rg);// 1236
    System.out.println(g.curry().apply("ab").apply(1233));// 1237
  }
}

特に難しいことはない。

前の投稿で、F1からF3まで実装して、F4以上も同じ要領と書いたが、いっそ F2 以上は全部カリー化された関数で表現するって手もある。もちろんトレードオフはいろいろあるだろうけど。

Java8 で関数の部分適用を書いてみた

取り急ぎ Java8で、引数3つまでの部分適用メソッドを持つ関数クラスを書いてみる。

こんな感じになった。

import java.util.function.Function;
import java.util.function.BiFunction;

interface F1<T, R> extends Function<T, R> {
}
interface F2<T, U, R> extends BiFunction<T, U, R> {
  default F1<U, R> apply(T p1) {
    return p2 -> apply(p1, p2);
  }
}
interface F3<T, U, V, R> {
  R apply(T t, U u, V v);
  default F2<U, V, R> apply(T p1) {
    return (p2, p3) -> apply(p1, p2, p3);
  }
}
public final class PartialTest {

  public static void main(final String[] args) {
    F3<Integer, String, Integer, Integer> f3 =
      (n, s, i) -> String.format("%d%s", n, s).length() + i;
    System.out.println(f3.apply(100, "test", 1)); // 8

    F2<String, Integer, Integer> f2 = f3.apply(1000);
    System.out.println(f2.apply("test", 2)); // 10

    F1<Integer, Integer> f1 = f2.apply("abcde");
    System.out.println(f1.apply(3)); // 12

    System.out.println(
      f3.apply(777).apply("ab").apply(12340));// 12345
  }
}

• Java8 標準の関数インターフェイスとぜんぜん別系統にしても良かったが、ここでは extends させた。例えば、すでに Function/BiFunctionを使っているアプリケーションに追加するような場合、こうした方が既存コードとの相性が良いと思う。
• F1、F2、F3 って型名は、「単語は省略すべきじゃない」って原則に反するけど、意味は自明だしこだわらないことにした。そもそも、このレベルの抽象度の高さだとほとんど具体性とか問われないと思うし。FunctionalJava もこんな感じだった。
• apply() も、もっと抽象的で記号っぽいメソッド名でもよかったけど、ここは Function の既存メソッドに合わせた。
• F1 は Functionと同じだけど、F2、F3と合わせるために敢えて extends した。Function<T, R> が持っている R apply(T) をそのまま用いる。
• F2 は BiFunction を extends した。ただし、BiFunction<T, U, R> には、R apply(T, U) があるが、部分適用がないので default メソッドとして定義した。
• F3 は 適当な基底インターフェイスが無いので、全引数を与えて最終的な値を得るメソッドと、第一引数だけ部分適用するメソッドを持つクラスを作った。

これに似たコードを Java 6とかで書いてみた事があるけど、やはり Java8だとだいぶスッキリする。

同じ要領で F4以上でも書ける（「パラメータが多すぎる関数っていかがなものか」ってのは別にすれば）。

古い FunctionalJava のラムダサンプルを Java 8で書き換えてみた (3)

今度は FunctionalJava のサンプルの Option_bind ってやつを書きなおしてみた。

これは Haskell の Maybe みたいなやつで、Java 8 では Optional がこれに相当する。

もとのコードはこんな感じ。

import fj.data.Option;
import static fj.data.Option.none;
import static fj.data.Option.some;
import static fj.Show.intShow;
import static fj.Show.optionShow;

public final class Option_bind {
  public static void main(final String[] args) {
    final Option<Integer> o1 = some(7);
    final Option<Integer> o2 = some(8);
    final Option<Integer> o3 = none();
    final Option<Integer> p1 = o1.bind({int i => i % 2 == 0 ? some(i * 3) : Option.<Integer>none()});
    final Option<Integer> p2 = o2.bind({int i => i % 2 == 0 ? some(i * 3) : Option.<Integer>none()});
    final Option<Integer> p3 = o3.bind({int i => i % 2 == 0 ? some(i * 3) : Option.<Integer>none()});
    optionShow(intShow).println(p1); // None
    optionShow(intShow).println(p2); // Some(24)
    optionShow(intShow).println(p3); // None
  }
}

書きなおしたものが以下。

import static java.util.Optional.empty;
import java.util.Optional;

public final class Option_bind {
  private static interface Show<T> {
    String show(T t);
    default void print(T t) { System.out.print(show(t)); }
    default void println(T t) { System.out.printf(show(t) + "%n"); }
  }
  private static Show<Integer> intShow = i -> String.valueOf(i);
  private static <T> Show<Optional<T>> optionShow(Show<T> s) {
    return o -> o.isPresent() ? "Optional:" + s.show(o.get()) : "None";
  }
  public static void main(final String[] args) {
    final Optional<Integer> o1 = Optional.of(7);
    final Optional<Integer> o2 = Optional.of(8);
    final Optional<Integer> o3 = Optional.empty();

    final Optional<Integer> p1 = o1.flatMap(i -> i % 2 == 0 ? Optional.of(i * 3) : empty());
    final Optional<Integer> p2 = o2.flatMap(i -> i % 2 == 0 ? Optional.of(i * 3) : empty());
    final Optional<Integer> p3 = o3.flatMap(i -> i % 2 == 0 ? Optional.of(i * 3) : empty());

    optionShow(intShow).println(p1); // None
    optionShow(intShow).println(p2); // Optional:24
    optionShow(intShow).println(p3); // None
  }
}

やや長くなったが、これは Show 周りの必要最小限のコードを自前で書いてみたため。
たぶんFunctionalJava も似たような感じでやってるんだろうけど（ソース読んでないが）、こういうクロージャっぽいコードは、ラムダがあっても無くてもわりと好みだったりする。 細かいが、 of（）は static インポートしてないけど、empty() はしていたりするところにこだわってしまう。

Option サンプルは他に、filter と map があるが、要領は同じなので試行は省略することにした。

あと更に、FunctionalJava で試みられていて Java8でも試してみたい課題があるとしたら、サンプルには無いが関数の合成、カリー化・部分適用、モノイド、ジッパーあたりかな。

古い FunctionalJava のラムダサンプルを Java 8で書き換えてみた (2)

前の投稿に続いて、Java SE 8 のお試しとして FunctionalJavaのサンプルをいじってみる。

今回はフィルタ。

import fj.data.Array;
import static fj.data.Array.array;
import static fj.Show.arrayShow;
import static fj.Show.intShow;

public final class Array_filter {
  public static void main(final String[] args) {
    final Array<Integer> a = array(97, 44, 67, 3, 22, 90, 1, 77, 98, 1078, 6, 64, 6, 79, 42);
    final Array<Integer> b = a.filter({int i => i % 2 == 0});
    arrayShow(intShow).println(b); // {44,22,90,98,1078,6,64,6,42}
  }
}

書きなおしたやつがこれ。

import java.util.stream.IntStream;
import static fj.data.Array.iterableArray;
import static fj.Show.arrayShow;
import static fj.Show.intShow;

public final class Array_filter {
  public static void main(final String[] args) {
    final IntStream a = IntStream.of(97, 44, 67, 3, 22, 90, 1, 77, 98, 1078, 6, 64, 6, 79, 42);
    final IntStream b = a.filter(i -> i % 2 == 0);
    arrayShow(intShow).println(iterableArray(()->b.iterator())); // {44,22,90,98,1078,6,64,6,42}
  }
}

あまり変わらないが、Arrayが IntStreamになった他に、当然ながら Show.println()への渡し方も変わってくる。

この Show は Haskell の Show にインスパイアされたのか、文字列化したり、このサンプルみたいに標準出力に書き出したりするクラス。で、arrayShow() から返される Show オブジェクトの println() メソッドは Array を期待しているので、それに渡すために IntStream b から Array を生成したいんだけど、上記のように書ける。

ポイントは Array を生成するための iterableArray() が入力として Iterable を期待している一方で、IntStream には Iterator を返すメソッドはあっても Iterable を返すメソッドはないという点で、どうするのかしばし迷ったが、よく考えると何のことはなくラムダ式で即決できる問題だった。 以下のように書いたのと同じことになる。

Iterable<Integer> iterable = ()-> b.iterator();
arrayShow(intShow).println(iterableArray(iterable)); // {44,22,90,98,1078,6,64,6,42}

ついでにもう1題やってみる。畳み込み。(オリジナルはここ)

  public static void main(final String[] args) {
    final IntStream a = IntStream.of(97, 44, 67, 3, 22, 90, 1, 77, 98, 1078, 6, 64, 6, 79, 42);
    final int b = a.reduce(0, (i, j) -> i + j);
    System.out.println(b); // 1774
  }

実は、IntStream は加算の単位元と二項演算が決まっているので、以下のようにも書ける。

  public static void main(final String[] args) {
    final IntStream a = IntStream.of(97, 44, 67, 3, 22, 90, 1, 77, 98, 1078, 6, 64, 6, 79, 42);
    System.out.println(a.sum()); // 1774
  }

単位元と二項演算が決まっているってことはモノイドが決まっているってことだけど、Monoid クラス自体は、FunctionalJavaにはあるが、Java8にはない。このあたり、FunctionalJava 的なアプローチを Java8 で実装する場合、上記の Show クラスに加えて自前でトライする価値があるかもしれない。

ちなみに以下のように書くと、ストリームが閉じていると言って実行時に怒られる。当然ながらコレクションとストリームでは全然別物ということになる。

  public static void main(final String[] args) {
    final IntStream a = IntStream.of(97, 44, 67, 3, 22, 90, 1, 77, 98, 1078, 6, 64, 6, 79, 42);
    final int b = a.reduce(0, (i, j) -> i + j);
    System.out.println(b); // 1774
    System.out.println(a.sum());
  }

古い FunctionalJava のラムダサンプルを Java 8で書き換えてみた

Javaプログラマなら知ってる FunctionalJavaっていう関数型プログラミングのライブラリが、けっこう昔からある。

このサンプルページに、それが書かれた当時、近々サポートされるであろうと想定されていた Java 7 closures を用いて書かれたものがある。

ただし、そのサンプルコード自体だいぶ古くて、今となっては文法も違っていたりするので、先日実際にリリースされた JDK8ではコンパイルできない。

というわけで、Java 8 を使ってちょっと書きなおしてみる。

まずオリジナルはこれ。

import fj.data.Array;
import static fj.data.Array.array;
import static fj.data.List.fromString;
import static java.lang.Character.isLowerCase;

public final class Array_exists {
  public static void main(final String[] args) {
    final Array<String> a = array("Hello", "There", "what", "DAY", "iS", "iT");
    final boolean b = a.exists({String s => fromString(s).forall({char c => isLowerCase(c)})});
    System.out.println(b); // true ("what" provides the only example; try removing it)
  }
}

で、書きなおしたやつがこれ。

import static java.lang.Character.isLowerCase;
import java.util.stream.Stream;

public final class Array_exists {
  public static void main(final String[] args) {
    final Stream<String> a = Stream.of("Hello", "There", "what", "DAY", "iS", "iT");
    final boolean b = a.anyMatch(s -> s.chars().allMatch(n -> isLowerCase((char)n)));
    System.out.println(b); // true ("what" provides the only example; try removing it)
  }
}

ラムダ式の部分だけじゃなく、fj.data パッケージ以下の Array や List も、Java8 標準APIで置き換えた（というか、そうせざるを得なかった）。

なんか chars() が IntStream を返してくるのがちょっと嫌な感じだけど、ここで議論されている。

（あと Java 8と直接関係あるわけではないが、当然ながら Stream.of() は static インポートすべきじゃないだろう。Stream of A, B and C という名詞句にするために敢えて前置詞を用いているはずなので。）

ちなみに Java7 以前のバージョンはこれ。

import fj.F;
import fj.data.Array;
import static fj.data.Array.array;
import static fj.data.List.fromString;
import static fj.function.Characters.isLowerCase;

public final class Array_exists {
  public static void main(final String[] args) {
    final Array<String> a = array("Hello", "There", "what", "DAY", "iS", "iT");
    final boolean b = a.exists(new F<String, Boolean>() {
      public Boolean f(final String s) {
        return fromString(s).forall(isLowerCase);
      }
    });
    System.out.println(b); // true ("what" provides the only example; try removing it)
  }
}

少なくともこのサンプルに限って言えば、だいぶマシになった感じだ。

Specification Pattern を Java8のラムダで書いてみる

そろそろ Java SE 8 の GAリリースなので、ちょっと書いてみる。

お題は、DDD でよく使われる Specification Pattern にしてみよう。Wikipediaのこのエントリに、C#で書かれたコードが載ってるので、ざっと書き換えてみよう。

interface Specification<t> {
  boolean isSatisfiedBy(T t);

  default Specification<t> and(Specification<t> other) { 
    assert other != null;
    return t -> this.isSatisfiedBy(t) && other.isSatisfiedBy(t);
  } 
  default Specification<t> or(Specification<t> other) { 
    assert other != null;
    return t -> this.isSatisfiedBy(t) || other.isSatisfiedBy(t);
  } 
  default Specification<t> not() { 
    return t -> !isSatisfiedBy(t);
  } 
}

だいたいこんな感じになる。元のコードよりだいぶ簡単になった。

試しに動かしてみるコードが以下。

public class Test {
  public static void main(String[] args) {
    Specification<String> shortString = s -> s.length() < 3;
    Specification<String> startsWithA = s -> s.length() > 0 && s.charAt(0) == 'a';

    System.out.println(shortString.not().isSatisfiedBy("bcdefg"));// true
    System.out.println(shortString.and(startsWithA).isSatisfiedBy("bc"));// false
    System.out.println(shortString.or(startsWithA).isSatisfiedBy("bc"));// true
  }
}

実は、この Specificationと同じような Predicate というインターフェイスが、すでに java.util.function パッケージ配下にあったりする。

ただ、単なる predicate(述語) というよりもっと具体的に specification(仕様)という意味で使う文脈だと、やはり test() より isSpecifiedBy() の方が良いし（Evans と Fowler の元の記事でもそうなってる）、negate() より not() の方がいいように思う。