Generic 型の分類（モナド、ファンクタの解説）Scala 版

最近 Extensible Effects というものについて勉強しており、そのことを Qiita に書きたいんだが、その前提となる知識として、Generic 型とその分類をまとめておく。

Generic型

型パラメータ A に対し、何らかの性質を付加した型のことを Generic 型と呼ぶ。
「何らかの性質」というのは大変曖昧だが曖昧ゆえにいろんなものを内包している。具体的には、

List[A]                          // A 型のリスト
Future[A]                        // 将来 A 型の値を保持する何らかの処理
Option[A]                        // A 型の値を保持または何も保持していない状態を表す型
type Pair[A] = (A, A)            // A 型 の値のペア
type Const[A] = Unit             // （型 A に依らず） 常に同じ値を持つ型
type Reader[E, A] = E => A       // E 型の値を受け取り A 型の値を返す関数
type AtoX[A, X] = A => X         // A 型 の値を受け取り X 型の値を返す関数
type Cont[A, R] = (A => R) => R  // A 型 の値を受け取り R 型の値を返す関数 を受け取り R 型の値を返す関数
type Catch[A, X, Y] = ((A => X) => Y) => Option[A] // A 型 の値を受け取り X 型の値を返す関数 を受け取り Y 型の値を返す関数 を受け取り Option[A] 型の値 を返す関数

などなど。 A に注目して Generic 型と言うときには、A 以外の型パラメータ E, R, X, Y は何か特定の型（Int や String など）に固定されていると思ってほしい。

（なお最後の例 Catch はこちらの記事を参考にした）

Functor

Generic 型のうち、次の map という関数が定義でき、以下の性質を満たすものを Functor と呼ぶ。圏論の Functor（関手）から来ている。

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

// 性質
// 任意の functor: Functor[F[_]], fa: F[A], f: A => B 及び g: B => C について、
functor.map(functor.map(fa)(f))(g) == functor.map(fa)(f andThen g)

上で挙げた Generic 型のうち、 AtoX[A, X] と Catch[A, X, Y] 以外は Functor でもある。
例えば、

implicit val pairFunctor = new Functor[Pair] {
  def map[A, B](pair: Pair[A])(f: A => B): Pair[B] = pair match {
    case (a1, a2) => (f(a1), f(a2))
  }
}

と言った具合に定義することが出来る。この implicit はどこか別のところで、 Generic 型が実は Functor であるという制約がほしい時に使われる：

def print[F[_], A](fa: F[A])(implicit functor: Functor[F]): Unit = {
  functor.map(fa)(println)
}

print((1, 2): Pair[Int])
// 1
// 2

Monad

Functor のうち、pure flatMap という関数が定義でき、以下の性質を満たすものを Monad と呼ぶ。同じく圏論の Monad から来ている。

trait Monad[M[_]] {
  def pure[A](a: A): M[A]
  def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B]
}

// 性質
// (1) 任意の monad: Monad[M[_]], a: A, f: A => M[B] について、
monad.flatMap(Monad.pure(a))(f) == f(a)

// (2) 任意の monad: Monad[M[_]], ma: M[A] について、
monad.flatMap(ma)(monad.pure) == ma

// (3) 任意の monad: Monad[M[_]], ma: M[A], f: A => M[B], g: B => M[C] について、
monad.flatMap(monad.flatMap(ma)(f))(g) ==
  monad.flatMap(ma)(a => moand.flatMap(f(a))(g))

上に挙げた Generic 型のうち、 Pair[A] は Functor だが Monad でない。
Const[A] は微妙なところで、例えば

implicit val constMonad = new Monad[Const] {
  def pure[A](a: A): Const[A] = ()
  def flatMap[A, B](ma: Const[A])(f: A => Const[B]): Const[B] = ()
}

と定義すれば性質 (1) 〜 (3) を満たすが、実は (1) の左辺は関数 f を実行していないのに対し右辺は実行している。f が "純粋" である限りこれはモナドと言えるが、そうでない場合（例えば内部で println を使っていたり例外が発生したり）はモナドと言って良いか微妙なところだ。誰か詳しい方居たら教えてください m(__)m

まとめ

まとめると、先に上げた Generic 型は次のように分類出来る。

型	Generic	Functor	Monad
List[A]	o	o	o
Future[A]	o	o	o
Option[A]	o	o	o
Pair[A] = (A, A)	o	o	x
Const[A] = Unit	o	o	?
Reader[E, A] = E => A	o	o	o
AtoX[A, X] = A => X	o	x	x
Cont[A, R] = (A => R) => R	o	o	o
Catch[A, X, Y] = ((A => X) => Y) => Option[A]	o	x	x

Extensible Effects とは？

複数の Generic 型 を合成して Monad にしてしまう仕組み。
Monad の合成は「モナド変換子」と呼ばれるものがあるんだが、こいつの抱えるいくつかの問題（入れ子にしたモナドの奥深くの値を取り出すのが骨、とか）を解決してくれるだけでなく、 Monad とは限らない Functor や Generic 型もうまいことモナドにして合成してくれる。これには自由モナド（Free Monad）とかむっちゃ自由モナド（Free-er Monad） とかを定義するんだが、長くなったので別記事に（そのうち）まとめる。詳しく知りたい方は下記リンク先がめちゃくちゃ分かり易いのでご参照ください。

Extensible Effects in Scala
Free モナド → Free-er モナド → Extensible Effects の流れが大変わかりやすくまとまっていて、勉強になりました。ただちょっとソースコードに若干のミスがあるっぽいのでこれも別記事で解説します。

Extensible Effects はモナド変換子に対する救世主になり得るか？
Extensible Effects がモナド変換子に比べてどういった利点があるか、といったことが詳しくまとめられています。こちらも大変参考になりました。