Ordered and Ordering

Scalaには2値の比較を扱うtraitがあります。一つはComparable[T]を継承しているOredered[T]、もう一つはComparator[T]を継承しているOrdering[T]です。

Comparable[T]はjava.util.Comparable、Comparator[T]はjava.util.Comparatorに対応しており、前者はcompareTo(t)を、後者はcompare(t1, t2)を持っています。つまり自分と他のオブジェクトを比較するか、2つのオブジェクトを比較するか、という点が異なります。

Ordered[T]を扱っていると、たまにOrderingへの変換に失敗した、というコンパイルエラーが出ることがあります。これがどうも気になったので、今回はOrderedとOrderingの関係を調べてみました。

A comparison of Ordered[T]

2つのOrdered[T]を比較するメソッドを作成してみたいと思います。そもそもOrdered[K]はcompare(k: K)というメソッドを持っているので、それを使えば良いはず。

def compareAB[K](a: Ordered[K], b: Ordered[K]): Int = {
    a.compare(b)
}

しかしこのメソッドはコンパイルエラーになります。

エラーの原因は、Ordred[K]#compare(k: K)が引数に取るのはKであって、Ordered[K]ではないことにあります。Ordered[K]はKの親クラスではないので、型に互換性がありません。しかしcompareメソッドを持っているのはOrdered[K]なので、このメソッドを使うにはOrdered[K]の型で扱う必要があります。以上より、compareABメソッドの定義は以下となります。

def compareAB[K](a: Ordered[K], b: K): Int = {
    a.compare(b)
}

2値の比較であるにも関わらず、2値の型が違うのは違和感があります。

A way to sorting Ordered[K]

先ほどの例は2値の比較だったので引数の型の調整は簡単に行えました。しかし、これが任意の要素を対象とした場合、どうなるのでしょうか？ 特に方法を思いつけなかったので、sortを行うAPIを見てみたところ、scala.util.Sortingに以下のメソッドが定義されていました。

def quickSort[K: Ordering](a: Array[K]) { sort1(a, 0, a.length) }

[K: Ordering]という箇所の意味が分からず調べてみたところ、これはContext Boundと呼ばれるシンタックスシュガーでした。

View Bound／Context Bound ｜ ブログ．武田ソフト．jp

これをシンタックスシュガーを適用せずに記述すると以下になります。

def quickSort[K](a: Array[K])(implicit arg0: Ordering[K]): Unit

SortingのAPIリファレンスにもこの形式で載っています。前記のシンタックスシュガーを使っているのはソースコードの方です。

とはいえ丸括弧が2つ連なっており、そんなに分かりやすくなった感も無いのですが、要はソート対象のArray以外に、Ordering[K]という暗黙パラメータを指定する仕組みになっています。

Orderingは前記のとおり、2値を比較するメソッドcompareを保持している為、quickSortメソッドの中ではこの暗黙パラメータを使って値の比較を行うことになっています。

Where has this implicit parameter defined?

Ordering[K]はどこで定義されているのでしょうか？ 試しに、以下のようなコードを書いてみました。

OrderedCompareTest.scala: 

 1package net.wrap_trap.scala.examples
 2
 3import java.util.Comparator
 4
 5object OrderedCompareTest {
 6    def main(args : Array[String]) : Unit = {
 7
 8        System.out.println("called main")
 9        System.out.println(
10            compareAB(new OrderedClass(2), new OrderedClass(1)))
11    }
12    
13    class OrderedClass(val n: Int) extends Ordered[OrderedClass] {
14        System.out.println("called new OrderedClass")
15        def compare(that: OrderedClass) =  this.n - that.n
16    } 
17
18    // View Bound from scala.math.LowPriorityOrderingImplicits 
19    implicit def ordered[T <% Comparable[T]]: Ordering[T] = new Ordering[T] {
20    /* = implicit def ordered[T](implicit f: T => Comparable[T]): Ordering[T] = new Ordering[T] { */
21        System.out.println("called ordered. f: " + implicitly)
22        def compare(x: T, y: T): Int = {
23            x.compareTo(y) 
24        }
25    }
26    
27    // Context Bound
28    def compareAB[K:Ordering](a: K, b: K): Int = {
29    /* = def compareAB[K](a: K, b: K)(implicit comp: Ordering[K]): Int = { */
30        val comp = implicitly
31        System.out.println("called compareAB comp:" + comp)
32        comp.compare(a, b);
33    }
34}

Context Boundを使っていたquickSortのメソッド定義を、compareABという2値を比較するメソッドに適用してみました(上記コードの最下部)。

このメソッドの中で、暗黙パラメータをimplicitlyメソッドで取得しコンソールに出力してみたところ、Ordering[K]はscala.math.LowPriorityOrderingImplicitsで定義されていました。ソースコードは以下となります。

 1trait LowPriorityOrderingImplicits {
 2  /** This would conflict with all the nice implicit Orderings
 3   *  available, but thanks to the magic of prioritized implicits
 4   *  via subclassing we can make `Ordered[A] => Ordering[A]` only
 5   *  turn up if nothing else works.  Since `Ordered[A]` extends
 6   *  `Comparable[A]` anyway, we can throw in some Java interop too.
 7   */
 8  implicit def ordered[A <% Comparable[A]]: Ordering[A] = new Ordering[A] {
 9    def compare(x: A, y: A): Int = x compareTo y
10  }
11  implicit def comparatorToOrdering[A](implicit cmp: Comparator[A]): Ordering[A] = new Ordering[A] {
12    def compare(x: A, y: A) = cmp.compare(x, y)
13  }
14}

2つの暗黙的な型変換を行うメソッドが定義されていますが、今回はorderedの方が適用されていました。暗黙的な型変換は定義されたメソッドのスコープが近い方が優先されるはずなので、先ほどのコード上で同じメソッドを定義し、そちらが暗黙裡に呼ばれるようにしています。

そしてこのメソッドも[A <% Comparable[A]]という部分が理解できませんでした。調べてみたところ、こちらはView Boundと呼ばれるシンタックスシュガーでした。詳しくは前記の「ブログ.武田ソフト.jp」のページを参照してください。

要は、AがComparable[A]に変換可能である場合、AをOrdering[A]に変換する暗黙的な型変換メソッドを定義しています。

今回の場合、Kの親クラスはOrdered[K]で、Ordered[K]の親traitはComparable[K]なので、KはComparable[K]に変換可能であることから、この条件が成り立ちます。このメソッドによって暗黙パラメータのOrdering[K]が提供されていたことになります。

ということで、Comparable[K]からOrdering[K]が生成され、それをcompareABが使用することで、K(extends Order[K])の2値を比較することができました。

A comparison of K(not Ordered[K])

もしKがOrdered[K]を継承していないとしたら、LowPriorityOrderingImplicits#orderedが適用されず、Ordering[K]が生成されない為、compareABメソッドは実行できないことになります。

これを確かめる為、前記のコードをOrdered[K]を継承していないクラスに適用してみました。

OrderedCompareTest2.scala: 

 1package net.wrap_trap.scala.examples
 2
 3import java.util.Comparator
 4
 5object OrderedCompareTest2 {
 6    def main(args : Array[String]) : Unit = {
 7
 8        System.out.println("called main")
 9        // compile error when disabling nonOrderedClassToComparable Method. 
10        // No implicit Ordering defined for 
11        // net.wrap_trap.scala.examples.OrderedCompareTest2.NonOrderedClass.
12        System.out.println(
13            compareAB(new NonOrderedClass(4), new NonOrderedClass(3)))     
14    }
15    
16    class NonOrderedClass(val n: Int) {}
17
18    implicit def nonOrderedClassToComparable(from: NonOrderedClass): Comparable[NonOrderedClass] = {
19        new Comparable[NonOrderedClass] {
20            def compareTo(b: NonOrderedClass): Int = {
21                from.n - b.n
22            }
23        }
24    }
25    
26    // View Bound from scala.math.LowPriorityOrderingImplicits 
27    implicit def ordered[T <% Comparable[T]]: Ordering[T] = new Ordering[T] {
28    /* = implicit def ordered[T](implicit f: T => Comparable[T]): Ordering[T] = new Ordering[T] { */
29        def compare(x: T, y: T): Int = {
30            x.compareTo(y) 
31        }
32    }
33    
34    // Context Bound
35    def compareAB[K:Ordering](a: K, b: K): Int = {
36    /* = def compareAB2[K](a: K, b: K)(implicit comp: Ordering[K]): Int = { */
37        val comp = Ordering[K]
38        System.out.println("called compareAB comp:" + comp)
39        comp.compare(a, b);
40    }
41}

すると以下のコンパイルエラーがでました。

No implicit Ordering defined for
net.wrap_trap.scala.examples.OrderedCompareTest2.NonOrderedClass.

やはりComparable[K]に変換できないことが原因のようです。

Comparable[K]に変換できるように、暗黙的な型変換メソッド「nonOrderedClassToComparable」を定義したところ、コンパイルがとおり、Ordered[K]の時と同じ結果になりました。

Conclusion

今回はOrdered[K]とOrdering[K]の関係について調べてみました。元々はHaskellの赤黒木のコードをScalaに移植するのが事の始まりなのですが、implicitな型変換、パラメータやシンタックスシュガーによって簡素化された構文が理解できず大分苦労しています。今回の件で暗黙パラメータ、View BoundとContext Boundは理解できたので、ここから先はスラスラ行く、と思いたい…。