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の勉強会が開催されています.¹

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

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

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

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は定義してくれています．

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
百聞は一見に如かずということで，実際のコード例を見てみましょう.

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とは以下で定義されています．

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

MkMonoidとは何でしょうか．

trait MkMonoid[T] extends Monoid[T]

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

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

MkMonoidDefivationの定義に戻ります．

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の導出に関係しそうなのはこの辺りです．

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から参照していますが，alleycatsはcatsの方に統合されたようですね．
MkEmpty1の中でOrderと関連するHListのMkEmptyのInstanceを導出しています．
mkEmptyGenericで使われている Generic.Aux[T, R]は今の場合だとGeneric.Aux[Order, Double::Double::HNil]でこれはshepelessがMacroを使って生成しています．

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> 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> 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を導出するために必要なパーツが全て揃いました．

まとめ

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

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

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

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

私は参加していませんが... ↩
todoの内容は把握してません... ↩
HaskellのようなMonadの自動導出は難しいのかな ↩