Как мне применить шаблон enrich-my-library к коллекциям Scala?

Question

Одним из самых мощных шаблонов, доступных в 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.}

Answer 1

Ключом к пониманию этой проблемы является осознание того, что существуют два разных способа создания коллекций и работы с ними в библиотеке коллекций.Одним из них является интерфейс публичных коллекций со всеми его приятными методами.Другой, который широко используется в создание библиотека коллекций, которые почти никогда не используются за ее пределами, - это builders.

Наша проблема с обогащением - это точно такая же проблема, с которой сталкивается сама библиотека коллекций при попытке вернуть коллекции того же типа.То есть мы хотим создавать коллекции, но при работе в общем виде у нас нет способа ссылаться на "тот же тип, что и коллекция".Поэтому нам нужно строители.

Теперь вопрос в том,:откуда мы берем наших строителей?Очевидное место - из самой коллекции. Это не сработает.Мы уже решили, переходя к универсальной коллекции, что забудем о типе коллекции.Таким образом, даже если коллекция могла бы вернуть конструктор, который сгенерировал бы больше коллекций нужного нам типа, он не знал бы, что это за тип.

Вместо этого мы привлекаем наших строителей из CanBuildFrom импликации, которые витают вокруг да около.Они существуют специально для сопоставления типов ввода и вывода и предоставления вам соответствующим образом типизированного конструктора.

Итак, нам предстоит совершить два концептуальных скачка:

1. Мы не используем стандартные операции с коллекциями, мы используем конструкторы.
2. Мы получаем эти конструкторы из implicit 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.

Осознав это, я понял, что это большая часть работы.Мы можем использовать наши 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, !!)

Answer 2

Что касается этого коммита , то коллекции Scala намного легче «обогатить», чем когда Рекс давалотличный ответ.В простых случаях это может выглядеть так:

родовое слово

который добавляет "одинаковый тип результата" с учетом операции сгенерированного кодового кода ко всем сгенерированным кодовым кодам,

родовое слово

И для примера из вопроса решение теперь выглядит так:

родовое слово

Пример сеанса REPL,

родовое слово

Опять же, обратите внимание, что тот же принцип типа результата соблюдался точно так же, как если бы filterMap был непосредственно определен в GenTraversableLike.

Answer 3

Начиная с этого коммита , магическое заклинание немного изменилось по сравнению с тем, что было, когда Майлз дал свой превосходный ответ.

Следующее работает, но является ли оно каноническим?Надеюсь один из канонов поправит.(Или, скорее, пушки, одно из главных орудий.) Если граница обзора является верхней границей, вы теряете применение для Array и String.Кажется, не имеет значения, является ли граница GenTraversableLike или TraversableLike;но IsTraversableLike дает вам GenTraversableLike.

родовое слово

Есть несколько способов снять шкуру с кошки с девятью жизнями.В этой версии говорится, что как только мой источник будет преобразован в GenTraversableLike, пока я могу построить результат из GenTraversable, просто сделайте это.Меня не интересует мой старый Repr.

родовое слово

Эта первая попытка включает ужасное преобразование Repr в GenTraversableLike.

родовое слово