(もりそば)Scalaによる高階型変数 - Higher-kind Generics

「ハイヤーーーーーッッ！！！」

と気合いを入れたところで、今日はScalaのコレクションライブラリで多用されている、Higher kind genericsについて軽く解説したいと思いハイヤーーーーーッッ！！！

Higher-kind Generics(type constructor parameter)って?

まぁぶっちゃけ@kmizu が解説してくれてるのでコレ読んでもらえばおけです。

ScalaのHigher-kind Genericsについて - Togetter

そういえば最近Javaでもid:Nagiseによるこんな話がありましたね。

Javaによる高階型変数の実装 - プログラマーの脳みそ
Java による高階型変数と Scala とジェネリクス - Togetter

要は、型パラメータを取る型パラメータ(?)が使えるよって話。

trait AttrHelper[+Holder[X]]

とあったときに、Holderってのは型パラメータで、そいつは更にXという型パラメータをとるなんらか、という用に定義できるんだなぁ。

ちなみにHigher-kind Genericsってのは水島さんが命名した名前で、とぅぎゃったーにあるとおり言語仕様書では"type constructor parameter"というようです。

"3.3.3 TypeConstructors"と"4.4 Type Parameters"、ChangeLogの"Changes in Version 2.5 (02-May-2007) Type constructor polymorphism"あたりを見るとよいでしょう。

http://www.scala-lang.org/sites/default/files/linuxsoft_archives/docu/files/ScalaReference.pdf:Scala Language Specification

型コンストラクタを型パラメータに取る例

論よりコード。例を見ます。

// 型コンストラクタ
type IntMap[A] = scala.collection.immutable.Map[Int, A]
type StringMap[A] = scala.collection.immutable.Map[String, A]

// ある型のMapにproxyするtrait
trait MapProxy[A,B, ReprMap[B] <: Map[A,B]] {
  val underlying:ReprMap[B]
}

IntMap, StringMapのふたつの型を定義しました。どちらも、Aという型パラメータを取ってMap[Int, A]とかMap[String, A]とかいう"型"を返す型コンストラクタです。

で、この型コンストラクタを型パラメータReprMapで取る、MapProxyというtraitを定義しました。
こいつは、MapのKeyの型A、値の型Bと、ProxyするMapの型を返す型コンストラクタReprMapを型パラメータでもらいます。underlying は、Proxyする対象となる実際のMap型の変数です。

このtraitを使うクラスは、こんな風に書けます。以下は、String型のKeyをもつMapへproxyするクラスと、Int型のKeyを持つMapへproxyするクラスです。

class StringMapProxy[A](elems:(String, A)*) extends MapProxy[String, A, StringMap]{
  val underlying:StringMap[A] = Map(elems:_*)
  def apply(key:String):A = underlying(key)
}

class IntMapProxy[A](elems:(Int, A)*) extends MapProxy[Int, A, IntMap]{
  val underlying:IntMap[A] = Map(elems:_*)
  def apply(key:Int):A = underlying(key)
}

実際に使ってみます。

scala> val ssm = new StringMapProxy("foo"->"bar","hoge"->"fuga")
ssm: StringMapProxy[java.lang.String] = StringMapProxy@199ec67

scala> ssm.underlying
res9: StringMap[java.lang.String] = Map(foo -> bar, hoge -> fuga)

scala> ssm("foo")
res10: java.lang.String = bar

scala> val sim = new StringMapProxy("foo"->1,"hoge"-> 2)
sim: StringMapProxy[Int] = StringMapProxy@741bb804

scala> sim.underlying
res11: StringMap[Int] = Map(foo -> 1, hoge -> 2)

scala> val ibm = new IntMapProxy( 1 -> true, 2 -> false)
ibm: IntMapProxy[Boolean] = IntMapProxy@785850e3

scala> ibm.underlying
res12: IntMap[Boolean] = Map(1 -> true, 2 -> false)

scala> ibm(1)
res13: Boolean = true

StringMapProxy, IntMapProxyともに、proxyするMapの型が型パラメータReprMapで与えた型になっていることがわかると思います。

scala.collectionパッケージでの利用例

scala.collectionパッケージでの利用例を見てます。
以下は、GenericCompanionの定義です。こいつは、型に応じたBuilderを返すためのコンパニオンで、CanBuildFromとかを型に合わせていい感じにimplicit conversionする、2.8のコレクションライブラリのキモッ!となる抽象クラスです。

// CCは型Xを取ってTraversable[X]以下の型を返す型コンストラクタ
abstract class GenericCompanion[+CC[X] <: Traversable[X]]

// Traversableを生成する抽象クラス
// GenericCompanionを継承してる。
abstract class TraversableFactory[CC[X] <: Traversable[X] with GenericTraversableTemplate[X, CC]] extends GenericCompanion[CC] 

// 実際のTraversableの定義。ここでCCはTraversableになってる
object Traversable extends TraversableFactory[Traversable] {
  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, Traversable[A]] = new GenericCanBuildFrom[A]
  def newBuilder[A]: Builder[A, Traversable[A]] = new mutable.ListBuffer
}

実践的な例:特定の型のIterableへProxyするクラス

まぁコードと利用例見てください。Iterableをproxyしつつ、mapやfilterしたときに、Traversableとかじゃなく自分の型を返すようにするためのtraitです。

import scala.collection.{Iterable, IterableLike}
trait TypedIterableProxy[A, Repr<: Iterable[A]] extends Iterable[A] with IterableLike[A, Repr]{
  import scala.collection.generic.CanBuildFrom
  import scala.collection.mutable.{ListBuffer, Builder}
  val self:Iterable[A]
  def newTo(from:Iterable[A]):Repr

  def iterator = self.iterator
  override def newBuilder:Builder[A, Repr] = new ListBuffer[A] mapResult {x => newTo(x) }
  implicit def canBuildFrom: CanBuildFrom[Repr, A, Repr] = new CanBuildFrom[Repr, A, Repr] {
    def apply(from: Repr):Builder[A, Repr] = newBuilder
    def apply() = newBuilder
  }
}

// 特定の型のIterableへProxyするクラス
class StringItrableProxy(v:String*) extends Iterable[String] with TypedIterableProxy[String, StringItrableProxy] {
  val self= v.toIterable
  def newTo(from:Iterable[String]) = new StringItrableProxy( from.toSeq:_*)
  def hoge = map{ "hoge" + }
}

scala> val StringItrableProxy = new StringItrableProxy("aa", "bb", "cc", "abc")
StringItrableProxy: StringItrableProxy = line56(aa, bb, cc, abc)

scala> StringItrableProxy.filter{_.startsWith("a")}
res8: StringItrableProxy = line56(aa, abc)