Ключом к пониманию этой проблемы является осознание того, что есть два разных способа создания и работы с коллекциями в библиотеке коллекций. Одним из них является интерфейс открытых коллекций со всеми его приятными методами. Другой, широко используемой в создании библиотеки коллекций, но почти никогда не используемой вне ее, являются компоновщики.
Наша проблема в обогащении - та же самая, с которой сталкивается сама библиотека коллекций при попытке вернуть коллекции одного типа. То есть мы хотим создавать коллекции, но при общей работе у нас нет способа сослаться на «тот же тип, что и коллекция». Поэтому нам нужно строителей .
Теперь вопрос: откуда мы берем наших строителей? Очевидное место от самой коллекции. Это не работает . Мы уже решили, переходя к общей коллекции, что мы собираемся забыть тип коллекции. Поэтому, хотя коллекция может возвращать конструктор, который будет генерировать больше коллекций нужного нам типа, он не будет знать, что это за тип.
Вместо этого мы получаем наших строителей от CanBuildFrom последствий, которые плавают вокруг. Они существуют специально для того, чтобы сопоставить типы ввода и вывода и дать вам правильно типизированный компоновщик.
Итак, у нас есть два концептуальных прыжка:
- Мы не используем стандартные операции с коллекциями, мы используем компоновщики.
- Мы получаем этих строителей из неявных
CanBuildFrom s, а не из нашей коллекции напрямую.
Давайте рассмотрим пример.
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)
}
Давайте разберем это. Во-первых, чтобы создать коллекцию коллекций, мы знаем, что нам нужно создать два типа коллекций: C[A] для каждой группы и C[C[A]], которая собирает все группы вместе. Таким образом, нам нужны два компоновщика, один из которых берет A с и строит C[A] с, а другой - C[A] с и строит C[C[A]] с. Глядя на тип подписи 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]. Незначительные детали, но вы получите ошибки во время компиляции, если вы попробуете другой способ.
Здесь я сделал метод немного более универсальным, чем коллекция «равные элементы» - скорее, метод разбивает исходную коллекцию на части всякий раз, когда его проверка последовательных элементов завершается неудачей.
Давайте посмотрим на наш метод в действии:
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))
Работает!
Единственная проблема заключается в том, что у нас вообще нет этих методов, доступных для массивов, поскольку для этого потребуются два неявных преобразования подряд. Есть несколько способов обойти это, включая написание отдельного неявного преобразования для массивов, приведение к 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, !!)