[解決済み] Scalaのコレクションにenrich-my-libraryパターンを適用するにはどうしたらいいですか？

質問

Scalaで利用できる最も強力なパターンの1つがenrich-my-library*パターンで、暗黙的な変換を利用して 現れる への暗黙の変換を利用して、動的なメソッド解決を必要とせずに既存のクラスにメソッドを追加することができます。 例えば，全ての文字列がメソッド spaces というメソッドを持ち、空白文字が何文字あるか数えることができれば、それは可能です。

class SpaceCounter(s: String) {
  def spaces = s.count(_.isWhitespace)
}
implicit def string_counts_spaces(s: String) = new SpaceCounter(s)

scala> "How many spaces do I have?".spaces
res1: Int = 5

残念ながら、このパターンは一般的なコレクションを扱うときに問題に直面します。 例えば、多くの質問があるのは コレクションでアイテムを順番にグループ化する . 一発で動作するようなものは組み込まれていないので、これは一般的なコレクションを使用した enrich-my-library パターンの理想的な候補のように思われます。 C と一般的な要素タイプ A :

class SequentiallyGroupingCollection[A, C[A] <: Seq[A]](ca: C[A]) {
  def groupIdentical: C[C[A]] = {
    if (ca.isEmpty) C.empty[C[A]]
    else {
      val first = ca.head
      val (same,rest) = ca.span(_ == first)
      same +: (new SequentiallyGroupingCollection(rest)).groupIdentical
    }
  }
}

を除いて、もちろん、それは は機能しません。 . REPLが教えてくれます。

<console>:12: error: not found: value C
               if (ca.isEmpty) C.empty[C[A]]
                               ^
<console>:16: error: type mismatch;
 found   : Seq[Seq[A]]
 required: C[C[A]]
                 same +: (new SequentiallyGroupingCollection(rest)).groupIdentical
                      ^

問題は2つあります。 C[C[A]] からどのようにして空の C[A] のリストから (あるいは空白から) を取得することはできますか? また、どのようにして C[C[A]] から戻ってくるのでしょうか？ same +: 行の代わりに Seq[Seq[A]] ?

* ^{以前は pimp-my-library として知られていました。}

どのように解決するのですか？

この問題を理解するための鍵は、次のようなものがあることに気づくことです。 コレクションを構築して作業するための 2 つの異なる方法 があることを理解することです。 1つは、すべての素晴らしいメソッドを持つパブリックコレクションインターフェースです。 もうひとつは 作成 を作成する際に広範囲に使用されますが、その外部ではほとんど使用されませんが、ビルダーです。

濃縮における私たちの問題は、同じ型のコレクションを返そうとするときにコレクション・ライブラリ自体が直面するものとまったく同じものです。 つまり、私たちはコレクションを構築したいのですが、一般的に作業する場合、"コレクションがすでにあるのと同じ型" を参照する方法がありません。 そこで ビルダー .

さて、問題はビルダーをどこから手に入れるかです。 明らかなのは、コレクションそのものからです。 これはうまくいきません。 . 私たちはすでに、一般的なコレクションに移行する際に、コレクションの型を忘れることを決定しました。 そのため、コレクションは私たちが望む型のコレクションをさらに生成するビルダーを返すことができたとしても、その型が何であるかはわからないのです。

その代わり、ビルダーは CanBuildFrom という暗黙の了解がある。 これらは特に入力と出力の型をマッチングさせ、適切に型付けされたビルダーを与える目的で存在します。

ということで、2つの概念の飛躍がありました。

1. 標準的なコレクション操作ではなく、ビルダーを使用しています。
2. これらのビルダーは暗黙の CanBuildFrom から取得します。

例を見てみましょう。

class GroupingCollection[A, C[A] <: Iterable[A]](ca: C[A]) {
  import collection.generic.CanBuildFrom
  def groupedWhile(p: (A,A) => Boolean)(
    implicit cbfcc: CanBuildFrom[C[A],C[A],C[C[A]]], cbfc: CanBuildFrom[C[A],A,C[A]]
  ): C[C[A]] = {
    val it = ca.iterator
    val cca = cbfcc()
    if (!it.hasNext) cca.result
    else {
      val as = cbfc()
      var olda = it.next
      as += olda
      while (it.hasNext) {
        val a = it.next
        if (p(olda,a)) as += a
        else { cca += as.result; as.clear; as += a }
        olda = a
      }
      cca += as.result
    }
    cca.result
  }
}
implicit def iterable_has_grouping[A, C[A] <: Iterable[A]](ca: C[A]) = {
  new GroupingCollection[A,C](ca)
}

これを分解してみましょう。 まず、コレクションオブコレクションを構築するために、2種類のコレクションを構築する必要があることがわかります。 C[A] を各グループに、そして C[C[A]] で、すべてのグループをまとめる。 したがって、2つのビルダーが必要で、1つは A を受け取り C[A] を取るもの、そして C[A] を取り込んで C[C[A]] s. の型シグネチャを見ると CanBuildFrom を見ると

CanBuildFrom[-From, -Elem, +To]

これは、CanBuildFrom がコレクションの種類を知りたがっていることを意味します。 C[A] そして、生成されるコレクションの要素とそのコレクションの型。 そこで、暗黙のパラメータとしてこれらを記入する cbfcc と cbfc .

これを実現したことで、ほとんどの作業は終了です。 私たちは CanBuildFrom を使えば、ビルダーを与えることができます (必要なのはそれを適用することだけです)。 そして、一つのビルダーがコレクションを構築するために += でコレクションを構築し、それを最終的にあるべき姿のコレクションに変換し result で自分自身を空にし、再び始められるようにします。 clear . ビルダーは空から始まるので、最初のコンパイルエラーは解決されました。

最後にもう一つ、実際に作業を行うアルゴリズム以外の小さな詳細は、暗黙の変換にあります。 私たちは new GroupingCollection[A,C] ではなく [A,C[A]] . これは、クラス宣言が C を一つのパラメータで埋め、それを自分自身で A で埋められます。 つまり、単に型 C という型を渡し、それを使って C[A] を生成させます。 細かいことですが、他の方法を試すとコンパイル時にエラーが発生します。

ここでは、メソッドを "equal elements" コレクションよりも少し汎用的にしました。むしろ、連続した要素のテストが失敗するたびに、メソッドは元のコレクションを切り離します。

私たちのメソッドを実際に見てみましょう。

scala> List(1,2,2,2,3,4,4,4,5,5,1,1,1,2).groupedWhile(_ == _)
res0: List[List[Int]] = List(List(1), List(2, 2, 2), List(3), List(4, 4, 4), 
                             List(5, 5), List(1, 1, 1), List(2))

scala> Vector(1,2,3,4,1,2,3,1,2,1).groupedWhile(_ < _)
res1: scala.collection.immutable.Vector[scala.collection.immutable.Vector[Int]] =
  Vector(Vector(1, 2, 3, 4), Vector(1, 2, 3), Vector(1, 2), Vector(1))

うまくいった!

唯一の問題は、一般的に配列に対してこれらのメソッドを利用できないことです。なぜなら、それは2つの暗黙の変換を並べる必要があるからです。 これを回避する方法はいくつかあります。例えば、配列のために別の暗黙の変換を書いたり、配列にキャストして WrappedArray へのキャスト、などです。

編集：配列や文字列などを扱う際に私が好んで使う方法は、コードを均等にすることです。 より そして、適切な暗黙の変換を使用して、配列も動作するように、それらをより特定化することです。 この特定のケースでは

class GroupingCollection[A, C, D[C]](ca: C)(
  implicit c2i: C => Iterable[A],
           cbf: CanBuildFrom[C,C,D[C]],
           cbfi: CanBuildFrom[C,A,C]
) {
  def groupedWhile(p: (A,A) => Boolean): D[C] = {
    val it = c2i(ca).iterator
    val cca = cbf()
    if (!it.hasNext) cca.result
    else {
      val as = cbfi()
      var olda = it.next
      as += olda
      while (it.hasNext) {
        val a = it.next
        if (p(olda,a)) as += a
        else { cca += as.result; as.clear; as += a }
        olda = a
      }
      cca += as.result
    }
    cca.result
  }
}

ここでは、暗黙的に Iterable[A] から C -ほとんどのコレクションでは、これは単なる同一性になります (例えば List[A] はすでに Iterable[A] になっています）が、配列の場合は本当に暗黙のうちに変換されることになります。 そして、その結果、私たちは以下の要件を取り下げました。 C[A] <: Iterable[A] --という要件を削除し、基本的に <% の要件を明示したに過ぎず、コンパイラがそれを埋めてくれる代わりに、私たちは任意でそれを明示的に使用することができます。 また、コレクションオブコレクションが C[C[A]] --であるという制限を緩和しました。 D[C] であり、これは後で私たちが望むものになるように記入します。 後で記入するので、メソッドレベルではなく、クラスレベルに押し上げています。 それ以外は基本的に同じです。

さて、問題はこれをどう使うかです。 通常のコレクションであれば

implicit def collections_have_grouping[A, C[A]](ca: C[A])(
  implicit c2i: C[A] => Iterable[A],
           cbf: CanBuildFrom[C[A],C[A],C[C[A]]],
           cbfi: CanBuildFrom[C[A],A,C[A]]
) = {
  new GroupingCollection[A,C[A],C](ca)(c2i, cbf, cbfi)
}

ここで、プラグイン C[A] に対して C と C[C[A]] に対して D[C] . を呼び出す際に明示的なジェネリック型が必要なことに注意してください。 new GroupingCollection を呼び出す際に、どの型が何に対応するのかを明確にできるようにする必要があることに注意してください。 そのため implicit c2i: C[A] => Iterable[A] のおかげで、これは自動的に配列を扱えるようになります。

でも、文字列を使いたい場合はどうすればいいのでしょうか？ なぜなら、文字列の文字列を持つことはできないからです。 ここで追加の抽象化が役に立ちます。 D を文字列を保持するのに適した何かと呼ぶことができるのです。 それでは Vector を選んで、次のようにしてみましょう。

val vector_string_builder = (
  new CanBuildFrom[String, String, Vector[String]] {
    def apply() = Vector.newBuilder[String]
    def apply(from: String) = this.apply()
  }
)

implicit def strings_have_grouping(s: String)(
  implicit c2i: String => Iterable[Char],
           cbfi: CanBuildFrom[String,Char,String]
) = {
  new GroupingCollection[Char,String,Vector](s)(
    c2i, vector_string_builder, cbfi
  )
}

私たちは、新しい CanBuildFrom を呼び出すだけなので、これはとても簡単です。 Vector.newBuilder[String] を呼び出すだけなのでとても簡単です）、そして、すべての型を埋める必要があります。 GroupingCollection が賢明に型付けされるように、すべての型を埋める必要があります。 私たちはすでに [String,Char,String] CanBuildFromがあるので、文字列は文字の集まりから作ることができます。

試してみましょう。

scala> List(true,false,true,true,true).groupedWhile(_ == _)
res1: List[List[Boolean]] = List(List(true), List(false), List(true, true, true))

scala> Array(1,2,5,3,5,6,7,4,1).groupedWhile(_ <= _) 
res2: Array[Array[Int]] = Array(Array(1, 2, 5), Array(3, 5, 6, 7), Array(4), Array(1))

scala> "Hello there!!".groupedWhile(_.isLetter == _.isLetter)
res3: Vector[String] = Vector(Hello,  , there, !!)