Как применить шаблон обогащения моей библиотеки к коллекциям Scala?

Один из самых мощных моделей , доступных в Scala является обогащает-мою библиотеку * шаблон, который использует неявные преобразования , чтобы появиться , чтобы добавить методы к существующим классам , не требуя разрешения метода динамического. Например, если бы мы хотели, чтобы у всех строк был метод 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.}

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

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

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

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

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

1. Мы не используем стандартные операции с коллекциями, мы используем конструкторы.
2. Мы получаем эти конструкторы из неявных 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]]которая объединяет все группы вместе. Таким образом, нам нужны два компоновщика: один принимает As и строит C[A]s, а другой принимает C[A]s и строит C[C[A]]s. Глядя на подпись типа CanBuildFrom, мы видим

CanBuildFrom[-From, -Elem, +To]

Это означает, что CanBuildFrom хочет знать тип коллекции, с которой мы начинаем - в нашем случае это C[A], а затем элементы созданной коллекции и тип этой коллекции. Поэтому мы заполняем их как неявные параметры cbfccи cbfc.

Осознав это, это большая часть работы. Мы можем использовать наши CanBuildFroms, чтобы дать нам строителей (все, что вам нужно сделать, это применить их). И один строитель может создать коллекцию +=, преобразовать ее в коллекцию, в которой он должен быть в конечном итоге 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]from 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, просто сделайте это. Меня не интересует мой старый Repr.

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)