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

はじまり

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

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

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が必要なことに気づきます。最初は

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

でいいのかなと思っていたのですが

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]になるので、全ての引数は反変、戻り値は共変として扱われるという点です。

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を取るようになっています。このとき、一体何が起きるのか……？

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

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)
Stack Overflowに同様の質問が投稿されていました