Ответ 1
Ключом к пониманию этой проблемы является осознание того, что существуют два разных способа создания и работы с коллекциями в библиотеке коллекций. Один из них - это интерфейс публичных коллекций со всеми его хорошими методами. Другие, которые широко используются при создании библиотеки коллекций, но которые почти никогда не используются за ее пределами, являются сборщиками.
Наша проблема в обогащении точно такая же, как и сама библиотека коллекций при попытке возврата коллекций того же типа. То есть мы хотим создавать коллекции, но при работе в общем случае у нас нет способа ссылаться на "тот же тип, что и в коллекции". Поэтому нам нужны строители.
Теперь возникает вопрос: откуда мы берем наших строителей? Очевидное место принадлежит самой коллекции. Это не работает. Мы уже решили, перейдя к общей коллекции, что мы собираемся забыть тип коллекции. Поэтому, даже если коллекция может вернуть построитель, который будет генерировать больше коллекций типа, который нам нужен, он не знал бы, что это за тип.
Вместо этого мы получаем наших сборщиков от CanBuildFrom implicits, которые плавают вокруг. Они существуют специально для сопоставления типов ввода и вывода и предоставления вам типично типизированного построителя.
Итак, у нас есть два концептуальных скачка:
- Мы не используем стандартные операции с коллекциями, мы используем сборщики.
- Мы получаем этих сборщиков из неявных
CanBuildFroms, а не из нашей коллекции напрямую.
Посмотрим на пример.
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] s, а тот, который принимает C[A] и строит C[C[A]] s. Глядя на подпись типа CanBuildFrom, мы видим
CanBuildFrom[-From, -Elem, +To]
что означает, что CanBuildFrom хочет знать тип коллекции, с которой мы начинаем, - в нашем случае это C[A], а затем элементы сгенерированной коллекции и тип этой коллекции. Поэтому мы заполняем их как неявные параметры cbfcc и cbfc.
Понимая это, большая часть работы. Мы можем использовать наш CanBuildFrom, чтобы дать нам строителей (все, что вам нужно сделать, это применить их). И один строитель может создать коллекцию с помощью +=, преобразовать ее в коллекцию, которая, как предполагается, в конечном итоге будет с result, и сама по себе очистится и будет готова снова начать с clear. Строители начинают пустые, что решает нашу первую ошибку компиляции, и поскольку мы используем сборщики вместо рекурсии, вторая ошибка также исчезает.
Одна последняя небольшая деталь, отличная от алгоритма, который фактически выполняет работу, находится в неявном преобразовании. Обратите внимание, что мы используем new GroupingCollection[A,C] not [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, !!)
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, !!)