読者です 読者をやめる 読者になる 読者になる

きくらげ観察日記

好きなことを、適当に。

implicit parameterによる型クラスの罠

Scala

Scalaの型クラスは暗黙引数の受け渡しにより行われるため、スコープごとに同一な型クラスの別なインスタンス実装を使うことができます。
例えば、以下のような比較を行う型クラス、Cmpを考えてみましょう。

trait Cmp[A] {
  def eq(x : A, y : A) : Boolean
  def lt(x : A, y : A) : Boolean
}

これに対して、例えばIntであれば少なくとも以下の2種類のインスタンスが考えられます。

// 昇順
object IntCmp extends Cmp[Int] {
  def eq(x : Int, y : Int) : Boolean = x == y
  def lt(x : Int, y : Int) : Boolean = x < y
}

// 降順
object IntRevCmp extends Cmp[Int] {
  def eq(x : Int, y : Int) : Boolean = x == y
  def lt(x : Int, y : Int) : Boolean = x > y
}

この時点では特に問題はありません。
しかし、以下のようなデータ構造を考えてみましょう。

sealed trait TreeSet[+A]
case class Branch[A](x : A, left : TreeSet[A], right : TreeSet[A]) extends TreeSet[A]
case object Leaf extends TreeSet[Nothing]

object TreeSet {

  def empty[A] : TreeSet[A] = Leaf

  def insert[A](x : A, tree : TreeSet[A])(implicit C : Cmp[A]) : TreeSet[A] =
    tree match {
      case Leaf => Branch(x, Leaf, Leaf)
      case Branch(y, left, right) =>
        if (C.eq(x, y))
          tree
        else if (C.lt(x, y))
          Branch(y, insert(x, left), right)
        else
          Branch(y, left, insert(x, right))
    }

  def fromSeq[A](xs : Seq[A])(implicit C : Cmp[A]) : TreeSet[A] =
    xs.foldLeft(Leaf : TreeSet[A]){ (tr, x) => insert(x, tr) }

  def apply[A](elems : A*)(implicit C : Cmp[A]) : TreeSet[A] =
    TreeSet.fromSeq(elems)

  def elem[A](x : A, tree : TreeSet[A])(implicit C : Cmp[A]) : Boolean =
    tree match {
      case Leaf => false
      case Branch(y, left, right) =>
        if (C.eq(x, y))
          true
        else if (C.lt(x, y))
          elem(x, left)
        else
          elem(x, right)
    }
}

これは、Cmp[A]で与えられた順序を元にした2分木によるツリーセットです(平衡をとったりはしていませんが、あくまで例なのでご了承ください)。

これを使うライブラリを考えてみましょう。

object Hoge {
  implicit val C : Cmp[Int] = IntCmp
  val someSet = TreeSet(5, 3, 7, 1, 6)
}

Hogeライブラリでは、昇順のCmpを利用したツリーセット、someSetを定義しています。

object Fuga {
  implicit val C : Cmp[Int] = IntRevCmp
  def is7InSet(set : TreeSet[Int]) : Boolean =
    TreeSet.elem(7, set)
}

一方こちらのFugaライブラリでは、与えられたツリーセットに7が含まれているかどうかを判定する関数を定義しています。

これらのモジュールを使用するプログラムを考えてみましょう。

object Main extends App {
  println("Hoge.someSet = " + Hoge.someSet.toString)
  if (Fuga.is7InSet(Hoge.someSet))
    println("7 is in someSet")
  else
    println("7 is not in someSet")
}

この実行結果はどうなるでしょうか?

$ scala Main
Hoge.someSet = Branch(5,Branch(3,Branch(1,Leaf,Leaf),Leaf),Branch(7,Branch(6,Leaf,Leaf),Leaf))
7 is not in someSet

someSetには7が含まれているにも関わらず、"7 is not in someSet"と表示されてしまいました。
これはHoge.someSetがIntCmpを使っているのに対し、Fuga.is7InSetがIntRevCmpを使っていることが原因になります。

一つの型クラスに対して複数のインスタンスが定義できるのは便利ではありますが、場合によってはこういった落とし穴もあるんですね。
実用上このような問題が起こることはあまりないとは思いますが。