Jak zastosować wzorzec wzbogacania mojej biblioteki do kolekcji Scala?

Jeden z najpotężniejszych wzorów dostępnych w Scala jest Enrich-my-biblioteka * wzór, który wykorzystuje niejawne konwersje pojawiają dodać metod do istniejących klas bez konieczności rozdzielczość metody dynamiczne. Na przykład, gdybyśmy chcieli, aby wszystkie łańcuchy miały metodę spaceszliczającą, ile mają białych znaków, moglibyśmy:

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

Niestety, ten wzorzec powoduje problemy w przypadku zbiorów ogólnych. Na przykład zadawano szereg pytań dotyczących grupowania elementów sekwencyjnie z kolekcjami . Nie ma nic wbudowanego, co działałoby w jednym ujęciu, więc wydaje się, że jest to idealny kandydat do wzorca wzbogacania-moja-biblioteka przy użyciu ogólnej kolekcji Ci ogólnego typu elementu 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
    }
  }
}

z wyjątkiem, oczywiście, że nie działa . REPL mówi nam:

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

Są dwa problemy: jak uzyskać C[C[A]]z pustej C[A]listy (lub z powietrza)? A jak możemy uzyskać C[C[A]]powrót z same +:linii zamiast a Seq[Seq[A]]?

* ^{Wcześniej znany jako pimp-my-library.}

Kluczem do zrozumienia tego problemu jest uświadomienie sobie, że istnieją dwa różne sposoby tworzenia i pracy z kolekcjami w bibliotece kolekcji. Jednym z nich jest interfejs publicznych kolekcji ze wszystkimi przyjemnymi metodami. Drugi, który jest szeroko stosowany przy tworzeniu biblioteki kolekcji, ale prawie nigdy nie jest używany poza nią, to budowniczowie.

Nasz problem ze wzbogacaniem jest dokładnie taki sam, z jakim boryka się sama biblioteka kolekcji, próbując zwrócić kolekcje tego samego typu. Oznacza to, że chcemy budować kolekcje, ale pracując ogólnie, nie mamy możliwości odniesienia się do „tego samego typu, jakim jest już kolekcja”. Potrzebujemy więc budowniczych .

Teraz pytanie brzmi: skąd bierzemy naszych konstruktorów? Oczywiste miejsce pochodzi z samej kolekcji. To nie działa . Już zdecydowaliśmy, przechodząc do kolekcji ogólnej, że zapomnimy o jej typie. Więc nawet jeśli kolekcja mogłaby zwrócić program budujący, który wygenerowałby więcej kolekcji żądanego typu, nie wiedziałby, jaki to był typ.

Zamiast tego otrzymujemy naszych budowniczych z CanBuildFromimplikacji, które krążą wokół. Istnieją one specjalnie w celu dopasowania typów danych wejściowych i wyjściowych i zapewniają odpowiednio wpisany konstruktor.

Mamy więc do zrobienia dwa koncepcyjne skoki:

1. Nie używamy standardowych operacji zbierania, używamy konstruktorów.
2. Otrzymujemy te konstruktory z ukrytych CanBuildFroms, a nie bezpośrednio z naszej kolekcji.

Spójrzmy na przykład.

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

Rozbierzmy to na części. Po pierwsze, aby zbudować kolekcję kolekcji, wiemy, że będziemy musieli zbudować dwa typy kolekcji: C[A]dla każdej grupy, C[C[A]]która gromadzi wszystkie grupy razem. Tak więc potrzebujemy dwóch konstruktorów, jednego, który bierze As i buduje C[A]s, a drugiego, który bierze C[A]si buduje C[C[A]]s. Patrząc na typ podpisu CanBuildFrom, widzimy

CanBuildFrom[-From, -Elem, +To]

co oznacza, że ​​CanBuildFrom chce poznać typ kolekcji, od której zaczynamy - w naszym przypadku jest to C[A], a następnie elementy wygenerowanej kolekcji i typ tej kolekcji. Więc wypełniamy je jako niejawne parametry cbfcci cbfc.

Uświadomiwszy sobie to, to większość pracy. Możemy użyć naszych, CanBuildFromaby dać nam konstruktorów (wszystko, co musisz zrobić, to je zastosować). Jeden konstruktor może zbudować kolekcję +=, przekonwertować ją na kolekcję, z którą ma się ostatecznie znajdować result, opróżnić się i być gotowym do ponownego użycia clear. Konstruktory zaczynają puste, co rozwiązuje nasz pierwszy błąd kompilacji, a ponieważ zamiast rekurencji używamy konstruktorów, drugi błąd również znika.

Ostatni mały szczegół - inny niż algorytm, który faktycznie działa - dotyczy niejawnej konwersji. Zauważ, że używamy new GroupingCollection[A,C]nie [A,C[A]]. Dzieje się tak, ponieważ deklaracja klasy zawierała Cjeden parametr, który sama wypełnia Aprzekazanym do niej parametrem. Więc po prostu podajemy mu typ Ci pozwalamy mu tworzyć C[A]z tego. Drobne szczegóły, ale jeśli spróbujesz w inny sposób, pojawią się błędy w czasie kompilacji.

Tutaj uczyniłem metodę nieco bardziej ogólną niż zbiór „równych elementów” - raczej metoda odcina oryginalną kolekcję, ilekroć nie powiedzie się jej test elementów sekwencyjnych.

Zobaczmy, jak działa nasza metoda:

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

To działa!

Jedynym problemem jest to, że generalnie nie mamy tych metod dostępnych dla tablic, ponieważ wymagałoby to dwóch niejawnych konwersji z rzędu. Istnieje kilka sposobów obejścia tego problemu, w tym napisanie oddzielnej niejawnej konwersji dla tablic, rzutowanie na WrappedArrayi tak dalej.

Edycja: Moim ulubionym podejściem do pracy z tablicami i ciągami jest uczynienie kodu jeszcze bardziej ogólnym, a następnie użycie odpowiednich niejawnych konwersji, aby uczynić je bardziej szczegółowymi w taki sposób, aby tablice również działały. W tym konkretnym przypadku:

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

Tutaj dodaliśmy niejawne, które daje nam Iterable[A]from C- dla większości kolekcji będzie to po prostu tożsamość (np. List[A]Już jest Iterable[A]), ale dla tablic będzie to prawdziwa niejawna konwersja. W konsekwencji zrezygnowaliśmy z wymagania, które - C[A] <: Iterable[A]po prostu wprowadziliśmy wymóg dotyczący jawności <%, więc możemy go używać jawnie do woli, zamiast wypełniać go za nas kompilator. Ponadto złagodziliśmy ograniczenie, że nasza kolekcja kolekcji jest - C[C[A]]zamiast tego jest dowolna D[C], którą wypełnimy później, aby była tym, czego chcemy. Ponieważ zajmiemy się tym później, przenieśliśmy to na poziom klasy, a nie na poziom metody. W przeciwnym razie jest w zasadzie to samo.

Teraz pytanie brzmi, jak to wykorzystać. W przypadku zwykłych kolekcji możemy:

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

gdzie teraz podłączamy C[A]dla Ci C[C[A]]dla D[C]. Zauważ, że potrzebujemy jawnych typów ogólnych w wywołaniu, aby new GroupingCollectionmożna było określić, które typy odpowiadają czemu. Dzięki implicit c2i: C[A] => Iterable[A]temu automatycznie obsługuje tablice.

Ale czekaj, a co jeśli chcemy użyć ciągów? Teraz mamy kłopoty, ponieważ nie możesz mieć „ciągu łańcuchów”. W tym pomaga dodatkowa abstrakcja: możemy wywołać Dcoś, co jest odpowiednie do przechowywania łańcuchów. Wybierzmy Vectori wykonaj następujące czynności:

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

Potrzebujemy nowego CanBuildFromdo obsługi budowy wektora ciągów (ale jest to naprawdę łatwe, ponieważ musimy tylko wywołać Vector.newBuilder[String]), a następnie musimy wypełnić wszystkie typy, aby było GroupingCollectionsensownie wpisane. Zauważ, że mamy już pływające wokół [String,Char,String]CanBuildFrom, więc łańcuchy mogą być tworzone z kolekcji znaków.

Wypróbujmy to:

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

W związku z tym zobowiązaniem znacznie łatwiej jest „wzbogacić” kolekcje Scali, niż wtedy, gdy Rex udzielił doskonałej odpowiedzi. W prostych przypadkach może to wyglądać tak:

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)

który dodaje „ten sam typ wyniku” z uwzględnieniem filterMapoperacji do wszystkich GenTraversableLikes,

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

Na przykład z pytania rozwiązanie wygląda teraz tak:

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)

Przykładowa sesja 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)

Ponownie zwróć uwagę, że ta sama zasada typu wyniku została zaobserwowana w dokładnie taki sam sposób, w jaki zostałaby groupIdenticalbezpośrednio zdefiniowana GenTraversableLike.

Od tego popełnienia magiczne zaklęcie jest nieco zmienione w porównaniu z tym, co było, gdy Miles udzielił doskonałej odpowiedzi.

Poniższe działa, ale czy jest kanoniczne? Mam nadzieję, że jeden z kanonów to naprawi. (A raczej armaty, jedno z dużych dział). Jeśli granica widoku jest górną granicą, tracisz zastosowanie do Array and String. Nie ma znaczenia, czy powiązanie to GenTraversableLike czy TraversableLike; ale IsTraversableLike daje Ci 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)

Jest więcej niż jeden sposób na oskórowanie kota, który ma dziewięć żyć. Ta wersja mówi, że gdy moje źródło zostanie przekonwertowane na GenTraversableLike, o ile mogę zbudować wynik z GenTraversable, po prostu zrób to. Nie interesuje mnie mój stary Repr.

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)

Ta pierwsza próba obejmuje brzydką konwersję Repr do 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)