ScalaでEitherの実装に見る、反変の反変？

## はじまり
※関数型言語の概念等はまだ慣れていない部分が多分にあるので、間違っていたら申し訳ないです。

関数型言語のお勉強のために、Scalaで自前のEither型を実装していた時のこと。色々と調べながら`map`と`flatMap`を実装しました。

```scala
object My {
  sealed trait Either[+E, +A] {
    def map[B](f: A => B): Either[E, B] = this match {
      case Right(value) => Right(f(value))
      case Left(error) => Left(error)
    }

    def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] = this match {
      case Right(value) => f(value)
      case Left(error) => Left(error)
    }

  case class Left[+E](error: E) extends Either[E, Nothing]
  case class Right[+A](val value: A) extends Either[Nothing, A]
}
```

コンパイラを通そうとすると、`map`はともかく、`flatMap`では`EE >: E`が必要なことに気づきます。最初は

```scala
def flatMap[B](f: A => Either[E, B]): Either[E, B] = this match {
  case Right(value) => f(value)
  case Left(error) => Left(error)
}
```
でいいのかなと思っていたのですが

```text
error: covariant type E occurs in contravariant position in type A => My.Either[E,B] of value f
          def flatMap[B](f: A=>Either[E,B]):Either[E,B] = this match {
                         ^
```
という具合に怒られてしまいました。結局`EE >: E`が必要だと分かったのですが、これを入れる理由が直感的に理解できなかったので、調べてまとめました。

## 再確認（共変・反変・非変etc）
すごくざっくりした事前知識を書いておきます。

Scalaにおける部分型は、`A <: B`または`B >: A`と書いて表します。この例では、AはBの部分型ということになります。部分型とは、要するに継承関係にあって、メソッドとか振る舞いが増え＆特化されているという意味。気持ちとしては`String <: Object`とか`Integer <: Number`とか、そんなイメージ。

型パラメータを持つ型C[T]について、`A <: B`である型`A`, `B`があって

- `C[A] <: C[B]`が成り立つとき、共変
- `C[A] >: C[B]`が成り立つとき、反変
- どちらでもないとき、非変

というらしいです。成り立つというのは、その型の変数に代入できる、と言い換えてもよさげ。これらの性質を型パラメータの前に`+`、`-`を付けて表します。Eitherが`Either[+E, +A]`で宣言されているのも、`E`と`A`が共変であるという指定です。

## ネストした場合の共変・反変
まず注意が必要なのは、Scalaにおける1引数関数は`Function1[-T, +R]`になるので、全ての引数は反変、戻り値は共変として扱われるという点です。

```scala
class M
class N extends M
class X
class Y extends X

val a: M => Y = _ => ......
val b: N => X = a
```
`b`は`N => X`なので、引数として`N`に適用できる関数を要求していますが、当然`N`のスーパークラスを受け入れられる関数ならば、`N`にも適用できるはず、というのが、ここに反変が来る直感的な意味だと思っています。同様に、`b`は適用後`X`になることを要求していますが、`Y`は継承関係にあるので常に`X`でもあります。だから型としては問題ないのです。

ややこしいのが、この関係がネストした場合です。`map`や`flatMap`は引数として関数`f`を取るようになっています。このとき、一体何が起きるのか……？

単純化した、こんな例で考えました。この代入は成功します。

```scala
class T
val c: (N => X) => T = _ => .......
val d: (M => Y) => T = c
```
この代入が型的に問題ないのかは、どちらも`Function1`型の引数部分が異なるので、そこについて反変`(N => X) >: (M => Y)`が成り立つかにかかっています。`Function1`の型パラメータから、この部分型関係は`N <: M`かつ`X >: Y`が成り立っていることが成立条件です。つまり、問題ないので代入は成功する、ということです。

まとめると、ネストした関数のいわゆる関数引数部分を再帰的にたぐっていくごとに、反変関係によって要求される部分型関係は反転する、ということのようです。

## 本題
以上の前提のもとで、`flatMap`についても再考します。

`flatMap`は`(A => Either[E, B]) => Either[E, B]`です。このうち`A => Either[E, B]`の部分は反変です。`A`は反変の中の反変なので、共変です。`A`は大丈夫。

一方、左の`Either[E, B]`は、反変の中にある共変の位置にあるので、結局反変関係を満たさなければならない……のですが、`Either[E, B]`のうち`E`は既にクラスの型パラメータで`+E`と共変宣言してしまっているので、型が合わないというわけです。

したがって、`E`については反変になるような制約を与えなければ型的におかしいことになります。そこで`EE >: E`なる上位型である`EE`を導入して、`E`の代わりに与えるということのようです。

## まとめ
- 反変の反変の位置にある型変数は、共変であることが要求される
- コンパイラに怒られたら、適切な制約付きの型変数を導入してやること

たぶん……この理解でいいはず……。力尽きたので記事はここまで。関数型言語は奥が深いですね。

## 参考
- [Scala関数型デザイン&プログラミング ―Scalazコントリビューターによる関数型徹底ガイド (impress top gear)](http://www.amazon.co.jp/dp/4844337769)
- Stack Overflowに[同様の質問](http://stackoverflow.com/questions/23409037/different-contravariance-requirement-for-map-flatmap)が投稿されていました