kmizuの日記

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

型クラスの真の力を見せる

昨日、

kmizu.hatenablog.com

という記事を書いたわけだが、その後、今日、型クラスに関する議論が一部で(?)盛り上がっているようだ。それは型クラスじゃなくても実現できるのでは、いや、やっぱりインタフェースのようなものと思っていいのでは、などなど。

今回の記事では、型クラスじゃないと実現が著しく困難であると思われる 使い方について書くことにする。

まず、前の記事では、Orderingの使い方を通して、型クラスの単純な使い方について説明したのであった。単純なオブジェクトの場合はそれでもいいが、より複雑なオブジェクトをOrderingを使ってソートしたい場合、前回の記事のようなやり方だけでは難しいことがある。

一例として、(A, B)というタプル型、つまり、A型の要素とB型の要素からなるペアを比較して、ソートしたいという要求を考える(実際には、標準ライブラリでタプル型の比較が提供されてしまっているので、新しい型MTuple[A, B]について考える)。このとき、タプル型同士を比較するOrderingを提供する段階では、ABも何が来るか全く不明なので、一見、そのままではOrderingを提供できないように見える。しかし、実は型クラスでは一般にそれができるのである、ということを示そう。

最初の、しかし、うまく動かないバージョンを以下に示す:

case class MTuple[A, B](_1: A, _2: B)
implicit def tupleOrdering[A, B]: Ordering[MTuple[A, B]] = new Ordering[MTuple(A, B)] {
  override def compare(x: MTuple[A, B], y: MTuple[A, B]): Int = {
    ???
  }
}

前の記事ではimplicit objectであったのが、implicit defになっているが、これはobjectジェネリックになれないため、仕方なく(?)そうなっているだけあり、本題とは関係ないので気にしないで欲しい。

???の部分を埋めて実装を完成させたいのだが、問題は、ABが何者であるかわからないため、比較を実装するのが無理である点だ。このcompareを実装するためには、Ordering[A]Ordering[B]の二つのインスタンスが必要で、しかも、今、私はオブジェクトを暗黙に渡して欲しいのだから、これらを明示的に与えるのは論外だ。では、どうすればいいのか?

回答を先に示す:

import scala.math.Ordering
case class MTuple[A, B](_1: A, _2: B)
implicit def tupleOrdering[A, B](implicit a: Ordering[A], b: Ordering[B]): Ordering[MTuple[A, B]] = new Ordering[MTuple[A, B]] {
  override def compare(x: MTuple[A, B], y: MTuple[A, B]): Int = {
    val MTuple(x1, x2) = x
    val MTuple(y1, y2) = y
    val r1 = a.compare(x1, y1)
    if(r1 < 0) {
      -1
    } else if(r1 > 0){
      1
    } else {
      b.compare(x2, y2)
    }
  }
}

利用例は以下のようになる:

List(MTuple(1, 2), MTuple(4, 3)).sorted  // => List(MTuple(1, 2), MTuple(4, 3))
List(MTuple(4, 3), MTuple(1, 2)).sorted // => List(MTuple(1, 2), MTuple(4, 3))
List(MTuple(new Object, new Object), MTuple(new Object, new Object)).sorted // => error: No implicit Ordering defined for MTuple[Object,Object].

最後の例は、MTupleの構成要素であるObjectに対して、Orderingが定義されていないので、したがって、MTuple[Object, Object]インスタンスも見つけられないということを意味している。

ある型クラスが別の型クラスに依存しているようなパターンといえる。このようなパターンは、単純なStrategyを明示的に渡すパターンではそのまま模倣しづらい(あえていうと、Strategyがネストしたオブジェクトを渡せば可能だがとても面倒だ)。

このような、型クラスが別の型クラスに依存するようなパターンは、おそらく、たとえば、open classのようなものでは実現が難しいし、通常のインタフェースでも実現が難しいであろう。

このとき、Ordering[MTuple[A, B]]の結果が、ユーザが実装をみないでも予想できるくらい十分にわかりやすいものになっているようにする必要がある点には注意されたい。

今回は、タプルの第一要素を先に比較して、それで順序が決まる場合はそれに従った順序に、それで決まらない場合(第一要素が同じである場合)、第二要素の比較を行うという形の辞書順比較なので、十分わかりやすいと言えるだろう。

上記の実装の意味については、また別の記事で解説したい。今回は、型クラスの本当のパワー(というとHaskellerの方に怒られそうではあるが、型クラス的なものでなくては実装が面倒なパターン)を見せるのが主な目的であるので。