型クラスパターン
型クラスパターンとは
型クラスパターンは、KotlinやJavaのようなインターフェースを使う言語において、Scala, Rust, Haskellなどで使われる型クラスの利点を得る手法です。
これから紹介する型クラスパターンは、単にインターフェースを使う場合に比べて、次のような利点があります。
- 特定のstatic関数を持つことを抽象化できる
- ファクトリーメソッドや型変換など
- 既存の型に対しても抽象化を適用できる
- プリミティブな型やライブラリによって提供される型など
型クラスパターンは、1. 型クラスの定義 2. 型クラスのインスタンスの定義 という二段階に分けられます。ここではMonoidを例に、型クラスの実装例を紹介します。
Monoidとは、単位元と結合的な二項演算を備えた代数的な構造です。プログラミングではしばしば畳み込みの文脈で使われるため、普段の開発でも有用な型クラスのうちの一つです。（参考: fold, Stream.reduce）
- 結合的な二項演算とは、
(a * b) * c = a * (b * c)が成り立つような二項演算*をいいます - 単位元とは、ある二項演算
*を考えたときにa * e = e * a = aが成り立つような元eをいいます
型クラスの定義
まずは型クラスを定義します。型クラスはインターフェースで書きますが、通常のインターフェースと区別するために、型クラスの先頭にはType classを表すTCの接頭辞をつけています。
Monoidは単位元と結合的な二項演算を備えているため、それぞれをインターフェースのメソッドとして実装します。
interface TCMonoid<M> {
val empty: M
fun compose(a: M, b: M): M
}
Java
interface TCMonoid<M> {
M empty();
M compose(M a, M b);
}
型クラスのインスタンス宣言
次に、型クラスのインスタンスを定義します。型クラスのインスタンスはクラスで書きます。型クラスのインスタンスは、ある型がその型クラスが課す条件を満たすことを表現します。
Monoidの課す条件は、1. 結合的な二項演算を持つこと 2. 単位元を持つこと の2点でした。
例として文字列を考えてみましょう。文字列は、1. 文字列の結合が結合的である ((s + t) + u = s + (t + u)) 2. 空文字は文字列の結合操作の単位元である (s + "" = "" + s = s) 点から、Monoidのインスタンスになることが分かります。
object MonoidString : Monoid<String> {
override val empty: String = ""
override fun compose(a: String, b: String) = a + b
}
Java
class MonoidString implements TCMonoid<String> {
@Override
public String empty() {
return "";
}
@Override
public String compose(String a, String b) {
return a + b;
}
}
型クラスの利用
型クラスとそのインスタンスが揃ったので、型クラスを利用した多相的な関数を書いてみましょう。以下はMonoidを使ったfoldの実装です。
fun <M> fold(instance: TCMonoid<M>, iter: Iterable<M>): M {
return iter.fold(instance.empty, instance::compose)
}
Java
Javaでは関数を何らかメソッドにしなければならないため、ここでは型クラスTCMonoidのデフォルトメソッドとして実装することを想定しています。
default M fold(Iterable<M> iter) {
M result = empty();
for (var e : iter) {
result = compose(result, e);
}
return result;
}
この多相的な関数は、次のように型クラスのインスタンスを用いて呼び出します。
fold(MonoidString, listOf("Hello ", "Beautiful ", "World")
Java
new MonoidString()
.fold(List.of("Hello ", "Beautiful ", "World"));
Monoidの他の例
Monoidの例には文字列の結合以外にも様々なものがあります。
もし時間があれば、自分で何かしらのMonoidのインスタンスを実装してみてください。そのうえでfoldを呼び出してみて、結果がどのようなものになるか確認してみましょう。
参考までに、以下はMonoidの例です：
- 足し算, 0
- 掛け算, 1
- 論理AND, true
- 論理OR, false
- ビットAND, ~0
- ビットOR, 0
-
Math.max, 最小値 -
Math.min, 最大値 -
Function<T, T>.andThen,Function.identity -
Predicate<T>.and,() -> true
発展：型クラスの継承
型クラスを継承することで、ある型クラスが別のある型クラスを前提条件として持つことを表現できます。
例えば結合的な二項演算を持つ構造である半群を考えると、Monoidは明らかに半群でもあることが分かります。
interface TCSemigroup<G> {
fun compose(a: G, b: G): G
}
interface TCMonoid<M> : TCSemigroup<M> {
val empty: M
}
このように型クラスをより細かい単位に分割すると、ジェネリックな関数に対してより正確な条件を課すことができるようになります。
発展：条件付きの型クラス
JavaのOptional型のように、ジェネリックなクラスであって、型パラメータTがMonoidを満たす場合にのみOptional<T>もMonoidを満たすような構造を考えることができます。
このような構造のインスタンス宣言は、前提条件（この場合は型パラメータTがMonoidであること）をコンストラクタで受け取ることによって実現できます。
class MonoidOptional<T>(
private val instance: TCMonoid<T>
) : TCMonoid<T?> {
override val empty: T? = null
override fun compose(a: T?, b: T?): T? {
if (a == null) {
return b
}
if (b == null) {
return a
}
return instance.compose(a, b)
}
}
Java
class MonoidOptional<T> implements TCMonoid<Optional<T>> {
private final TCMonoid<T> instance;
public MonoidOptional(TCMonoid<T> instance) {
this.instance = instance;
}
@Override
public Optional<T> empty() {
return Optional.empty();
}
@Override
public Optional<T> compose(
Optional<T> a,
Optional<T> b
) {
return a.map(a2 ->
b.map(b2 ->
instance.compose(a2, b2)
).orElse(a2)
).or(() -> b);
}
}
応用：Universal mapping property
型クラスを応用して、実装に対して一意性を与える性質(Universal mapping property, UMP)を、型クラスによって与えることができます。この型クラスのインスタンスは、純粋な関数を書く限りにおいて、どのような実装を書いてもプログラムの意味が同じことが保障される性質を持ちます。
Pair型クラス
ここでは例として、2つ組を表す型クラスを作成してみたいと思います。
JavaではPairというクラスは用意されていません。しかしながらPairに相当するクラスは様々に実装されています。
そこでこれらを統一的に扱えるPairインターフェースを作成することを考えます。このインターフェースを実装していれば、それはPairに相当するクラスであるということです。
interface Pair<T, U> {
val first: T
val second: U
}
Java
interface Pair<T, U> {
T first();
U second();
}
実際これはうまく動作するように見えます。2つ組であればどのようなクラスであってもPairを実装できます。
data class Tuple2<T, U>(
override val first: T,
override val second: U,
) : Pair<T, U>
data class Size<T>(
val width: T,
val height: T,
) : Pair<T, T> {
override val first: T
get() = width
override val second: T
get() = height
}
Java
record Tuple2<T, U>(
T first,
U second
) implements Pair<T, U> {
}
record Size<T>(
T width,
T height
) implements Pair<T, T> {
@Override
public T first() {
return this.width;
}
@Override
public T second() {
return this.height;
}
}
しかしながら、ここで問題が発生します。
Pairインターフェースは、実際のところ、2つ組ではなくても実装することができてしまいます。例えば3つ組でも実装できることは想像に難くありません。Pairインターフェースは条件が緩すぎるのです。
data class Tuple3<A, B, C>(
override val first: A,
override val second: B,
val third: C,
) : Pair<A, B>
Java
record Tuple3<A, B, C>(
A first,
B second,
C third
) implements Pair<A, B> {
}
そこで、新たに型クラスを使ってUniversal mapping propertyを導入します。次の定義では、Pairを実装する任意の型Pに対する追加の制約を導入します。
すなわち2つ組とは、任意のPairインターフェースを満たす型から一意に得られるような型である、という制約です。
interface TCPair<
T, U, P : Pair<T, U>> {
fun <Q : Pair<T, U>> terminal(
other: Q,
): P
}
Java
interface TCPair<
T, U, P extends Pair<T, U>> {
<Q extends Pair<T, U>> P terminal(
Q other
);
}
この型クラスには、2つ組であれば自明なインスタンスを与えることができます。
class Tuple2TCPair<T, U> :
TCPair<T, U, Tuple2<T, U>> {
override fun <Q : Pair<T, U>> terminal(
other: Q,
) = Tuple2(other.first, other.second)
}
class SizeTCPair<T> :
TCPair<T, T, Size<T>> {
override fun <Q : Pair<T, T>> terminal(
other: Q,
) = Size(other.first, other.second)
}
Java
class Tuple2TCPair<T, U> implements
TCPair<T, U, Tuple2<T, U>> {
public <Q extends Pair<T, U>> Tuple2<T, U> terminal(
Q q
) {
return new Tuple2<>(
q.first(),
q.second()
);
}
}
class SizeTCPair<T> implements
TCPair<T, T, Size<T>> {
public <Q extends Pair<T, T>> Size<T> terminal(
Q q
) {
return new Size<>(
q.first(),
q.second()
);
}
}
しかしながらTuple3はPairインターフェースを実装するもののTCPairのインスタンスを作れないため、2つ組ではありません。
class Tuple3TCPair<A, B, C> :
TCPair<A, B, Tuple3<A, B, C>> {
override fun <Q : Pair<A, B>> terminal(
other: Q,
) = Tuple3(
other.first,
other.second,
/* thirdがないので実装できない */
)
}
Java
class Tuple3TCPair<A, B, C> implements
TCPair<A, B, Tuple3<A, B, C>> {
public <Q extends Pair<A, B>> Tuple3<A, B, C> terminal(
Q other
) {
return new Tuple3(
other.first,
other.second,
/* thirdがないので実装できない */
)
}
}
TCPairの一般化
TCPair型クラスのような、UMPを提供する型クラスは次のように一般化できます。UMPには二種類があり、それぞれInitialとTerminalと名前をつけています。
実際のところTCPair型クラスはTCTerminal型クラスの特殊化です。
Initial型クラス
interface TCInitial<I : Condition, Condition> {
fun <J : Condition> initial(other: I): J
}
Java
interface TCInitial<I extends Condition, Condition> {
<J extends Condition> J initial(I other);
}
Terminal型クラス
interface TCTerminal<T : Condition, Condition> {
fun <U : Condition> terminal(other: U): T;
}
Java
interface TCTerminal<T extends Condition, Condition> {
<U extends Condition> T terminal(U other);
}
TCPair
TCPairのTerminalTCを使った定義です。
interface TCPair<T, U, P : Pair<T, U>> :
TCTerminal<P, Pair<T, U>> {
override fun <Q : Pair<T, U>> terminal(other: Q): P
}
Java
interface TCPair<T, U, P extends Pair<T, U>> extends
TerminalTC<P, Pair<T, U>> {
}
Discussion
型変換の型クラス。単射、全射、全単射
TerminalやInitialの条件が不必要に強すぎる。
TやIは必ずしもCを実装している必要はない