Como aplico o padrão enriquecer minha biblioteca a coleções Scala?

Um dos padrões mais poderosos disponíveis em Scala é o padrão enriquecer minha biblioteca *, que usa conversões implícitas para aparentar adicionar métodos a classes existentes sem exigir resolução de método dinâmico. Por exemplo, se desejássemos que todas as strings tivessem o método spacesque contasse quantos caracteres de espaço em branco elas 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 tem problemas ao lidar com coleções genéricas. Por exemplo, várias perguntas foram feitas sobre o agrupamento de itens sequencialmente com coleções . Não há nada integrado que funcione de uma só vez, então este parece um candidato ideal para o padrão enriquecer minha biblioteca usando uma coleção genérica Ce 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, que não funciona . O REPL nos diz:

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

Existem dois problemas: como obtemos um C[C[A]]de uma C[A]lista vazia (ou do nada)? E como obtemos um C[C[A]]retorno da same +:linha em 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 coleções na biblioteca de coleções. Um é a interface de coleções públicas com todos os seus métodos interessantes. O outro, que é amplamente utilizado na criação da biblioteca de coleções, mas que quase nunca é usado fora dela, são os construtores.

Nosso problema de enriquecimento é exatamente o mesmo que a própria biblioteca de coleções enfrenta ao tentar retornar coleções do mesmo tipo. Ou seja, queremos construir coleções, mas ao trabalhar genericamente, não temos como nos referir a "o mesmo tipo que a coleção já é". Portanto, precisamos de construtores .

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

Em vez disso, obtemos nossos construtores de CanBuildFromimplícitos que estão flutuando. Eles existem especificamente para o propósito de combinar os tipos de entrada e saída e fornecer a você um construtor apropriadamente tipado.

Portanto, temos dois saltos conceituais a dar:

1. Não estamos usando operações de coleções padrão, estamos usando construtores.
2. Obtemos esses construtores de CanBuildFroms implícitos , não diretamente de nossa coleção.

Vejamos 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 coleções, sabemos que precisaremos construir dois tipos de coleções: C[A]para cada grupo, e C[C[A]]que reúne todos os grupos. Portanto, precisamos de dois construtores, um que obtém se Aconstrói se C[A]e outro que obtém se C[A]constrói C[C[A]]s. Olhando para a assinatura de tipo de CanBuildFrom, vemos

CanBuildFrom[-From, -Elem, +To]

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

Tendo percebido isso, é a maior parte do trabalho. Podemos usar nossos CanBuildFroms para nos fornecer construtores (tudo que você precisa fazer é aplicá-los). E um construtor pode construir uma coleção +=, convertê-la na coleção com a qual ela deveria estar result, esvaziar-se e estar pronto para começar de novo clear. Os construtores começam vazios, o que resolve nosso primeiro erro de compilação e, como estamos usando construtores em vez de recursão, 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 da classe foi para Ccom um parâmetro, que ela própria preenche com o Apassado para ela. Então, simplesmente entregamos o tipo Ce o deixamos criar a C[A]partir dele. Pequenos detalhes, mas você obterá erros de tempo de compilação se tentar de outra maneira.

Aqui, tornei o método um pouco mais genérico do que a coleção de "elementos iguais" - em vez disso, o método separa a coleção original sempre que seu 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 métodos disponíveis para arrays, pois isso exigiria duas conversões implícitas em uma linha. Há várias maneiras de contornar isso, incluindo escrever uma conversão implícita separada para arrays, converter para WrappedArraye assim por diante.

Edit: Minha abordagem preferida para lidar com matrizes e strings e outros é tornar o código ainda mais genérico e, em seguida, usar as conversões implícitas apropriadas para torná-las mais específicas novamente, de modo que as matrizes também funcionem. 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, adicionamos um implícito que nos dá um Iterable[A]from C--para a maioria das coleções, essa será apenas a identidade (por exemplo, List[A]já é um Iterable[A]), mas para matrizes será uma conversão implícita real. E, conseqüentemente, deixamos de lado o requisito de que C[A] <: Iterable[A]- basicamente tornamos o requisito de <%explícito, para que possamos usá-lo explicitamente à vontade, em vez de ter o compilador preenchê-lo para nós. Além disso, relaxamos a restrição de que nossa coleção de coleções é - ao C[C[A]]invés, é qualquer D[C], que preencheremos mais tarde para ser o que queremos. Como vamos preencher isso mais tarde, nós o elevamos para o nível da classe em vez do nível do método. Caso contrário, é basicamente o mesmo.

Agora, a questão é como usar isso. Para coleções 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 ligamos C[A]para Ce C[C[A]]para D[C]. Observe que precisamos dos tipos genéricos explícitos na chamada para new GroupingCollectionpara que possamos determinar quais tipos correspondem a quais. Graças ao implicit c2i: C[A] => Iterable[A], isso lida automaticamente com arrays.

Mas espere, e se quisermos usar strings? Agora estamos com problemas, porque você não pode ter uma "seqüência de cordas". É aqui que a abstração extra ajuda: podemos chamar Dalgo que seja adequado para conter strings. Vamos escolher Vectore 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 CanBuildFrompara lidar com a construção de um vetor de strings (mas isso é realmente fácil, já que só precisamos chamar Vector.newBuilder[String]), e então precisamos preencher todos os tipos para que o GroupingCollectionseja digitado de maneira sensata. Observe que já temos um [String,Char,String]CanBuildFrom flutuando , então strings podem ser feitas de coleções 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 desse commit , é muito mais fácil "enriquecer" as coleções do 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 filterMapoperação para todos os 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

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 groupIdenticalsido definido diretamente em GenTraversableLike.

A partir deste commit, o encantamento mágico é ligeiramente alterado em relação ao que era quando Miles deu sua excelente resposta.

O seguinte funciona, mas é canônico? Espero que um dos cânones o corrija. (Ou melhor, canhões, uma das grandes armas.) Se o limite da vista for um limite superior, você perderá a aplicação para Array e String. Não parece importar se o limite é GenTraversableLike ou TraversableLike; mas IsTraversableLike oferece 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 seja convertida em GenTraversableLike, contanto que eu possa construir o resultado de GenTraversable, basta fazer isso. Não estou interessado no 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)

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