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 という言語はちょっとの事をやるのにも書かなきゃならないコードが多い。とはいえ最近では、こういう言語でいろいろ工夫するのも、割と面白いんじゃないかとも思える心境になってきていたりする。