型クラスをOrderingを用いて説明してみる

ちょっと今日は疲れてるので、表題の件について、簡単に書いてみる。私の経験上、型クラスにおける、最も多い誤解は、(Javaとかにおける）インタフェースのようなもの、というもので、これはかなり多くの人にみられるように思う。

まず、そもそも、何故そういう勘違いが生まれたかを考えてみると、「インスタンス」「メソッド」といったオブジェクト指向言語にもある用語が使われていること、また、両者とも「操作の集合を提供する」という特徴があるためではないかと思う。しかし、根本的な違いがある。一番大きなものは、型クラスは（一般的には）レシーバ（thisといってもselfといってもなんでもいいが）とそれに付随する状態が基本的に存在しない、という点だ。

この点について、Scalaの標準ライブラリにおいて、両者の違いを説明するのに格好の例がある。OrderingとOrderedだ。混乱を避けるために先に説明しておくと、両者ともScala言語上の仕組みとしては、trait（≒実装ありインタフェース）なのだが、Orderingは、this（の状態）を使わずに全てのメソッドのプロトコルが定義されているのに対して、Orderedはthisと引数との比較をするためのプロトコルが定義されている。

まず、比較する対象のクラスPersonを定義する。比較がしたいだけなので、これはage: Intをフィールドとしてもつcase classとして実装することにする。以下のようになる：

case class Person(age: Int)

OrderedとOrderingのPersonに関する実装を、それぞれ書いてみる。まずはOrdering[Person]だ。

import scala.math.Ordering

implicit object PersonOrdering extends Ordering[Person] {
  override def compare(x: Person, y: Person): Int = {
    if(x.age < y.age) -1 else if(x.age > y.age) 1 else 0
  }
}

ここで、どっかで見たことあるような…と思った人は鋭いが、これは、java.util.Comparator<T>とほぼ同じだ。違いはどこかというと、Orderingはimplicit parameterとして与えられると、（まさに）implicitに検索されて、コンパイラによって追加の引数として与えられるのに対して、java.util.Comparator<T>は呼ぶ側がexplicitに与えなければいけないという点にある（これは不正確で、実際のところ、java.util.Comparator<T>がimplicit parameterとして宣言されれば、それは型クラスとして振る舞う。正しい説明としては、java.util.Comparator<T>はexplicitに与える「ため」にもっぱら使われる、ということになるだろう）。さて、java.util.Comparator<T>のような使い方は、オブジェクト指向言語では一般的にStrategyパターンとして知られているが、型クラスはStrategyを暗黙に渡すための言語機構を用意しているということができる。実際のところ、これで説明はほとんど終わりだ（コンパイラがどうやってStrategyを見つけるのかという点を説明していないが）。

次に、Orderedについて考えてみる。これは次のようになる：

import scala.math.Ordered
case class Person(age: Int) extends Ordered[Person] {
  def compare(that: Person): Int = {
    if(this.age < that.age) -1 else if(this.age > that.age) 1 else 0
  }
}

ここで、元のPersonのクラス定義を書き換えている、というか、書き換えないと実用にならないという点が一つの問題になる。定義を書き換えない方法として、ラッパーを作る、例えば次のようにすることも可能ではある：

import scala.math.Ordered
case class PersonWrapper(person: Person) extends Ordered[Person] {
  def compare(that: Person): Int = {
    if(this.person.age < that.age) -1 else if(this.person.age > that.age) 1 else 0
  }
}

しかし、ちょっと考えればわかるが、たとえば、Personのリストをソートしたいのに、そのために全要素をラッパーに変換する、という操作を事前に行うのは、オブジェクトの確保コストが馬鹿にならないし、とても面倒でもあり、およそ非実用的だ。なので、Orderedをまともに運用したければ、ほとんど必然的に元のデータ型の定義を書き換える必要に迫られる*1

これが、通常の、(thisが）状態を持ったインタフェースをベースにした解決策の問題だ。一方、Orderingを使った解決策では、事前に比較関数を準備しなくても、後付けで比較方法を提供できる。通常のStrategyパターンでは、Orderingを明示的に渡す必要があるが、型クラスを用いるとそこも暗黙的にできる。たとえば、このような感じになる：

List(Person(1), Person(5), Person(3)).sorted // => List(Person(1), Person(3), Person(5))

まとめ

通常のインタフェースベースと型クラスベースの解決策の最大の違いは、レシーバの状態を必要とするかしないか（正確には、型クラスにおいて、レシーバは登場しないが、オブジェクト指向言語では全てのメソッド呼び出しがレシーバを持つため、オブジェクト指向言語において型クラス相当の機能を提供する場合、レシーバを「使わない」という形になるはず）
型クラスベースの解決策では、ある種の型に対する操作の集合を「後付けで」与えることができる
型クラスのインスタンスを作ることは、Strategyパターンにおいて具体的なStrategyを定義するようなもの`
どのようなStrategyが引数に与えられるかをコンパイラが推論できるようにしたものが型クラスである

言い訳

Wadlerらが提案した元々の型クラスとは、実際の裏側の仕組みや、型推論との関連において異なる。また、オーバーロードを一般化したものという元々の提案にあった視点についても、うまく説明に取り込むことができなかったため、あえて書いていない。型クラスの継承についてもはしょった。ただ、状態を保たない操作の集合を提供するものが型クラスである、という視点を得ることができれば（この点でつまづく人が多いように思う）、型クラスのその他の点について理解することもそれほど困難ではないと考えている。

*1:実は、Scalaの機能の一つであるimplicit conversionを使えば面倒さに関してはなんとかすることも可能ではあるが、オブジェクト確保のコストに関してはどうしようもない

kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

型クラスをOrderingを用いて説明してみる

まとめ

言い訳