kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Stringを要素に持つ任意のコレクションにgrepを適用できるようにする - あるいはScalaの暗黒面について

2011/07/03:末尾に補足を追記しました。

id:xuwei さんのエントリから引用します。

最近ちょっとRubyやってたりします。で、RubyのEnumerableにgrepっていうメソッドがあるらしいけど、Scalaには直接対応するものがないので、かなり雑につくってみた

誰得？(・ω・｀)っていうか、ジェネリックにしようとしたら意外と難しくてできなかった*1んだけどどうやるの・・・Scala1年半以上やっててそんなこともできなくて死にたい orz


まず、 id:xuwei さんが、本来満たしたい仕様を実現するのはさほど簡単なことでもないので*1、特に気される必要は無いかと思います。


説明が長くなるので、先に結論から言うと次のコードで id:xuwei さんの要求を満たすことができます。


このコードは次のようにして使うことができます。


REPLの例を見ていただければわかるように、Stringを要素に持つ、List, Set, Vectorに対してgrepを適用することができて、各コレクションに対するgrepは同じ静的なコレクション型を返していることがわかります。

id:xuwei さんがどのようなアプローチを試みられたのかはわからないのですが、おそらく次のような感じだったのではないでしょうか。

import scala.collection.Traversable
import scala.collection.generic.CanBuildFrom
object PimpGrepToCollection {
  class GrepCallable[C[X] <: Traversable[X]](tr: C[String]){
    def grep[A](regex:String)(func:String => A = identity _)(implicit bf: CanBuildFrom[C[String], A, C[A]]):C[A] =
      tr.collect[A, C[A]]{
        case s if regex.r.findFirstIn(s).isDefined => func(s)
      }(bf)
  }
  implicit def toGrepCallable[C[X] <: Traversable[X]](tr: C[String]): GrepCallable[C] = new GrepCallable[C](tr)
}

しかし、このコードをコンパイルしてみようとすると、次のようなコンパイルエラーが出てしまいます。

error: type mismatch;
 found   : scala.collection.generic.CanBuildFrom[C[String],A,C[A]]
 required: scala.collection.generic.CanBuildFrom[Traversable[String],A,C[A]]
             }(bf)


この型エラーは、

CanBuildFrom[C[String],A,C[A]]

が

CanBuildFrom[Traversable[String],A,C[A]]

のサブタイプでないので、コンパイルできないよー、という事を言っています。


ここで問題なのは、何故、コンパイルできないか、ということです。それを理解するためには、

  1. Traversable#collectの宣言(シグニチャ)
  2. Scala/Java5以降における型チェックの手法

を知る必要があります。


まず最初の点について。Scala 2.9.0.1のAPIリファレンスから引用すると、collectのシグニチャは

def collect [B, That] (pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Traversable[A], B, That]): That

のようになっていることがわかります。


ここでのポイントは、Traversable型の定義時点で、既にCanBuildFromの最初の型パラメータがTraversable[A]になってしまっていることです。


次に2点目について。Scala/Java 5以降のジェネリクスでは、イレイジャという手法によって、コンパイル時に型パラメータ情報を消去します。そのため、型パラメータに対して何も制約を指定しない場合、Anyに定義されているメソッドしか呼び出すことができません。型パラメータAを型に持つ式xに対して必要なメソッドを適用できるようにするには、Aに対して適切な上限境界/下限境界を指定する必要があります。


上記の誤ったコード例では、

  class GrepCallable[C[X] <: Traversable[X]](tr: C[String]){
    def grep[A](regex:String)(func:String => A = identity _)(implicit bf: CanBuildFrom[C[String], A, C[A]]):C[A] =
      tr.collect[A, C[A]]{
        case s if regex.r.findFirstIn(s).isDefined => func(s)
      }(bf)
  }

のC[X] <: Traversable[X]の部分が該当します*2。


ここで、この宣言は、あるジェネリックな型コンストラクタCはTraversableを継承していなければいけない、ということを表現しています。


問題は、tr.collect()の呼び出しの型が一体何になるかということです。Cの上限境界の指定では、Traversableを継承しているということしか言っていませんから、tr.collect()を呼び出したときは、Traversable[String]#collectを呼び出したときと同じように型チェックされます。


再びTraversable[A]#collectの宣言を見てみましょう。

def collect [B, That] (pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Traversable[A], B, That]): That

collectの呼び出し時に明示的に型パラメータB, Thatを指定しているので、実際には、

def collect(pf: PartialFunction[String, A])(implicit bf: CanBuildFrom[Traversable[String], A, C[A]]): C[A]

というシグニチャを持ったcollectの呼び出しに対して型チェックが行われます。ここで問題になるのが、CanBuildFrom同士の型の互換性です。

端的に言うと、

CanBuildFrom[C[String], A, C[A]] // (呼び出し側)

と

CanBuildFrom[Traversable[String], A, C[A]] //(呼び出され側)

の二つの型の間には互換性が無いため、コンパイルエラーになってしまいます。なぜ互換性が無いかというと、

C[String] <: Travrersable[String] // A <: B は A は B のサブタイプである、ということを意味する

なのに対して、CanBuildFromの定義は

trait CanBuildFrom [-From, -Elem, +To] extends AnyRef

であり、第一型パラメータFromが反変として定義されているからです*3。


さて、ここまでは、何故、最初の誤ったコードがコンパイルエラーになるかを説明しましたが、それは原因の根本ではありません。


根本的な問題は、grepの定義を含むコードをコンパイルする時点では、ScalaコンパイラはC[String]の「実際の型」を知る手段が無いため、C[String]をTraversable[String]のようにみなして型チェックを行うという点です。


コードを書いた人間としては、C[String]#collectの呼び出しにおいて、C[String]の「実際の型」(List[String], Set[String], ...)に基づいて型チェックをして欲しいのですが、Scalaの型システムの制限上、それは不可能です。


Scala 2.8のコレクションライブラリでは、ややトリッキーな技巧を用いてこの問題点を回避しています。まず、Traversable[A]#collectを実際に定義しているトレイトであるTraversableLikeの宣言を見てみます。

trait TraversableLike [+A, +Repr] extends /* 本題に関係ないので省く ... */ {
  //...
  def collect [B, That] (pf: PartialFunction[A, B])(implicit bf: CanBuildFrom[Repr, B, That]): That 
  //...
}


Traversableと比較すると、

  • トレイトの宣言で、謎の型パラメータReprが追加されている
  • collectの宣言では、CanBuildFromに渡す第一型パラメータがReprになっている
のが主な違いです。


このReprが重要なところで、型パラメータReprには、コレクションの実装クラス・トレイト(Traversable, List ...)を定義する時に、そのコレクションの「実際の型」を渡すことになっています。このようなテクニックによって、コレクションの「実際の型」をうまく回復しよう、というわけです。


これを踏まえた上で、「正しい」定義を見てみましょう。

class GrepCallable[C[X] <: TraversableLike[X, C[X]]](tr: C[String]){

C[X]の上限境界には、Traversable[X]の代わりにTraversableLike[X, C[X]]が指定されていることがわかります。このようにすると、tr.collectの呼び出し時には、collectの型が

def collect(pf: PartialFunction[String, A])(implicit bf: CanBuildFrom[C[String], A, C[A]]): C[A]

となります。この

CanBuildFrom[C[String], A, C[A]]

という型は、collectの呼び出し側にあるbfの型

CanBuildFrom[C[String], A, C[A]]

と一致するため、無事にコンパイルを通るようになります。


長々と説明してきたことからわかるように、この問題はなかなかやっかいなもので、Scala初心者だけではなく、ある程度Scalaの経験がある人にとっても難しいかと思います。


一般論としては、コレクションに関する、汎用性が非常に高いメソッドをPimp my library*4によって追加しようとすると、Scalaの型システムに対するある程度高度な理解が必要になります。つまり、Scalaの暗黒面*5にある程度触れなければなりません。


Scalaの暗黒面を学ぶためにどの程度の期間が必要かによるのですが、今回のようなケースで List 限定で grep メソッドを追加するようにしたのは、それなりに妥当かと思います。


ちなみに、C++のテンプレートでは、メソッド定義時点では型パラメータに関する操作の正当性をチェックしないため*6、このような問題は発生しませんが、一方で、分割コンパイルの実装は容易ではありません。Scalaのようなシステムでは、上記のような問題が起こる代わりに、分割コンパイルを容易に実装することができます。


補足(重要)：このエントリでの趣旨は、Stringを要素に持つ任意のコレクションにgrepを適用できるようにしつつ、かつ、Scalaコレクションライブラリの基本思想である「戻り値同型」の原則を遵守しようとすると複雑になるというものです。


強調した部分を明示していなかったので、コレクションにメソッドを追加するだけでこれだけ複雑な事を知らなければいけない、と誤解されたかもしれません。実際には、「戻り値同型」の原則を守らなくていいのなら、

import scala.collection.Traversable
import scala.collection.generic.CanBuildFrom
object PimpGrepToCollection {
  class GrepCallable[X](tr: Traversable[String]){
    def grep[A](regex:String)(func:String => A = identity _):Traversable[A] =
      tr.collect{
        case s if regex.r.findFirstIn(s).isDefined => func(s)
      }
  }
  implicit def toGrepCallable[A](tr: Traversable[String]): GrepCallable[A] = new GrepCallable[A](tr)
}

というコードを書くだけでOKです。これで、ほとんど全てのコレクションにgrepメソッドが追加できます。ただし、grepの戻り値は必ずTraversableになってしまいます。

*1:コード自体はさほど長くありませんが

*2:このXは通常の型パラメータではなく、高階型パラメータと呼ぶべきものですが、その説明をすると長くなるので省きます

*3:共変であればコンパイルを通ります

*4:implicit conversionによってメソッドを「後付けで」追加するパターンのこと

*5:半分は冗談ですが

*6:この理解が間違っていたらツッコミお願いします