Como aplico o padrão enriquecer minha biblioteca às collections Scala?

Um dos padrões mais poderosos disponíveis no Scala é o pattern enrich-my-library *, que usa conversões implícitas para adicionar methods a classs existentes sem exigir resolução dinâmica de método. Por exemplo, se desejássemos que todas as strings tivessem os spaces methods que contavam quantos caracteres de espaço em branco eles tinham, poderíamos:

 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 

Infelizmente, esse padrão apresenta problemas ao lidar com collections genéricas. Por exemplo, várias perguntas foram feitas sobre o agrupamento de itens sequencialmente com collections . Não há nada embutido que funcione de uma só vez, então isso parece ser um candidato ideal para o padrão enriquecer minha biblioteca usando uma coleção genérica C e um tipo de elemento genérico 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 } } } 

exceto, claro, isso não funciona . O REPL nos diz:

 :12: error: not found: value C if (ca.isEmpty) C.empty[C[A]] ^ :16: error: type mismatch; found : Seq[Seq[A]] required: C[C[A]] same +: (new SequentiallyGroupingCollection(rest)).groupIdentical ^ 

Existem dois problemas: como obtemos um C[C[A]] de uma lista C[A] vazia (ou do ar rarefeito)? E como obtemos um C[C[A]] volta da same +: linha same +: vez de um Seq[Seq[A]] ?

* Anteriormente conhecido como pimp-my-library.

A chave para entender esse problema é perceber que existem duas maneiras diferentes de construir e trabalhar com collections na biblioteca de collections. Uma é a interface de collections públicas com todos os seus methods agradáveis. O outro, que é usado extensivamente na criação da biblioteca de collections, mas que quase nunca é usado fora dela, são os construtores.

Nosso problema no enriquecimento é exatamente o mesmo que a própria biblioteca de collections enfrenta ao tentar retornar collections do mesmo tipo. Ou seja, queremos construir collections, mas quando trabalhamos genericamente, não temos como nos referir ao “mesmo tipo que a coleção já é”. Então precisamos de construtores .

Agora a questão é: de onde tiramos nossos construtores? O lugar óbvio é da própria coleção. Isso não funciona . Já decidimos, ao mudar para uma coleção genérica, que íamos esquecer o tipo da coleção. Assim, embora a coleção possa retornar um construtor que geraria mais collections do tipo que queremos, ela não saberia qual era o tipo.

Em vez disso, obtemos nossos construtores de CanBuildFrom implícitos que estão flutuando. Eles existem especificamente para o propósito de combinar os tipos de input e saída e fornecer um construtor apropriadamente typescript.

Então, nós temos dois saltos conceituais para fazer:

  1. Não estamos usando operações de collections padrão, estamos usando construtores.
  2. CanBuildFrom esses construtores a partir de CanBuildFrom implícito, não da nossa coleção diretamente.

Vamos ver um exemplo.

 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) } 

Vamos desmontar isso. Primeiro, para construir a coleção de collections, sabemos que precisaremos construir dois tipos de collections: C[A] para cada grupo e C[C[A]] que reúne todos os grupos. Assim, precisamos de dois construtores, um que tome A e construa C[A] s, e um que tome C[A] s e construa C[C[A]] s. Olhando para a assinatura do tipo CanBuildFrom , vemos

 CanBuildFrom[-From, -Elem, +To] 

o que significa que CanBuildFrom quer saber o tipo de coleção que estamos começando - no nosso caso, é C[A] e, em seguida, os elementos da coleção gerada e o tipo dessa coleção. Então nós os preenchemos como parâmetros implícitos cbfcc e cbfc .

Tendo percebido isso, isso é a maior parte do trabalho. Podemos usar nosso CanBuildFrom s para nos fornecer construtores (tudo que você precisa fazer é aplicá-los). E um construtor pode construir uma coleção com += , convertê-lo para a coleção que deveria estar com result e esvaziar-se e estar pronto para começar de novo com clear . Os construtores começam vazios, o que resolve nosso primeiro erro de compilation e, como estamos usando construtores em vez de recursivos, o segundo erro também desaparece.

Um último pequeno detalhe - além do algoritmo que realmente faz o trabalho - está na conversão implícita. Note que usamos new GroupingCollection[A,C] não [A,C[A]] . Isso ocorre porque a declaração de class era para C com um parâmetro, que é preenchido com o A passado para ele. Então nós apenas entregamos o tipo C , e deixamos criar C[A] partir dele. Detalhe menor, mas você receberá erros de compilation se tentar de outra maneira.

Aqui, tornei o método um pouco mais genérico do que a coleção "elementos iguais" - em vez disso, o método separa a coleção original sempre que o teste de elementos sequenciais falha.

Vamos ver nosso método em ação:

 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)) 

Funciona!

O único problema é que, em geral, não temos esses methods disponíveis para matrizes, pois isso exigiria duas conversões implícitas em sequência. Há várias maneiras de contornar isso, incluindo escrever uma conversão implícita separada para matrizes, conversão para WrappedArray e assim por diante.


Edit: A minha abordagem favorecida para lidar com matrizes e seqüências de caracteres e tal é tornar o código ainda mais genérico e, em seguida, usar conversões implícitas apropriadas para torná-los mais específicos novamente de tal forma que as matrizes funcionem também. Neste caso particular:

 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 } } 

Aqui nós adicionamos um implícito que nos dá um Iterable[A] de C maioria das collections isso será apenas a identidade (por exemplo, List[A] já é um Iterable[A] ), mas para matrizes será um conversão implícita real. E, conseqüentemente, descartamos o requisito de que C[A] <: Iterable[A] - basicamente, fizemos o requisito de <% explicit, para que possamos usá-lo explicitamente à vontade, em vez de ter o preenchimento do compilador para nós. Além disso, relaxamos a restrição de que nossa coleção de collections é C[C[A]] vez disso, é qualquer D[C] , que iremos preencher mais tarde para ser o que queremos. Como vamos preencher isso mais tarde, subimos para o nível da class em vez do nível do método. Caso contrário, é basicamente o mesmo.

Agora a questão é como usar isso. Para collections regulares, podemos:

 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) } 

onde agora conectamos C[A] para C e C[C[A]] para D[C] . Observe que precisamos dos tipos genéricos explícitos na chamada para o new GroupingCollection modo que ele possa manter diretamente quais tipos correspondem a quais. Graças ao implicit c2i: C[A] => Iterable[A] , isso manipula automaticamente as matrizes.

Mas espere, e se quisermos usar strings? Agora estamos com problemas, porque você não pode ter uma "string de strings". É aqui que a abstração extra ajuda: podemos chamar D algo que é adequado para armazenar strings. Vamos escolher Vector e fazer o seguinte:

 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 ) } 

Precisamos de um novo CanBuildFrom para lidar com a construção de um vetor de strings (mas isso é realmente fácil, já que precisamos apenas chamar Vector.newBuilder[String] ), e então precisamos preencher todos os tipos para que o GroupingCollection seja typescript de forma sensata. Note que nós já temos flutuando em volta de um [String,Char,String] CanBuildFrom, então as strings podem ser feitas a partir de collections de chars.

Vamos experimentar:

 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, !!) 

A partir disso , é muito mais fácil “enriquecer” as collections Scala do que quando Rex deu sua excelente resposta. Para casos simples, pode ser assim,

 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) 

que adiciona um “mesmo tipo de resultado” respeitando a operação filterMap para todos os GenTraversableLike s,

 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 

E para o exemplo da pergunta, a solução agora parece,

 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) 

Sessão REPL de amostra,

 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) 

Novamente, observe que o mesmo princípio de tipo de resultado foi observado exatamente da mesma maneira que teria sido se groupIdentical tivesse sido definido diretamente em GenTraversableLike .

A partir deste compromisso, o encantamento mágico é ligeiramente diferente do que foi quando Miles deu sua excelente resposta.

Os seguintes trabalhos, mas é canônico? Espero que um dos cânones corrija. (Ou melhor, canhões, uma das grandes armas.) Se o limite da vista for um limite superior, você perderá o aplicativo para Array e String. Não parece importar se o limite é GenTraversableLike ou TraversableLike; mas IsTraversableLike dá-lhe um 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) 

Há mais de uma maneira de esfolar um gato com nove vidas. Esta versão diz que uma vez que minha fonte é convertida em um GenTraversableLike, desde que eu possa construir o resultado do GenTraversable, apenas faça isso. Não estou interessado em meu antigo 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) 

Esta primeira tentativa inclui uma conversão feia de Repr para 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)