act-act about projects rss

Ordered And Ordering

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)というメソッドを持っているので、それを使えば良いはず。

1
2
3
    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メソッドの定義は以下となります。

1
2
3
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に以下のメソッドが定義されていました。

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

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

View Bound/Context Bound | ブログ.武田ソフト.jp

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

1
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package net.wrap_trap.scala.examples

import java.util.Comparator

object OrderedCompareTest {
    def main(args : Array[String]) : Unit = {

        System.out.println("called main")
        System.out.println(
            compareAB(new OrderedClass(2), new OrderedClass(1)))
    }
    
    class OrderedClass(val n: Int) extends Ordered[OrderedClass] {
        System.out.println("called new OrderedClass")
        def compare(that: OrderedClass) =  this.n - that.n
    } 

    // View Bound from scala.math.LowPriorityOrderingImplicits 
    implicit def ordered[T <% Comparable[T]]: Ordering[T] = new Ordering[T] {
    /* = implicit def ordered[T](implicit f: T => Comparable[T]): Ordering[T] = new Ordering[T] { */
        System.out.println("called ordered. f: " + implicitly)
        def compare(x: T, y: T): Int = {
            x.compareTo(y) 
        }
    }
    
    // Context Bound
    def compareAB[K:Ordering](a: K, b: K): Int = {
    /* = def compareAB[K](a: K, b: K)(implicit comp: Ordering[K]): Int = { */
        val comp = implicitly
        System.out.println("called compareAB comp:" + comp)
        comp.compare(a, b);
    }
}

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
package net.wrap_trap.scala.examples

import java.util.Comparator

object OrderedCompareTest2 {
    def main(args : Array[String]) : Unit = {

        System.out.println("called main")
        // compile error when disabling nonOrderedClassToComparable Method. 
        // No implicit Ordering defined for 
        // net.wrap_trap.scala.examples.OrderedCompareTest2.NonOrderedClass.
        System.out.println(
            compareAB(new NonOrderedClass(4), new NonOrderedClass(3)))     
    }
    
    class NonOrderedClass(val n: Int) {}

    implicit def nonOrderedClassToComparable(from: NonOrderedClass): Comparable[NonOrderedClass] = {
        new Comparable[NonOrderedClass] {
            def compareTo(b: NonOrderedClass): Int = {
                from.n - b.n
            }
        }
    }
    
    // View Bound from scala.math.LowPriorityOrderingImplicits 
    implicit def ordered[T <% Comparable[T]]: Ordering[T] = new Ordering[T] {
    /* = implicit def ordered[T](implicit f: T => Comparable[T]): Ordering[T] = new Ordering[T] { */
        def compare(x: T, y: T): Int = {
            x.compareTo(y) 
        }
    }
    
    // Context Bound
    def compareAB[K:Ordering](a: K, b: K): Int = {
    /* = def compareAB2[K](a: K, b: K)(implicit comp: Ordering[K]): Int = { */
        val comp = Ordering[K]
        System.out.println("called compareAB comp:" + comp)
        comp.compare(a, b);
    }
}

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

1
2
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は理解できたので、ここから先はスラスラ行く、と思いたい…。