続<:<を使ってメソッド引数の型を限定する（厳密に）

# 前回の記事

前回、<:<を利用して型制限する例を示した。
[<:<を使ってメソッド引数の型を限定する](http://qiita.com/mtoyoshi/items/fbf2c744e3c7fd69a438)

ただし、次のようなときにうまくいかない事が判明。

- Any型として渡すとすり抜けてしまう
- Seqを受け付けると定義した際、サブクラスのListを渡すとエラー（特にこっちは普段使いに支障が出る）

```scala
/* Int もしくは String */
def foo[T](t:T)(implicit ev: Int with String <:< T): T = t
foo(2.3: Any) // Any型としての2.3が返ってくる ※コンパイルエラーにならない

/* SeqもしくはSet */
def bar[T[_], A](t: T[A])(implicit ev: Seq[A] with Set[A] <:< T[A]): T[A] = t
bar(List(1)) // error: Cannot prove that Seq[Int] with Set[Int] <:< List[Int].
```

この ```A with B <:< T``` というのはA with BのスーパークラスならOKという意味なのでAとB以外にもAnyなら当然OKだし、逆にAやBのサブクラスを渡すとエラーになるのも当然だ。

よって ```<:<``` を使ってORを表現する際、Tが第二パラメータではなく第一パラメータに来るように仕向けないとこれらの問題は防げそうにないことが分かる。
もうひとひねり必要になるというわけだ。
幸い参考サイトを教えていただき理解できたので、忘れないうちに自分の言葉で書き記しておこうと考えた。

参考サイト

- [Unboxed union types in Scala via the Curry-Howard isomorphism](http://www.chuusai.com/2011/06/09/scala-union-types-curry-howard/)
- [Scalaの型と論理](http://halcat0x15a.github.io/programming/curry_howard.html)

# 先に最終形を

```scala
type ¬[T] = T => Nothing
type ¬¬[T] = ¬[¬[T]]
type ∧[T, U] = T with U
type ∨[T, U] = ¬[¬[T] ∧ ¬[U]]
type |∨|[T, U] = {
  type λ[X] = ¬¬[X] <:< (T ∨ U)
}

def foo[T : (Int |∨| String)#λ](t: T): T = t

foo(1)  // 1
foo("hello")  // hello
foo(2.3)  // error: Cannot prove that (Double => Nothing) => Nothing <:< Int => Nothing with String => Nothing => Nothing.
foo(2.3: Any)  // error: Cannot prove that (Any => Nothing) => Nothing <:< Int => Nothing with String => Nothing => Nothing.


def bar[F[_], A](t: F[A])(implicit ev: ¬¬[F[A]] <:< (Set[A] ∨ Seq[A])): F[A] = t

bar(Set(1))  // Set(1)
bar(Seq(1))  // Seq(1) ※実際にはList(1)と表示
bar(List(1))  // List(1)
bar(Future.successful(1))  // error: Cannot prove that ¬¬[Future[Int]] <:< ∨[Set[Int],Seq[Int]].
```

ひとひねりどころじゃねーじゃねーかというツッコミが聞こえてきそう。

なおこれは [Shapeless](https://github.com/milessabin/shapeless/blob/master/core/src/main/scala/shapeless/package.scala) に実際に定義されている。

# 解説

## ANDとORとNOT
まずはこれらの定義から。
ANDはwithを使って表現できる。

```scala
type AND[T, U] = T with U
```

しかしANDにおけるwithのようにORを表現できるものはScalaには存在しない。

ではどうするか？
ド・モルガンの法則により、ORはANDとNOTを使って表現できるのであった。

```
A OR B = !(!A AND !B)
```

ではNOTはどう表現するのか？
やはりこれもダイレクトに表現出来るものは存在しない（!はBoolean型の否定なので今回求めているものとは違う）。
が、NOTをFunction1で以下のように表現することとしている。

```scala
type NOT[T] = T => Nothing
```

自分なりの理解では、

- Nothingは偽を表現するのに相応しい
- 最終的には<:<と組み合わせて使う必要があるわけだがNothing型には該当する値(インスタンス)がないので型定義の上でのロジックに終始することが出来、渡ってくる値から誤判断する事故が防げる
- 後で詳しく見るが、Function1を使うことでFunction1の型パラメータに設定されている共変・反変定義がいい感じに作用する

という理由でこう表現したのでは、、と考えているが完全に理解したとは言いがたい。
が、とにかくNOTをこのようなFunction1で表現するという発明(?)によって、重要なピースが埋まった。残りは比較的サクサク進んでいくこととなる。

というわけでORは以下のように定義できる。

```scala
type OR[T, U] = NOT[NOT[T] AND NOT[U]]
```

## implicit部の定義
ORを使って書いてみる。

```scala
def foo[T](t: T)(implicit ev: T <:< (Int OR String)): T = t
```

が、OKになってほしいIntやStringの値をfooに渡してもうまくいかない。

というのも ```Int OR String``` は ```(Int => Nothing) with (String => Nothing) => Nothing``` なFunction1でありIntやStringとそもそも継承関係がない。
というわけで、TをFunction1にしつつ、ORと合わせるにはNOTを使うのが手っ取り早い。

```scala
def foo[T](t: T)(implicit ev: NOT[NOT[T]] <:< (Int OR String)): T = t
```

これでIntの場合は ```(Int => Nothing) => Nothing``` となり ```(Int => Nothing) with (String => Nothing) => Nothing``` と揃うようになる。
もちろん否定の否定なのでもとのTと意味的にも同じだ（もちろん、型は変わってしまっている）。

```scala
implicitly[NOT[NOT[Int]] <:< (Int OR String)]  // <:<[NOT[NOT[Int]],OR[Int,String]] = <function1>
```

というわけで無事見つかるようになった。基本的にはこれで完成。

あとはカッコよく仕上げていくフェーズとなる。

### ところでなんで無事見つかるんだっけ？
前回説明したように、$conformsというimplicit def で宣言された関数から ```<:<``` 型のインスタンスが生成される。
今回の場合は、 ```<:<[(Int => Nothing) => Nothing, (Int => Nothing) => Nothing]``` 。
実際には ```<:<[(Int => Nothing) => Nothing, (Int => Nothing) with (String => Nothing) => Nothing]``` を探しているので、 ```<:<[(Int => Nothing) => Nothing, (Int => Nothing) with (String => Nothing) => Nothing]``` に ```<:<[(Int => Nothing) => Nothing, (Int => Nothing) => Nothing]``` が代入可能ならOK、つまり見つかったということになる。

<:<の１つ目の型は同じなので問題ない。

２つ目。共変設定がされているので、 ```(Int => Nothing) with (String => Nothing) => Nothing``` に ```(Int => Nothing) => Nothing``` が代入可能でなければならない。
ここもFunction1なわけだが、 ちょっとややこしいので簡単に置き換えると ```子 => Nothing``` に ```親 => Nothing``` が代入可能かということを言っている。
フツーに考えたら無理じゃね？となるわけだが、入力の型を表すFunction1の１つ目は反変定義されていることから子に親を代入することが可能である。

よく分からない場合は以下の例を参考に。
単純化するため ```(Int => Nothing) with (String => Nothing)``` を ```Cat（子）``` 、 ```(Int => Nothing)``` を```Animal（親）``` 、 ```Nothing``` を ```Int``` に置き換えてみたい。

```scala
trait Animal
trait Cat extends Animal

val x: Cat => Int = (a: Animal) => 100  // Cat(子) => Int に Animal(親) => Intが代入可能
```

で、更に ```<:<``` で考えると１つ目の型は同じ ```(Int => Nothing) => Nothing``` だったので、これを ```String``` にでも置き換えると以下が成り立つので当該のものも成り立つというわけだ。

```scala
val y: Function1[String, Cat => Int] = (s: String) => (a: Animal) => 100
```

## 仕上げその１：数学記号に置き換えていく
これまでAND、OR、NOTでやってきたがこれを書き換えていく。

```scala
type ¬[T] = T => Nothing
type ¬¬[T] = ¬[¬[T]]
type ∧[T, U] = T with U
type ∨[T, U] = ¬[¬[T] ∧ ¬[U]]
```

これで、先ほどのfooがこのようになる。

```scala
def foo[T](t: T)(implicit ev: ¬¬[T] <:< (Int ∨ String)): T = t
```

よし、記号コワクナイ。

## 仕上げその２：Context Bound
Scalaでは型パラメータをimplicitで使っている場合にContext Boundと呼ばれる別の書き方が出来る。
例えば、

```scala
def sorted[T](implicit o: math.Ordering[T])
```

これは以下のように書き換えることが可能だ。

```scala
def sorted[T : math.Ordering]
```

最後に行う仕上げは先程のfoo関数をContext Boundで書きなおすというものだ。
但し、Orderingのように話は単純ではない。
単にimplicit部をTの横に持っていってもコンパイルエラーとなる。

```scala
def foo[T : ¬¬ <:< (Int ∨ String)](t: T): T = t // error: <:<[<error>,<error>] does not take type parameters
```

上のsortedの例のように、 ```[T : math.Ordering]``` と書くと ```implicit evidence$1: math.Ordering[T]``` というようにimplicitで書いたのと同じように変換されており、このfooの書き方では確かにうまく変換できないだろう事は容易に想像がつく。

```T : ``` の右側にはTを取り得る型を１つ宣言するだけ、としないといけない。
この制約を突破するためにScalaでよく使われるテクがこのような書き方。

```scala
type |∨|[T, U] = {
  type λ[X] = ¬¬[X] <:< (T ∨ U)
}

def foo[T : (Int |∨| String)#λ](t: T): T = t
```

これで完成。

### #ってなんだよ？
以下のように、class A内部に定義されたclass Bを指す時に使われる。

```scala
class A {
  class B(val n: Int)
}

def foo(b: A#B): Int = b.n
```

今回の場合は、 ```|∨|```の内部に定義された ```λ``` を指している。
よく見ると ```λ``` は型パラメータを１つだけ取るよう宣言されており 、要は ```[T : math.Ordering]``` と同じ表現になっている事がわかる。
しかも、 ```|∨|``` は型パラメータを２つ取るように宣言されており、 ```λ``` を指定する時に２つの型の定義も兼ねている。確かにこの書き方なら文法エラーにはならないだろう。

しかしまぁよく思いつくもんだ。

というわけで以上、完全に終わり。

# 終わりに
厳密には前回の記事はIntもしくはStringもしくはBooleanという３つのORだったわけだがそれをやろうとするとOR3[T,U,V]とでも定義しないと出来ない…？