Java で higher kinded polymorphism を実現する

#Disclaimer
この記事では一般的な（一般的とは…？）Java プログラマにも理解してもらえるように、比較的理解が簡単なかわりに informal な説明をしています。higher kinded polymorphism に関する formal な情報を求めている人は…ちょっと探した感じでは Qiita にはないようなので、適当にぐぐるか、References を参照してください。

#TL;DR
俺はスーパー Java プログラマだぜって人は記事最下部の References にある highj を参照してください。これ読まなくていいです。Don't Read.

#higher kinded polymorphism とは
higher kinded polymorphism をさす言葉として、他にも type constructor polymorphism とか実に様々な呼称があるのですが、ややこしいので統一してほしい。日本語だと高階型パラメタとかが一般的？なのかな？ようは、こういうのです。

public interface Higher<TypeConstructor> {
  TypeConstructor<Integer> tInteger(); // Error!
}

java.util.List のような「型変数を取る型」を、型変数として扱うということです。型変数を取り、具体的な型（List<Integer> のような）を返すというのは、「型を作る型」ともいえるため、type constructor と呼ばれたりします。これをパラメトリックに扱うので type constructor polymorphism とか type constructor parameter とか言われるわけです。心底統一してほしい。
勿論上のコードはコンパイルできません。これを何とかして実現できないか、というのが今回の記事のゴールです。

#Motivation and Example
できるだけわかりやすい例で。
例えば、型変数を一つ取る、任意のコレクションの「空」の値を返すメソッドを持つ interface を書きたいとします。
より具体的には java.util.Collections の emptyList や emptySet を統一的に扱えるようなメソッドを持つ interface を書きたいとします。

public interface EmptyCollections<Coll> {
  <Elem> Coll<Elem> empty(); // Error!
}

前述の通り、今のところ Java ではこのようなメソッドをそのままでは実現できません。

#型安全でない手法による実現とその問題点
リフレクションを使えば一見実現できるように思えます。

List<Elem> emptyList = (List<Elem>)List.class.newInstance(); // Error!

しかしこれはエラーになります。List は interface ですから instantiation できるはずがありません。

List<Elem> emptyList = (List<Elem>)ArrayList.class.newInstance();

ArrayList は具象クラスですから instantiation できます。引数に具象クラスの Class を貰うことにすれば解決できるように思えますが…

public static <T> List<T> empty(Class<? extends List> concreteListClass) { ... }

これも完全ではありません。引数に abstract class である java.util.AbstractList の Class が渡されても、問題なくコンパイルできてしまいます。Java では型変数に対して、それが具象クラスであることを示すような制約を記述することはできません。

大体リフレクションなんていうのは、基本的には最後の手段です。

#Type Indexed Value

Type Indexed Value と呼ばれる手法が存在します。これは、これ型を表す値を定義しうまく利用することで、型安全性を保ちつつ柔軟な API を提供するための手法です。
「ある型を表す値」の型は、なんのメソッドも提供しない Class クラスのようなものだと思って貰うのがわかりやすいと思います。

public interface Type<T> { }

public static class Types {
   public static Type<Integer> integer = new Type<Integer>() { };
   public static Type<List> list = new Type<List>() { };
}

Integer と List を表す値を作ることができました。
list の型に注目してください。この型は List のような型変数を取る型ではなく、単なる型です。
型変数を取る型を型変数として扱えないなら、それと一対一対応する型を作り、変わりにそれを使えばいい、という発想です。具体的には、List の代わりに Type<List> を型変数に利用します。
ここでは、これ以上 Type Indexed Value についての解説、例えばこの手法を使ってどのようなことが実現できるのか、については説明しません。重要なのは、「型変数を取る型」と一体一対応する型を作ることで、擬似的に「型変数を取る型」を単なる型として型変数に渡すことを表現できる、ということです。
higher kinded polymorphism を実現するために、Type Indexed Value の一部のエッセンスだけを拝借していきます。
そんなわけで、今回の目的に Type interface は不要なので、以下では List を表す型は次のようなクラス ListType として定義することにしましょう。

public class ListType { }

#一休み
ここまで読まれた方の中には「別に ListType なんて使わなくても List を使えばいいじゃないか、現に Type<List> で使っているじゃないか」と思う人もいると思います。そう、「型変数を取る型」を型変数として「表現できない」ことと、「型変数を取る型」を型変数として「渡すこと」は別の話です。実際 Type<List> は valid です。これは Java に原型（Raw Types）の存在があるためです。が、原型なんて今の時代、例えそれが型の上にしか現れなかったとしても、避けたほうがいいでしょう。避けます。ぶっちゃけこれから ListType に static メソッド持たせたいので。

#「型変数を取る型」に型を適用した型
List の代わりに ListType を使うことで、擬似的に「型変数を取る型」を型変数に渡すことができるようになりました。これを使って、最初の例について考え直してみましょう。

public interface EmptyCollections<Coll> {
  <Elem> Coll<Elem> empty();
}

まだ足りませんね。「型変数を取る型」を（擬似的に）型変数に渡すことができるようにはなりましたが、依然として Coll<Elem> というような記述をすることはできません。型変数に渡されたものがなんであれ、型変数は「型変数を取る型」ではなく、単なる型変数でしかないからです。
これは、「型変数を取る型」に「型を適用すること」を型として表現することで回避しましょう。

public class Apply<TypeConstructor, Param> { }

List<Integer> を Apply<List, Integer> として表現します。これも考え方は Type Indexed Value に近いですね。実際は全然別物なんですが。この Apply interface を使って、書き直した物が以下になります。

public interface EmptyCollections<Coll> {
  <Elem> Apply<Coll, Elem> empty();
}

だいぶゴールが見えてきました。

#List に対する実装

ちゃちゃっと実装してしまいましょう。

public class EmptyLists implements EmptyCollections<ListType> {
  public <Elem> Apply<ListType, Elem> empty() {
    return Collections.<Elem>emptyList(); // Error!
  }
}

と思いましたがまだ駄目ですね。型の方は何とか諸々誤魔化すことができましたが、値のほうはまだ手付かずでした。型の上では同一視して扱うと決めていますから、ここは Apply<List, Elem> と List<Elem> の相互変換のためのメソッドを定義してしまいましょう。ちょっと長いです。

Apply.java

public class Apply<TypeConstructor, Param> {
  private final Object applied;
  private Apply(Object applied) {
    this.applied = applied;
  }
  public static <TC, P, Applied> Apply<TC, P> to(Applied applied) {
    return new Apply<>(applied);
  }
  @SuppressWarnings("unchecked")
  public static <TC, P, Applied> Applied from(Apply<TC, P> apply) {
    return (Applied)apply.applied;
  }
}

ListType.java

public class ListType {
  public static <Elem> Apply<ListType, Elem> to(List<Elem> value) {
    return Apply.to(value);
  }
  public static <Elem> List<Elem> from(Apply<ListType, Elem> value) {
    return Apply.from(value);
  }
}

これでようやく実装することができます。お疲れ様でした。

public class EmptyLists implements EmptyCollections<ListType> {
  public <Elem> Apply<ListType, Elem> empty() {
    return ListType.to<Elem>(Collections.emptyList()); // wrap
  }
}

EmptyCollections<ListType> emptyLists = new EmptyLists();
List<Integer> integers = ListType.from(emptyLists.<Integer>empty()); // unwrap

毎回 EmptyLists クラスのインスタンスを生成するのは無駄なので、EmptyLists の static メンバとして持たせておいてもいいですね。

#まとめ
Java で higher kinded polymorphism を実現する手法を紹介しました。
「型変数を取る型」を渡せない（原型なら渡せますが）問題は、「型変数を取る型」を表す型を導入することにより解決しました。
型変数が型変数を取れない問題は「型変数を取る型」に「型を適用すること」を表す型を導入することにより解決しました。
本来の「型変数を取る型」に型を適用した型と、前述の二つの型によりそれを擬似的に再現した型との間で相互変換を行うメソッドを提供することで、必要に応じて本来の型に戻したり、擬似的な型に変換したりすることを可能とすることで、値レベルでも問題なく運用できるようになっています。

今回の手法では、例えば Map のような型変数を二つ取る型に対して、「型変数を二つ取る型」に「二つの型を適用すること」を表す型（名前は Apply2 とかになるでしょうか）の導入が必要になります。冗長ですが、こればかりは仕方ない。Map のような型変数を二つ取る型を「型変数を一つ取り、型変数を一つ取る型を返す型」としてみれば、できなくはないですが、あまりにも記述が煩雑になってしまいます。

#References
Jeremy Yallop and Leo White. Lightweight higher-kinded polymorphism (pdf)
OCaml で Functor（fmap じゃなくて言語機能です）を使わずに higher-kinded polymorphism を実現しよう、という論文です。今回の記事はこの論文の手法をベースにしています。
去年 OCaml に追加された新しい言語機能 Extensible variant types があまりにも使われてなさすぎるので、何処かに使っているコードはないか、と探していたら見つかったもので、かなりひねった面白い使い方をしています。こういうのもあるんだなあと勉強になりました。全然本来の使われ方じゃない…

Aggelos Biboudis, Nick Palladinos, George Fourtounis, and Yannis Smaragdakis. Streams à la carte: Extensible Pipelines with Object Algebras (pdf)
Object Algebras (pdf) を使って Java8 の Stream API よりも柔軟な、拡張性のある Stream を扱うための API を実現しよう、という論文です。API として Stream のような型変数を取る型を抽象的に扱う必要があるため、higher-kinded polymorphism が必要になるのですが、Java で実現する方法が簡単に紹介されています。参考文献として後述の highj が挙げられています。
これを書くために読み直していて気づいたんですが、普通に上の論文も挙げられてますね…

highj (github)
Java で Haskell みたいに Monad とか Functor みたいな Type Classes バリバリ使いたい！というライブラリです。今回紹介した手法と同じ手法を使っている practical な（？）ライブラリです。Java で Type Classes ってどうやるの、と思ってる人はコードを覗いてみるといいかもしれません。
この記事では List と対応する ListType というクラスを外部で定義しましたが、highj ではデータ構造を表すクラスに、必ず ListType の代わりとなるような内部クラス "µ" を定義し、データ構造を表すクラスはその型を Apply（highj では _）に適用したインターフェースを implements することで、この記事でいうところの "to" をアップキャストで暗黙に、"from" をダウンキャストで陽に行う、という作法になっています。
highj の作法はコード量も減りスマートですが、既存のデータ構造を表すクラスに適用できない侵入的（intrusive）な手法です。この記事では、広く知られている java.util.List を例に使いたかったため、Apply クラスが元のデータ構造を保持する実装になっています。この手法は非侵入的（non-intrusive）ですが、boxing のように wrap, unwrap が必要になるというデメリットがあります。

#補足（言い訳タイム）（読まなくてよい）

Type Indexed Value は比較的色んなところで使われている手法なので、具体的な資料がぱっと出てこないのですが…ML 系の言語で typesafe な printf を実現するために使われたりとか、そういう感じのものです。今回の記事では「型の変わりになる値（重要なのは型のほうですが）を定義する」という部分でしか使ってないので、詳しい話も別にいいでしょう。
じゃあなんでわざわざ出してきたんだといわれると、天下り的に ListType が降ってくるというのは説明的に何か嫌なので、比較的近いところからアイデアを借りてきたことにした、という…余計ややこしくしてしまった気もする…

kind という概念があります。String のような型は kind が 1、List のような「型を一つとる型」は kind が 2、Map のような「型を二つ取る型」は kind が 3、みたいな具合です。この kind が 2 以上、つまり List や Map のような型に対しても parametric な polymorphism を実現するのが、higher(1 でない) kinded polymorphism、ということなのですが（本当に呼称統一してほしい）、kind 等の比較的ややこしい概念を知らない、分からない人向けに記事を書こうということで、今回はこうなりました。馬鹿みたいに長くなってしまった。

個人的には Scala 使えばいいと思います。言語にはそれぞれのやり方、Java なら Java way があるし、Scala なら Scala way があるわけです。しかし時には、言語機能は勿論として、主要なライブラリやフレームワークを駆使してもうまくいかないこともあります。そういう時には、道から外れてみてもいいんじゃないでしょうか。higher kinded polymorphism はその一例だと思います。

おしまい。