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

はじめに

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

概要

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

Example: collapsing a list

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)

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

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は代数学の概念。
簡単に言えば二項演算子で閉じた集合に結合律と単位元がひっついたもの。

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

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

Type classes vs. subtyping

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

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

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

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

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

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

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になっていると嬉しい。
とりあえず実装してみる。

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]から推論できる。

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を自動で取得できる。

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にできる。

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を適用できる。

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)