encoding data families by using dependent method types

gistfile1.scala

trait GMap[+V] {
  type P[+_]
  val content: P[V]
}
trait GMapKey[K] {
  type GM[+V] <: GMap[V]
  def empty[V]: GM[V]
  def lookup[V](k: K, m: GM[V]): Option[V]
  def insert[V](k: K, v: V, m: GM[V]): GM[V]
}

case class GMapInt[+V](
  override val content: Map[Int, V]
) extends GMap[V] {
  type P[+A] = Map[Int,A]
}
implicit object GMapKeyInt extends GMapKey[Int] {
  type GM[+V] = GMapInt[V]
  def empty[V] = GMapInt[V](Map())
  def lookup[V](k: Int, m: GMapInt[V]) = m.content.find{case (x, _) => k == x}.map(_._2)
  def insert[V](k: Int, v: V, m: GMapInt[V]) = GMapInt(m.content + (k -> v))
}

case class GMapUnit[+V](
  override val content: Option[V]
) extends GMap[V] {
  type P[+A] = Option[A]
}
implicit object GMapKeyUnit extends GMapKey[Unit] {
  type GM[+V] = GMapUnit[V]
  def empty[V] = GMapUnit[V](None)
  def lookup[V](k: Unit, m: GMapUnit[V]) = m.content
  def insert[V](k: Unit, v: V, m: GMapUnit[V]) = GMapUnit(Some(v))
}

object GMapPair {
  trait GMapPair[T[+_], +V] extends GMap[V] {
    type P[+A] = T[A]
    override def toString = "GMapPair(" + content.toString + ")"
  }
  def apply[A, B, V](
    a: GMapKey[A],
    b: GMapKey[B]
  )(m: a.GM[b.GM[V]]): GMapPair[({type X[+A]=a.GM[b.GM[A]]})#X, V] =
    new GMapPair[({type X[+A]=a.GM[b.GM[A]]})#X, V] {
      val content = m
    }
}
implicit def mkGMapKeyPair[A: GMapKey, B: GMapKey] = new GMapKey[(A, B)] {
  val (a, b) = (implicitly[GMapKey[A]], implicitly[GMapKey[B]])
  type GM[+V] = GMapPair.GMapPair[({type X[+A]=a.GM[b.GM[A]]})#X, V]
  def empty[V] = GMapPair[A, B, V](a, b)(a.empty)
  def lookup[V](p: (A, B), m: GM[V]) = for {
    x <- a.lookup(p._1, m.content)
    y <- b.lookup(p._2, x)
  } yield y
  def insert[V](p: (A, B), v: V, m: GM[V]) = {
    GMapPair[A, B, V](a, b){
      a.lookup(p._1, m.content) match {
        case None =>
          a.insert(p._1, b.insert(p._2, v, b.empty), m.content)
        case Some(m1) =>
          a.insert(p._1, b.insert(p._2, v, m1), m.content)
      }
    }
  }
}

def mkGMap[K: GMapKey, V](k: K, v: V): GMapKey[K]#GM[V] = {
  val gm = implicitly[GMapKey[K]]
  gm.insert(k, v, gm.empty)
}

def lookup[K: GMapKey, V](k: K, m: GMapKey[K]#GM[V]) = {
  val gm = implicitly[GMapKey[K]]
  gm.lookup(k, m.asInstanceOf[gm.GM[V]])
}


val m = mkGMap((1, (2, (3, ()))), 3)
println(lookup((1, (2, (3, ()))), m))

def mkGMapBug[K, V](k: K, v: V)(implicit gm: GMapKey[K]): gm.GM[V] = {
  gm.insert(k, v, gm.empty)
}

val m = mkGMapBug((1, (2, (3, ()))), 3)
println(lookup((1, (2, (3, ()))), m))