Как применить шаблон enrich-my-library к коллекциям Scala?
Одним из самых мощных шаблонов, доступных в Scala, является шаблон enrich-my-library *, который использует неявные преобразования для добавления методов в существующие классы без необходимости динамического разрешения методов. Например, если мы хотим, чтобы у всех строк был метод spaces подсчитав, сколько у них было пробельных символов, мы могли бы:
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
К сожалению, этот шаблон сталкивается с проблемами при работе с общими коллекциями. Например, был задан ряд вопросов о группировании элементов последовательно с коллекциями. Нет ничего встроенного, что бы работало за один раз, так что это кажется идеальным кандидатом для паттерна enrich-my-library с использованием универсальной коллекции C и универсальный тип элемента 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
}
}
}
кроме, конечно, это не работает. REPL говорит нам:
<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
^
Есть две проблемы: как мы можем получить C[C[A]] из пустого C[A] список (или из воздуха)? И как мы можем получить C[C[A]] обратно из same +: линия вместо Seq[Seq[A]]?
* Ранее известный как pimp-my-library.
3 ответа
Ключом к пониманию этой проблемы является осознание того, что существует два разных способа создания и работы с коллекциями в библиотеке коллекций. Одним из них является интерфейс открытых коллекций со всеми его приятными методами. Другой, который широко используется при создании библиотеки коллекций, но который почти никогда не используется вне ее, - это сборщики.
Наша проблема в обогащении точно такая же, с которой сталкивается сама библиотека коллекций, когда пытается вернуть коллекции одного типа. То есть мы хотим создавать коллекции, но при общей работе у нас нет способа ссылаться на "тот же тип, что коллекция уже есть". Поэтому нам нужны строители.
Теперь вопрос: откуда мы берем наших строителей? Очевидное место от самой коллекции. Это не работает Мы уже решили, переходя к общей коллекции, что мы собираемся забыть тип коллекции. Таким образом, хотя коллекция может возвращать конструктор, который будет генерировать больше коллекций нужного нам типа, он не будет знать, что это за тип.
Вместо этого мы получаем наших строителей из CanBuildFrom последствия, которые плавают вокруг. Они существуют специально для того, чтобы соответствовать типам ввода и вывода и дать вам типизированный компоновщик.
Итак, у нас есть два концептуальных скачка:
- Мы не используем стандартные операции с коллекциями, мы используем компоновщики.
- Мы получаем эти строители из неявного
CanBuildFromс, не из нашей коллекции напрямую.
Давайте посмотрим на пример.
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]]s. Глядя на тип подписи CanBuildFrom, мы видим
CanBuildFrom[-From, -Elem, +To]
Это означает, что CanBuildFrom хочет знать тип коллекции, с которой мы начинаем - в нашем случае это C[A]и затем элементы сгенерированной коллекции и тип этой коллекции. Таким образом, мы заполняем их как неявные параметры cbfcc а также cbfc,
Осознав это, это большая часть работы. Мы можем использовать наши CanBuildFroms, чтобы дать нам строителей (все, что вам нужно сделать, это применить их). И один строитель может создать коллекцию с +=, преобразовать его в коллекцию, с которой он должен быть 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, !!)
Начиная с этого коммита, "обогатить" коллекции Scala намного проще, чем когда Рекс дал свой превосходный ответ. Для простых случаев это может выглядеть так,
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)
который добавляет "тот же тип результата", уважая filterMap операция для всех 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
И для примера из вопроса, решение теперь выглядит так:
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)
Образец сессии 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)
Опять же, обратите внимание, что тот же принцип типа результата соблюдается точно так же, как если бы groupIdentical был прямо определен на GenTraversableLike,
Начиная с этого коммита, магическое заклинание немного изменилось по сравнению с тем, что было, когда Майлз дал свой отличный ответ.
Следующие работы, но это каноническое? Я надеюсь, что один из канонов исправит это. (Вернее, пушки, одно из больших орудий.) Если граница вида - это верхняя граница, вы теряете приложение для Array и String. Кажется, не имеет значения, является ли граница GenTraversableLike или TraversableLike; но IsTraversableLike дает вам 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)
Существует более одного способа снять кожу с девяти жизней. В этой версии говорится, что после преобразования моего источника в GenTraversableLike, если я могу построить результат из GenTraversable, просто сделайте это. Мне не интересен мой старый репр.
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)
Эта первая попытка включает в себя уродливое преобразование Repr в 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)