Bagaimana cara menerapkan pola perkaya-perpustakaan-saya ke koleksi Scala?

Salah satu pola paling kuat yang tersedia di Scala adalah pola perkaya-pustaka-saya *, yang menggunakan konversi implisit agar tampak menambahkan metode ke kelas yang ada tanpa memerlukan resolusi metode dinamis. Misalnya, jika kita ingin semua string memiliki metode spacesyang menghitung berapa banyak karakter spasi yang mereka miliki, kita dapat:

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

Sayangnya, pola ini mengalami masalah saat menangani koleksi generik. Misalnya, sejumlah pertanyaan telah ditanyakan tentang pengelompokan item secara berurutan dengan koleksi . Tidak ada bawaan yang berfungsi dalam satu pengambilan, jadi ini tampaknya kandidat ideal untuk pola memperkaya-perpustakaan-saya menggunakan koleksi umum Cdan jenis elemen generik 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
    }
  }
}

kecuali, tentu saja, itu tidak berhasil . REPL memberi tahu kita:

<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
                      ^

Ada dua masalah: bagaimana kita mendapatkan C[C[A]]dari C[A]daftar kosong (atau dari udara kosong )? Dan bagaimana kita mendapatkan C[C[A]]kembali dari same +:garis daripada Seq[Seq[A]]?

* ^{Sebelumnya dikenal sebagai pimp-my-library.}

Kunci untuk memahami masalah ini adalah dengan menyadari bahwa ada dua cara berbeda untuk membangun dan bekerja dengan koleksi di perpustakaan koleksi. Salah satunya adalah antarmuka koleksi publik dengan semua metodenya yang bagus. Yang lainnya, yang digunakan secara ekstensif dalam membuat perpustakaan koleksi, tetapi yang hampir tidak pernah digunakan di luarnya, adalah pembangun.

Masalah kita dalam memperkaya sama persis dengan yang dihadapi perpustakaan koleksi itu sendiri ketika mencoba mengembalikan koleksi dari jenis yang sama. Artinya, kami ingin membangun koleksi, tetapi saat bekerja secara umum, kami tidak memiliki cara untuk merujuk ke "tipe yang sama dengan koleksi tersebut". Jadi kami membutuhkan pembangun .

Sekarang pertanyaannya adalah: dari mana kita mendapatkan pembangun kita? Tempat yang jelas adalah dari koleksi itu sendiri. Ini tidak berhasil . Kami telah memutuskan, saat pindah ke koleksi umum, bahwa kami akan melupakan jenis koleksinya. Jadi, meskipun collection dapat mengembalikan pembangun yang akan menghasilkan lebih banyak koleksi dari jenis yang kita inginkan, ia tidak akan tahu apa jenisnya.

Sebagai gantinya, kita mendapatkan pembangun kita dari CanBuildFromimplikasinya yang beredar. Ini ada secara khusus untuk tujuan mencocokkan jenis masukan dan keluaran dan memberi Anda pembangun yang diketik dengan tepat.

Jadi, kami memiliki dua lompatan konseptual yang harus dilakukan:

1. Kami tidak menggunakan operasi pengumpulan standar, kami menggunakan pembangun.
2. Kami mendapatkan pembangun ini dari implisit CanBuildFrom, bukan dari koleksi kami secara langsung.

Mari kita lihat contohnya.

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)
}

Mari kita pisahkan ini. Pertama, untuk membangun koleksi-koleksi, kita tahu kita perlu membangun dua jenis koleksi: C[A]untuk setiap grup, dan C[C[A]]itu mengumpulkan semua grup bersama-sama. Jadi, kita membutuhkan dua pembangun, satu yang mengambil As dan membangun C[A], dan satu yang mengambil C[A]s dan membangun C[C[A]]. Melihat jenis tanda tangan CanBuildFrom, kita lihat

CanBuildFrom[-From, -Elem, +To]

yang berarti CanBuildFrom ingin mengetahui jenis koleksi yang kita mulai - dalam kasus kita, ini C[A], lalu elemen koleksi yang dihasilkan dan jenis koleksi itu. Jadi kami mengisinya sebagai parameter implisit cbfccdan cbfc.

Setelah menyadari ini, itulah sebagian besar pekerjaan. Kami dapat menggunakan milik kami CanBuildFromuntuk memberi kami pembangun (yang perlu Anda lakukan hanyalah menerapkannya). Dan satu pembangun dapat membuat koleksi dengan +=, mengubahnya menjadi koleksi yang seharusnya ada result, dan mengosongkan dirinya sendiri serta siap untuk memulai lagi clear. Pembangun mulai dari kosong, yang memecahkan kesalahan kompilasi pertama kita, dan karena kita menggunakan pembangun alih-alih rekursi, kesalahan kedua juga akan hilang.

Satu detail kecil terakhir - selain algoritme yang benar-benar berfungsi - ada dalam konversi implisit. Perhatikan bahwa kami new GroupingCollection[A,C]tidak menggunakan [A,C[A]]. Ini karena deklarasi kelas adalah untuk Cdengan satu parameter, yang akan mengisinya sendiri dengan yang Aditeruskan padanya. Jadi kita hanya menyerahkan jenisnya C, dan membiarkannya C[A]membuatnya. Detail kecil, tetapi Anda akan mendapatkan kesalahan waktu kompilasi jika Anda mencoba cara lain.

Di sini, saya telah membuat metode ini sedikit lebih umum daripada kumpulan "elemen yang sama" - alih-alih, metode ini memotong koleksi asli setiap kali pengujiannya terhadap elemen sekuensial gagal.

Mari kita lihat metode kita beraksi:

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))

Berhasil!

Satu-satunya masalah adalah bahwa kita secara umum tidak memiliki metode ini tersedia untuk array, karena itu akan membutuhkan dua konversi implisit berturut-turut. Ada beberapa cara untuk menyiasatinya, termasuk menulis konversi implisit terpisah untuk array, mentransmisikan ke WrappedArray, dan sebagainya.

Sunting: Pendekatan favorit saya untuk menangani array dan string dan semacamnya adalah membuat kode menjadi lebih umum dan kemudian menggunakan konversi implisit yang sesuai untuk membuatnya lebih spesifik lagi sedemikian rupa sehingga array juga berfungsi. Dalam kasus khusus ini:

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
  }
}

Di sini kita telah menambahkan implisit yang memberi kita Iterable[A]dari C--untuk sebagian besar koleksi ini hanya akan menjadi identitas (misalnya List[A]sudah merupakan Iterable[A]), tetapi untuk array itu akan menjadi konversi implisit nyata. Dan, akibatnya, kami telah menghilangkan persyaratan bahwa - C[A] <: Iterable[A]kami pada dasarnya baru saja membuat persyaratan untuk <%eksplisit, jadi kami dapat menggunakannya secara eksplisit sesuka hati alih-alih meminta kompiler mengisinya untuk kami. Juga, kami telah melonggarkan batasan bahwa koleksi-koleksi kami adalah C[C[A]]--malahan, apa saja D[C], yang akan kami isi nanti untuk menjadi apa yang kami inginkan. Karena kita akan mengisinya nanti, kita telah mendorongnya ke tingkat kelas alih-alih ke tingkat metode. Kalau tidak, pada dasarnya sama.

Sekarang pertanyaannya adalah bagaimana menggunakan ini. Untuk koleksi biasa, kami dapat:

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)
}

di mana sekarang kita pasang C[A]untuk Cdan C[C[A]]untuk D[C]. Perhatikan bahwa kita memang membutuhkan tipe generik eksplisit pada panggilan tersebut new GroupingCollectionsehingga dapat menjaga tipe mana yang sesuai dengan apa. Berkat implicit c2i: C[A] => Iterable[A], ini secara otomatis menangani array.

Tapi tunggu dulu, bagaimana jika kita ingin menggunakan string? Sekarang kami dalam masalah, karena Anda tidak dapat memiliki "string". Di sinilah abstraksi ekstra membantu: kita dapat memanggil Dsesuatu yang cocok untuk menyimpan string. Ayo pilih Vector, dan lakukan hal berikut:

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
  )
}

Kita membutuhkan yang baru CanBuildFromuntuk menangani pembangunan vektor string (tapi ini sangat mudah, karena kita hanya perlu memanggil Vector.newBuilder[String]), dan kemudian kita perlu mengisi semua tipe sehingga GroupingCollectiondiketik dengan bijaksana. Perhatikan bahwa kita telah mengapung di sekitar [String,Char,String]CanBuildFrom, sehingga string dapat dibuat dari kumpulan karakter.

Mari kita coba:

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, !!)

Sejak komitmen ini, jauh lebih mudah untuk "memperkaya" koleksi Scala daripada saat Rex memberikan jawaban yang sangat bagus. Untuk kasus sederhana mungkin terlihat seperti ini,

import scala.collection.generic.{ CanBuildFrom, FromRepr, HasElem }
import language.implicitConversions

class FilterMapImpl[A, Repr](val r : Repr)(implicit hasElem : HasElem[Repr, A]) {
  def filterMap[B, That](f : A => Option[B])
    (implicit cbf : CanBuildFrom[Repr, B, That]) : That = r.flatMap(f(_).toSeq)
}

implicit def filterMap[Repr : FromRepr](r : Repr) = new FilterMapImpl(r)

yang menambahkan "jenis hasil yang sama" filterMapuntuk operasi ke semua GenTraversableLike,

scala> val l = List(1, 2, 3, 4, 5)
l: List[Int] = List(1, 2, 3, 4, 5)

scala> l.filterMap(i => if(i % 2 == 0) Some(i) else None)
res0: List[Int] = List(2, 4)

scala> val a = Array(1, 2, 3, 4, 5)
a: Array[Int] = Array(1, 2, 3, 4, 5)

scala> a.filterMap(i => if(i % 2 == 0) Some(i) else None)
res1: Array[Int] = Array(2, 4)

scala> val s = "Hello World"
s: String = Hello World

scala> s.filterMap(c => if(c >= 'A' && c <= 'Z') Some(c) else None)
res2: String = HW

Dan untuk contoh dari pertanyaan tersebut, solusinya sekarang terlihat seperti,

class GroupIdenticalImpl[A, Repr : FromRepr](val r: Repr)
  (implicit hasElem : HasElem[Repr, A]) {
  def groupIdentical[That](implicit cbf: CanBuildFrom[Repr,Repr,That]): That = {
    val builder = cbf(r)
    def group(r: Repr) : Unit = {
      val first = r.head
      val (same, rest) = r.span(_ == first)
      builder += same
      if(!rest.isEmpty)
        group(rest)
    }
    if(!r.isEmpty) group(r)
    builder.result
  }
}

implicit def groupIdentical[Repr : FromRepr](r: Repr) = new GroupIdenticalImpl(r)

Contoh sesi REPL,

scala> val l = List(1, 1, 2, 2, 3, 3, 1, 1)
l: List[Int] = List(1, 1, 2, 2, 3, 3, 1, 1)

scala> l.groupIdentical
res0: List[List[Int]] = List(List(1, 1),List(2, 2),List(3, 3),List(1, 1))

scala> val a = Array(1, 1, 2, 2, 3, 3, 1, 1)
a: Array[Int] = Array(1, 1, 2, 2, 3, 3, 1, 1)

scala> a.groupIdentical
res1: Array[Array[Int]] = Array(Array(1, 1),Array(2, 2),Array(3, 3),Array(1, 1))

scala> val s = "11223311"
s: String = 11223311

scala> s.groupIdentical
res2: scala.collection.immutable.IndexedSeq[String] = Vector(11, 22, 33, 11)

Sekali lagi, perhatikan bahwa prinsip tipe hasil yang sama telah diamati dengan cara yang sama persis seperti prinsip yang groupIdenticaldidefinisikan secara langsung GenTraversableLike.

Saat melakukan ini , mantra sihir sedikit berubah dari saat Miles memberikan jawaban yang sangat bagus.

Berikut ini berfungsi, tetapi apakah itu kanonik? Saya berharap salah satu kanon akan memperbaikinya. (Atau lebih tepatnya, meriam, salah satu senjata besar.) Jika view bound adalah batas atas, Anda kehilangan aplikasi untuk Array dan String. Tampaknya tidak masalah apakah yang terikat adalah GenTraversableLike atau TraversableLike; tapi IsTraversableLike memberi Anda GenTraversableLike.

import language.implicitConversions
import scala.collection.{ GenTraversable=>GT, GenTraversableLike=>GTL, TraversableLike=>TL }
import scala.collection.generic.{ CanBuildFrom=>CBF, IsTraversableLike=>ITL }

class GroupIdenticalImpl[A, R <% GTL[_,R]](val r: GTL[A,R]) {
  def groupIdentical[That](implicit cbf: CBF[R, R, That]): That = {
    val builder = cbf(r.repr)
    def group(r: GTL[_,R]) {
      val first = r.head
      val (same, rest) = r.span(_ == first)
      builder += same
      if (!rest.isEmpty) group(rest)
    }
    if (!r.isEmpty) group(r)
    builder.result
  }
}

implicit def groupIdentical[A, R <% GTL[_,R]](r: R)(implicit fr: ITL[R]):
  GroupIdenticalImpl[fr.A, R] =
  new GroupIdenticalImpl(fr conversion r)

Ada lebih dari satu cara untuk menguliti kucing dengan sembilan nyawa. Versi ini mengatakan bahwa setelah sumber saya diubah menjadi GenTraversableLike, selama saya dapat membuat hasil dari GenTraversable, lakukan saja. Saya tidak tertarik dengan Repr lama saya.

class GroupIdenticalImpl[A, R](val r: GTL[A,R]) {
  def groupIdentical[That](implicit cbf: CBF[GT[A], GT[A], That]): That = {
    val builder = cbf(r.toTraversable)
    def group(r: GT[A]) {
      val first = r.head
      val (same, rest) = r.span(_ == first)
      builder += same
      if (!rest.isEmpty) group(rest)
    }
    if (!r.isEmpty) group(r.toTraversable)
    builder.result
  }
}

implicit def groupIdentical[A, R](r: R)(implicit fr: ITL[R]):
  GroupIdenticalImpl[fr.A, R] =
  new GroupIdenticalImpl(fr conversion r)

Upaya pertama ini mencakup konversi Repr yang buruk ke GenTraversableLike.

import language.implicitConversions
import scala.collection.{ GenTraversableLike }
import scala.collection.generic.{ CanBuildFrom, IsTraversableLike }

type GT[A, B] = GenTraversableLike[A, B]
type CBF[A, B, C] = CanBuildFrom[A, B, C]
type ITL[A] = IsTraversableLike[A]

class FilterMapImpl[A, Repr](val r: GenTraversableLike[A, Repr]) { 
  def filterMap[B, That](f: A => Option[B])(implicit cbf : CanBuildFrom[Repr, B, That]): That = 
    r.flatMap(f(_).toSeq)
} 

implicit def filterMap[A, Repr](r: Repr)(implicit fr: ITL[Repr]): FilterMapImpl[fr.A, Repr] = 
  new FilterMapImpl(fr conversion r)

class GroupIdenticalImpl[A, R](val r: GT[A,R])(implicit fr: ITL[R]) { 
  def groupIdentical[That](implicit cbf: CBF[R, R, That]): That = { 
    val builder = cbf(r.repr)
    def group(r0: R) { 
      val r = fr conversion r0
      val first = r.head
      val (same, other) = r.span(_ == first)
      builder += same
      val rest = fr conversion other
      if (!rest.isEmpty) group(rest.repr)
    } 
    if (!r.isEmpty) group(r.repr)
    builder.result
  } 
} 

implicit def groupIdentical[A, R](r: R)(implicit fr: ITL[R]):
  GroupIdenticalImpl[fr.A, R] = 
  new GroupIdenticalImpl(fr conversion r)