shapeless - TypeClass

代数的データ型が持ってる型から型クラスのインスタンスを自動導出して、scala.math.Orderingを適用できるようにしてみる。Orderingは型クラスなのでscala本体に定義してある型クラスのインスタンスをそのまま使う。

まずGenericやHList知らない方はコレを読もう。

shapelessのGenericを使ってHListかCoproductに変換して、先頭から一つずつscala.math.Orderingの型インスタンスを取得してcompareしていく。同じじゃなくなるまでcompareする。

Genericを直接使わずTypeClassを使うと少しシンプルに書ける。TypeClassを継承して、GenericでHListかCoproductに変換した後に処理する関数を定義する。

コード

import shapeless._

object OrderingDerive extends TypeClassCompanion[Ordering] {

  object typeClass extends TypeClass[Ordering] {

    override def coproduct[L, R <: Coproduct](cl: => Ordering[L], cr: => Ordering[R]): Ordering[L :+: R] =
      new Ordering[L :+: R] {
        def compare(a1: L :+: R, a2: L :+: R) =
          (a1, a2) match {
            case (Inl(l1), Inl(l2)) => cl.compare(l1, l2)
            case (Inr(r1), Inr(r2)) => cr.compare(r1, r2)
            case (Inl(_), Inr(_)) => -1
            case (Inr(_), Inl(_)) => 1
          }
      }

    override def emptyCoproduct: Ordering[CNil] =
      new Ordering[CNil] {
        def compare(a1: CNil, a2: CNil) = 0
      }

    override def product[H, T <: HList](ch: Ordering[H], ct: Ordering[T]): Ordering[H :: T] =
      new Ordering[H :: T] {
        def compare(a1: H :: T, a2: H :: T) = ch.compare(a1.head, a2.head) match {
          case 0 => ct.compare(a1.tail, a2.tail)
          case a => a
        }
      }

    override def emptyProduct: Ordering[HNil] =
      new Ordering[HNil] {
        def compare(a1: HNil, a2: HNil) = 0
      }

    override def project[F, G](instance: => Ordering[G], to: F => G, from: G => F): Ordering[F] =
      new Ordering[F] {
        def compare(a1: F, a2: F) = instance.compare(to(a1), to(a2))
      }
  }
}

全部の型でcompare使えるように。

implicit class ToComparable[A](val a1: A) {
  def compare(a2: A)(implicit ord: Ordering[A]): Int = ord.compare(a1, a2)
}

試す

Versionを表した型

case class Version(major: Int, middle: Int, minor: Int)

import OrderingDerive._

scala> Version(1,0,0) compare Version(1,0,1)
res74: Int = -1

scala> Version(1,0,0) compare Version(1,0,0)
res75: Int = 0

scala> Version(1,1,0) compare Version(1,0,0)
res76: Int = 1

Treeを表した型

sealed trait Tree[T]
case class Leaf[T](t: T) extends Tree[T]
case class Node[T](l: Tree[T], r: Tree[T]) extends Tree[T]

scala> def node[A](a: A, b: A): Tree[A] = Node(Leaf(a), Leaf(b))
//node: [A](a: A, b: A)Tree[A]

scala> node(1, 2) compare node(1, 3)
//res91: Int = -1

scala> node(1, 2) compare node(1, 2)
//res92: Int = 0

scala> node(1, 3) compare node(1, 2)
//res93: Int = 1

scala> Leaf(1) compare Leaf(2)
//res94: Int = -1

あってる。はず。
いやしかしGenericすごい。