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:
- Nie używamy standardowych operacji zbierania, używamy konstruktorów.
- 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, !!)