[Scala] generalized type constraints （ <:< と =:= ）のしくみ

どう使うのか

たとえば、実際にScalaのコレクションライブラリにある例だけど、 List[E] に、E が Tuple2 である場合にのみ呼出可能なメソッドを定義することなどができる。

class Map[K, V]

// implicit ev: E <:< (T, U) のところが、generalized type constraints
// 型Eが型(T, U)のサブ型でなければならないと表明している
class List[E] {
  def toMap[T, U](implicit ev: E <:< (T, U)): Map[T, U] = new Map[T, U]
}

// List[Int]に対するtoMap呼出はコンパイルエラーになる
val ints = new List[Int]
ints.toMap
// <console>:17: error: Cannot prove that Int <:< (T, U).
//        ints.toMap
//             ^

// List[(Int, String)]に対してはtoMap呼出可
val tuples = new List[(Int, String)]
tuples.toMap
// res10: Map[Int,String] = Map@18759a

<:< と =:= の定義

<:< と =:= はどちらも、Predef.scala でクラスとして定義されている。とりあえず定義部分を抜粋するけど（Scala2.12.8より）、これを解読していく前に、いくつか予備知識の復習をしておきたい。

@implicitNotFound(msg = "Cannot prove that ${From} <:< ${To}.")
sealed abstract class <:<[-From, +To] extends (From => To) with Serializable
private[this] final val singleton_<:< = new <:<[Any,Any] { def apply(x: Any): Any = x }
implicit def $conforms[A]: A <:< A = singleton_<:<.asInstanceOf[A <:< A]

@deprecated("use `implicitly[T <:< U]` or `identity` instead.", "2.11.0")
def conforms[A]: A <:< A = $conforms[A]

@implicitNotFound(msg = "Cannot prove that ${From} =:= ${To}.")
sealed abstract class =:=[From, To] extends (From => To) with Serializable
private[this] final val singleton_=:= = new =:=[Any,Any] { def apply(x: Any): Any = x }
object =:= {
   implicit def tpEquals[A]: A =:= A = singleton_=:=.asInstanceOf[A =:= A]
}

予備知識

中置型

パラメータが2つの型コンストラクタでは中置記法が使えるというもの。

// たとえばこんな型コンストラクタがあるとき
class Map[K, V]

// Map[String, Int] と書くかわりに String Map Int と書いてもよいことになっている。
// 中置記法を使うことが想定される型コンストラクタは演算子っぽく記号で定義したりする。
type ~>[K, V] = Map[K, V]
def scoresMap: String ~> Int = ???
// scoresMap: String ~> Int

implicitパラメータの解決

implicit宣言された関数

スコープ内にあるimplicit宣言つきの関数で、求められているimplicitパラメータと同じ型の戻り値をもつものがあれば、その関数が暗黙に実行され、戻り値がimplicitパラメータに供給される。

class Config
def execute()(implicit config: Config): String = s"Config: $config"

implicit def _findConfig: Config = new Config
execute()
// res26: String = Config: Config@791c14a

サブ型の変数によるimplicitパラメータ解決

スコープ内に存在しなければならないimplicitな変数は、探しているimplicitパラメータ型のサブ型であってもよい。

class A
class B extends A

def aClassName(implicit a: A): String = a.getClass.getName

// スコープにimplicitなB型変数がある状態でaClassNameを呼び出すと
// B型変数の値がA型の暗黙パラメータとして供給される
implicit val _b: B = new B()
aClassName
// res15: String = B

implicitパラメータ解決と変位指定

暗黙に供給される値はimplicitパラメータ型のサブ型でもあってよいという前項のルールと、変位指定によるサブ型関係から自然に導かれるとおり。

// CellがTについて非変の場合、Cell[A]とCell[B]にはサブ型関係が存在しないので、
// Cell[B]型のimplicitな変数をスコープに定義しても、implicitパラメータは解決できない
case class Cell[T](value: T)
def aCell(implicit cell: Cell[A]): String = s"Type of the cell value: ${cell.value.getClass.getName}"

implicit val _bCell: Cell[B] = new Cell[B](new B)
aCell
// <console>:20: error: could not find implicit value for parameter cell: Cell[A]
//        aCell

// CellがTについて共変の場合、Cell[B]はCell[A]のサブ型なので、
// Cell[B]型のimplicitな変数をスコープに定義すると、implicitパラメータを解決できる
case class Cell[+T](value: T)
def aCell(implicit cell: Cell[A]): String = s"Type of the cell value: ${cell.value.getClass.getName}"

implicit val _bCell: Cell[B] = new Cell[B](new B)
aCell
// res25: String = Type of the cell value: B

// 反変についても同様（略）

Function1 型のサブ型関係

引数がひとつの関数の型定義は次のようになっている。

// T1が引数の型、Rが戻り値の型
trait Function1[-T1, +R] 

Function1 型は戻り値について共変なので、たとえば次のような代入が成立する（AとBは前項で宣言したクラス）。

// 戻り値がBの関数を、戻り値がAの関数型の変数に代入できる
val func: Function1[String, A] = str => new B
func("Give me an A instance!")
// res27: A = B@33935a7a

generalized type constraints のしくみ

<:< の定義を改めて抜粋。

sealed abstract class <:<[-From, +To] extends (From => To) with Serializable
private[this] final val singleton_<:< = new <:<[Any,Any] { def apply(x: Any): Any = x }
implicit def $conforms[A]: A <:< A = singleton_<:<.asInstanceOf[A <:< A]

つづいて、例として、Cell クラスに、T が CharSequence の場合のみ呼出可能なメソッドを作り、それを Cell[String] 型変数に対して呼び出してみる。これがどのように動作するかを見ていく。

case class Cell[T](value: T) {
  def subSequence(start: Int, end: Int)(implicit ev: T <:< CharSequence): Cell[CharSequence] = Cell(value.subSequence(start, end))
}

Cell("Hello, world!!").subSequence(7, 12)
// res40: Cell[CharSequence] = Cell(world)

T が String 型であるとき、 Cell#subSequence 呼出では String <:< CharSequence 型のimplicit宣言された変数、もしくは String <:< CharSequence 型の値を返すimplicit宣言された関数がスコープから検索される。String <:< CharSequence がひとつの型を表しているということがいまいちピンと来ない場合は、中置記法を <:<[String, CharSequence] と読み替えてみるとよいかもしれない。ともかく、Predef.scalaにそれっぽいimplicitな識別子が供給されていないかを確認すると、これ↓が見つかる。

implicit def $conforms[A]: A <:< A = singleton_<:<.asInstanceOf[A <:< A]

この関数の戻り値は A <:< A 型なので、<:< 型コンストラクタによって生成される型のうち、2つの型パラメータが同じであるものに対してだけ、implicitな値が供給される。 String <:< String 型のimplicitな値なら見つかるけれど、 String <:< CharSequence 型の値は見つからないということになる。

だけど、ここで、暗黙に供給される値は求められているパラメータ型のサブ型であってもよいことを思い出そう。 <:< の型パラメータ宣言は <:<[-From, +To] で、2つ目のパラメータについて共変なので、String <:< String は String <:< CharSequence のサブ型となる。String <:< CharSequence 型のimplicitパラメータは、 $conforms[A] が String <:< String 型の値を返すことによって、供給されるのである。つまり、変位指定から生まれるサブ型関係によって、「 T は CharSequence のサブ型である」が成り立つ場合のみ T <:< CharSequence 型のimplicit値が供給されるという仕組みが実現されている。

このimplicitパラメータは「 T が CharSequence のサブ型である」が成り立つことを示す証拠なので、エビデンス、略して ev などといったパラメータ名がよくつけられる¹。とはいえ、このパラメータの役割は単なる証拠にとどまらず、メソッド内部でも用いられる。 <:< クラスは Function1 を継承しており、 T <:< CharSequence であれば T 型の値を受け取って CharSequence 型の値を返す。その関数の apply 定義は下記のとおりで、受け取った値をそのまま返しているだけなのだけど、それが代入される変数 ev は T 型を受け取り CharSequence 型を返す関数型なので、その呼出は要するに T から CharSequence へのキャストを行うのに等しい。ev が供給された時点で T は CharSequence のサブ型であることが保証されているので、これは安全なアップキャストとなる。

private[this] final val singleton_<:< = new <:<[Any,Any] { def apply(x: Any): Any = x }

それが、今度は暗黙の型変換としてメソッドのボディで利用される。暗黙パラメータの解決と、暗黙の安全な型変換がきれいに調和している。

// T型変数valueをCharSequence型に暗黙変換してsubSequenceを呼び出す
Cell(value.subSequence(start, end))
// ↓
Cell(ev(value).subSequence(start, end))

もうひとつのクラス =:= も仕組みはほとんど変わらない。こちらは型が正確に一致する場合のみimplicitパラメータを供給しなくてはならないので、=:= は型パラメータを非変としている。暗黙の型変換の仕組みもほぼ同じで、たとえばパラメータ implicit ev: T =:= Int であれば、定義上は T 型値を Int 型値にキャストする関数だけど、実際には T が Int である場合のみ暗黙に供給され、結果的に Int 値を受け取ってそのまま Int 型で返す関数となる。

1. implicitパラメータがエビデンスと呼ばれるのはgeneralized type constraintsに限らないけれど。 ↩