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


# どう使うのか

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

```scala
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より）、これを解読していく前に、いくつか予備知識の復習をしておきたい。

```scala
@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つの型コンストラクタでは中置記法が使えるというもの。

```scala
// たとえばこんな型コンストラクタがあるとき
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パラメータに供給される。

```scala
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パラメータ型のサブ型であってもよい。

```scala
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パラメータ型のサブ型でもあってよいという前項のルールと、変位指定によるサブ型関係から自然に導かれるとおり。

```scala
// 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` 型のサブ型関係
引数がひとつの関数の型定義は次のようになっている。

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

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

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

# generalized type constraints のしくみ

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

```scala
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]` 型変数に対して呼び出してみる。これがどのように動作するかを見ていく。

```scala
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な識別子が供給されていないかを確認すると、これ↓が見つかる。

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

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

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

```scala
// 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に限らないけれど。