ScalaライブラリCatsの型クラスの例意訳

## はじめに
型クラスの勉強でCatsの例が面白かったのでまとめ。

https://typelevel.org/cats/typeclasses.html

## 概要
- 型クラスはアドホック多相を実現する
    - アドホック多相はオーバーロードのこと
- オブジェクト指向ではサブ型を利用してポリモーフィズムを実現する
- 一方関数型ではジェネリクスのようなパラメトリック多相とアドホック多相を利用

## Example: collapsing a list

```scala
def sumInts(list: List[Int]): Int = list.foldRight(0)(_ + _)

def concatStrings(list: List[String]): String = list.foldRight("")(_ ++ _)

def unionSets[A](list: List[Set[A]]): Set[A] = list.foldRight(Set.empty[A])(_ union _)
```

このコードはintのリストの合計、stringのリストの結合、setのリストの和を実行する。
共通点として

- 初期値の存在(0, 空文字列, 空集合)
- 結合関数(+, ++, union)

がある。
様々な型に対しての重複実装を避けるために抽象化する。

```scala
trait Monoid[A] {
  def empty: A
  def combine(x: A, y: A): A
}

// Int型への実装
val intAdditionMonoid: Monoid[Int] = new Monoid[Int] {
  def empty: Int = 0
  def combine(x: Int, y: Int): Int = x + y
}
```

ちなみにMonoidは代数学の概念。
簡単に言えば二項演算子で閉じた集合に結合律と単位元がひっついたもの。

上のインターフェースを利用すれば下のような関数が書ける。

```scala
// 任意のList[A]型に合計のような操作を行える
def combineAll[A](list: List[A], A: Monoid[A]): A = list.foldRight(A.empty)(A.combine)
```

## Type classes vs. subtyping
上の実装では実際にMonoidを引数として取る。
よくあるオブジェクト指向ではサブ型を利用する。

```scala
// サブ型
// AはMonoidalなため合計のような操作を実行できる
def combineAll[A <: Monoid[A]](list: List[A]): A = ???
```

AはMonoid[A]のサブ型だからemptyメソッドを呼べば適切に初期値を取得できる。
しかしもしlistが空のときはemptyを呼ぶべきオブジェクトが見当たらないため`empty`な値を取得できない。
そもそもstaticでないオブジェクトから定数を取得するのもなんか気持ち悪い。

もう一個面白い例を考えてみる。

```scala
final case class Pair[A, B](first: A, second: B)
```

`Monoid[Pair[A, B]]`が定義できるかどうかは`Monoid[A]`と`Monoid[B]`が定義できるかにかかっている。
すなわち１つ目のペアの第一要素が２つ目のペアの第一要素と結合できるか。
第二要素についても同様。
サブ型で実装すると以下のような感じ。

```scala
final case class Pair[A <: Monoid[A], B <: Monoid[B]](first: A, second: B) extends Monoid[Pair[A, B]] {
  def empty: Pair[A, B] = ???

  def combine(x: Pair[A, B], y: Pair[A, B]): Pair[A, B] = ???
}
```

なんか汚い。
それにPairはどんな要素でもcarryしたいのにPairをMonoidにしたいがためにMonoidしか要素として持てなくなっている。
理想はMonoidを要素として持っているときだけMonoidになっていると嬉しい。
とりあえず実装してみる。

```scala
final case class Pair[A, B](first: A, second: B) extends Monoid[Pair[A, B]] {
  def empty(implicit eva: A <:< Monoid[A], evb: B <:< Monoid[B]): Pair[A, B] = ???

  def combine(x: Pair[A, B], y: Pair[A, B])(implicit eva: A <:< Monoid[A], evb: B <:< Monoid[B]): Pair[A, B] = ???
}
// <console>:15: error: class Pair needs to be abstract, since:
// it has 2 unimplemented members.
// /** As seen from class Pair, the missing signatures are as follows.
//  *  For convenience, these are usable as stub implementations.
//  */
//   def combine(x: Pair[A,B],y: Pair[A,B]): Pair[A,B] = ???
//   def empty: Pair[A,B] = ???
// 
//        final case class Pair[A, B](first: A, second: B) extends Monoid[Pair[A, B]] {
//                         ^
```

しかしimplicit制約のせいでMonoidのinterfaceに適合せずにコンパイルエラー。

## Implicit derivation
`Monoid[Pair[A, B]]`は`Monoid[A]`と`Monoid[B]`から推論できる。

```scala
final case class Pair[A, B](first: A, second: B)

def deriveMonoidPair[A, B](A: Monoid[A], B: Monoid[B]): Monoid[Pair[A, B]] =
  new Monoid[Pair[A, B]] {
    def empty: Pair[A, B] = Pair(A.empty, B.empty)

    def combine(x: Pair[A, B], y: Pair[A, B]): Pair[A, B] =
      Pair(A.combine(x.first, y.first), B.combine(x.second, y.second))
  }
```

でも実はScalaのimplicitを使えば必要に応じて各Monoidを自動で取得できる。

```scala
object Demo { // needed for tut, irrelevant to demonstration
  final case class Pair[A, B](first: A, second: B)

  object Pair {
    implicit def tuple2Instance[A, B](implicit A: Monoid[A], B: Monoid[B]): Monoid[Pair[A, B]] =
      new Monoid[Pair[A, B]] {
        def empty: Pair[A, B] = Pair(A.empty, B.empty)

        def combine(x: Pair[A, B], y: Pair[A, B]): Pair[A, B] =
          Pair(A.combine(x.first, y.first), B.combine(x.second, y.second))
      }
  }
}
```

またMonoid制約を持つどんな関数もimplicitな引数として制約を表現できるし、どんな型クラスもimplicitにできる。

```scala
implicit val intAdditionMonoid: Monoid[Int] = new Monoid[Int] {
  def empty: Int = 0
  def combine(x: Int, y: Int): Int = x + y
}

def combineAll[A](list: List[A])(implicit A: Monoid[A]): A = list.foldRight(A.empty)(A.combine)
```

こうしてMonidalな型のPairにcombineAllを適用できる。

```scala
implicit val stringMonoid: Monoid[String] = new Monoid[String] {
  def empty: String = ""
  def combine(x: String, y: String): String = x ++ y
}

import Demo.{Pair => Paired}
// import Demo.{Pair=>Paired}

combineAll(List(Paired(1, "hello"), Paired(2, " "), Paired(3, "world")))
// res2: Demo.Pair[Int,String] = Pair(6,hello world)
```