case classのMonoid Instanceを自動導出する

# tl;dr

* HaskellのようにADTのMonoid Instanceを自動導出したい
* アイディアの理解にはこれを読んで (https://typelevel.org/blog/2013/06/24/deriving-instances-1.html)
* kittens (https://github.com/milessabin/kittens) というライブラリを使う

# はじめに
最近部署内でこれ (https://underscore.io/books/scala-with-cats/) をテキストとしてcatsの勉強会が開催されています.[^1]
[^1]: 私は参加していませんが...

演習問題として以下のcase classのMonoid Instanceを作成するというものがあったようです.

```scala
case class Order(totalCost: Double, quantity: Double)
```

素直な解答は以下のようになるかと思います.

```scala
implicit val OrderMonoid = new Monoid[Order] {
  override def empty: Order = Order(0d, 0d)
  override def combine(x: Order, y: Order): Order = Order(x.totalCost + y.totalCost, x.quantity + y.quantity)
}
```

しかし， それぞれの要素`totalCost`と`quantity`には単元が`0d`，結合演算が`+`であるMonoid Instanceが既に用意されています．
その場合，catsに`Order`型のMonoid Instanceを自動で導出して欲しいと思いませんか？

実際catsは，それぞれの要素の型のMonoid Instanceが定義されているTupleのMonoid Instanceは定義してくれています．

```scala
import cats._, cats.implicits._

(1.0, 2.0) |+| (0.0, 1.0)
// res0: (Double, Double) = (1.0,3.0)
```

case classの場合は残念ながらcatsのみの利用では不可能ですが，kittensというshaplessを利用したライブラリを使えば実現可能です.

# kittens
GitHub: https://github.com/milessabin/kittens
百聞は一見に如かずということで，実際のコード例を見てみましょう.

```scala
import cats._, cats.implicits._, cats.derived._

case class Order(totalCost: Double, quantity: Double)

implicit val orderMonoid: Monoid[Order] = {
  import auto.monoid._
  semi.monoid}

Order(1.0, 2.0) |+| Order(0.0, 1.0)
// res0: Order = Order(1.0,3.0)
```

これだけです！
一体どのように実現されているのでしょうか．
なお自動導出の仕組みのアイディアそのものは全部これが説明してくれますので一読をオススメします．
http://typelevel.org/blog/2013/06/24/deriving-instances-1.html

以下前提条件としてshapelessが`Order`のような直積形式のcase classをHListに相互変換できるということを覚えておいてください．
今回の場合は`Order` <=> `Double::Double::HNil`ですね.


では実際中身を見ていきます. kittensのソースのコミットハッシュは1ac9fe32dd06d722aedb80011439d1bae4024922を参照してます．
まず`semi.monoid`とは以下で定義されています．

```scala
object semi {
  def monoid[T](implicit T: MkMonoid[T]): Monoid[T] = T
}
```

`MkMonoid`とは何でしょうか．

```scala
trait MkMonoid[T] extends Monoid[T]
```

catsのMonoidを継承しているだけのtraitですね．
さて，implicitなMkMonoidは`import auto.monoid._`にて提供されていそうです.
関係しそうなものは以下ですね． [^2]

```scala
object auto {
  object monoid extends MkMonoidDerivation //todo the regular approach doesn't work for monoid
}
```

[^2]: todoの内容は把握してません...

MkMonoidDefivationの定義に戻ります．

```scala
object MkMonoid extends MkMonoidDerivation {
  def apply[T](implicit m: MkMonoid[T]): MkMonoid[T] = m
}

private[derived] abstract class MkMonoidDerivation {
  implicit def mkMonoidAlgebraic[T](implicit e: Lazy[MkEmpty[T]], sg: Lazy[MkSemigroup[T]])
    : MkMonoid[T] = new MkMonoid[T] {
      def empty = e.value.empty
      def combine(x: T, y: T) = sg.value.combine(x, y)
    }
}
```

`Lazy`は恐らく遅延評価関連でしょう，全体の仕組みの理解のためには脇に置いておきます.
`MkEmpty`と`MkSemigroup`のInstanceから`MkMonoid`のInstanceを導出してくれるみたいですね.

`MkEmpty`の導出に関係しそうなのはこの辺りです．

```scala
trait MkEmpty[T] extends Empty[T]

object MkEmpty extends MkEmptyDerivation {
  def apply[T](implicit e: MkEmpty[T]): MkEmpty[T] = e
}

private[derived] abstract class  MkEmptyDerivation extends MkEmpty1 {
  implicit val mkEmptyHnil: MkEmpty[HNil] =
    new MkEmpty[HNil] {
      def empty = HNil
    }

  implicit def mkEmptyHconsAvailableInstance[H, T <: HList](implicit eh: Lazy[Empty[H]], et: MkEmpty[T])
    : MkEmpty[H :: T] = mkEmptyHcons(eh.value, et)
}

private[derived] abstract class MkEmpty1 {
  implicit def mkEmptyHconsFurtherDerive[H, T <: HList](implicit eh: Lazy[MkEmpty[H]], et: MkEmpty[T])
  : MkEmpty[H :: T] = mkEmptyHcons(eh.value, et)

  protected def mkEmptyHcons[H, T <: HList](eh: Empty[H], et: MkEmpty[T])
  : MkEmpty[H :: T] = new MkEmpty[H :: T] {
    val empty = eh.empty :: et.empty
  }

  implicit def mkEmptyGeneric[T, R](implicit gen: Generic.Aux[T, R], er: Lazy[MkEmpty[R]])
    : MkEmpty[T] = new MkEmpty[T] {
      val empty = gen.from(er.value.empty)
    }
}
```

`Empty`はkittens 1.0.0-RC3では[alleycats](https://github.com/non/alleycats)から参照していますが，alleycatsはcatsの方に統合されたようですね．
`MkEmpty1`の中でOrderと関連するHListの`MkEmpty`のInstanceを導出しています．
`mkEmptyGeneric`で使われている `Generic.Aux[T, R]`は今の場合だと`Generic.Aux[Order, Double::Double::HNil]`でこれはshepelessがMacroを使って生成しています．

```scala
scala> implicitly[Generic.Aux[Order, Double::Double::HNil]]
res0: shapeless.Generic.Aux[Order,Double :: Double :: shapeless.HNil] = anon$macro$73$1@5db4cc3a
```

ちゃんと存在しますね．
これが`from`でHList => Order，`to`でOrder => HListの変換を実施しています．

`mkEmptyHconsFurtherDerive`でHNilから一つずつ要素をconsした型のMkEmptyを順次導出してくれているようです．

```scala
scala> implicitly[MkEmpty[HNil]]
res0: cats.derived.MkEmpty[shapeless.HNil] = cats.derived.MkEmptyDerivation$$anon$1@649f3e46

scala> implicitly[MkEmpty[Double::HNil]]
res1: cats.derived.MkEmpty[Double :: shapeless.HNil] = cats.derived.MkEmptyDerivation$$anon$1@3e44eb95

scala> implicitly[MkEmpty[Double::Double::HNil]]
res2: cats.derived.MkEmpty[Double :: Double :: shapeless.HNil] = cats.derived.MkEmptyDerivation$$anon$1@6e38fc15

scala> implicitly[MkEmpty[Order]]
res3: cats.derived.MkEmpty[Order] = cats.derived.MkEmptyDerivation$$anon$2@42fa7621
```

ちゃんと全部導出されていますね．

同様にしてMkSemigroupのInstanceも導出されているのが確認できます．

```scala
scala> implicitly[MkSemigroup[HNil]]
res4: cats.derived.MkSemigroup[shapeless.HNil] = cats.derived.MkSemigroupDerivation$$anon$1@328a6fb1

scala> implicitly[MkSemigroup[Double::HNil]]
res5: cats.derived.MkSemigroup[Double :: shapeless.HNil] = cats.derived.MkSemigroupDerivation$$anon$2@7d772c64

scala> implicitly[MkSemigroup[Double::Double::HNil]]
res6: cats.derived.MkSemigroup[Double :: Double :: shapeless.HNil] = cats.derived.MkSemigroupDerivation$$anon$2@134fbecc

scala> implicitly[MkSemigroup[Order]]
res7: cats.derived.MkSemigroup[Order] = cats.derived.MkSemigroupDerivation$$anon$3@606c0be7
```

かくしてMkMonoidを導出するために必要なパーツが全て揃いました．

# まとめ
正直あまりまとまりのない文章でしたが，

1. shapelessにより case class <=> HListの相互変換のためのオブジェクトを作成
1. kittensがHListのMkEmptyとMkSemigroupのInstanceを導出する
1. kittensが上記Instanceからcase classのMkEmptyとMkSemigroupのInstanceを導出する
1. kittensが上記Instanceからcase classのMonoid Instanceを導出する

という流れが全てです.
kittensはMonoidだけでなく，FunctorのInstanceなども自動導出できるようです．[^3]

ここまで読んでいただきありがとうございました.

[^3]: HaskellのようなMonadの自動導出は難しいのかな