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

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

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

```scala
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` は[こちらの記事](http://math.andrej.com/2008/11/17/not-all-computational-effects-are-monads/)を参考にした）

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

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

```scala
// 性質
// 任意の 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` でもある。
例えば、

```scala
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 であるという制約がほしい時に使われる：

```scala
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` から来ている。

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

```scala
// 性質
// (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](http://halcat.org/scala/extensible/)
Free モナド → Free-er モナド → Extensible Effects の流れが大変わかりやすくまとまっていて、勉強になりました。ただちょっとソースコードに若干のミスがあるっぽいのでこれも別記事で解説します。

[Extensible Effects はモナド変換子に対する救世主になり得るか？](http://konn-san.com/prog/haskell/extensible-effects.html)
Extensible Effects がモナド変換子に比べてどういった利点があるか、といったことが詳しくまとめられています。こちらも大変参考になりました。