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

StackOverflow https://stackoverflow.com/questions/5410846

Pergunta

Um dos padrões mais poderosos disponíveis em Scala é o padrão enriquecer minha biblioteca *, que usa conversões implícitas para aparecer para 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 spaces que 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 agrupar itens sequencialmente com coleções . Não há nada integrado que funcione de uma só vez, então isso parece 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, 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 lista vazia de C[A] (ou do nada)? E como obtemos um C[C[A]] de volta da linha same +: em vez de um Seq[Seq[A]]?

* Anteriormente conhecido como pimp-my-library.

Foi útil?

Solução

A chave para entender este 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 legais. O outro, que é usado extensivamente 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 passar 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 dos implícitos CanBuildFrom que estão flutuando. Eles existem especificamente com 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 de nossa coleção diretamente.

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. Assim, precisamos de dois construtores, um que obtém As e cria C[A]s e outro que obtém C[A]s e cria C[C[A]]s. Olhando para a assinatura de tipo de CanBuildFrom, vemos 

CanBuildFrom[-From, -Elem, +To]

o que significa que CanBuildFrom deseja saber o tipo de coleção com o qual 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 cbfcc e 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 com +=, convertê-la na coleção que é suposto ser, em última análise, com result, esvaziar-se e estar pronto para começar novamente com 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. Observe que usamos new GroupingCollection[A,C], não [A,C[A]]. Isso ocorre porque a declaração da classe era para C com um parâmetro, que ela mesma o preenchia com o A passado a ela. Então, apenas fornecemos o tipo C e deixamos que ele crie C[A] 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 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 métodos disponíveis para matrizes, uma vez que isso exigiria duas conversões implícitas em um

fileira. Existem várias maneiras de contornar isso, incluindo escrever uma conversão implícita separada para matrizes, converter para WrappedArray e assim por diante.

Editar: minha abordagem preferida para lidar com matrizes e strings é 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 funcionem Além disso. 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] de C - para a maioria das coleções, isso 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, eliminamos o requisito de C[A] <: Iterable[A] - basicamente apenas 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 é C[C[A]] - em vez disso, é qualquer D[C], que preencheremos mais tarde para ser o que queremos. Como iremos 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 conectamos C[A] para C e C[C[A]] para D[C]. Observe que precisamos dos tipos genéricos explícitos na chamada para new GroupingCollection para que possamos determinar quais tipos correspondem a quais. Graças ao implicit c2i: C[A] => Iterable[A], ele lida automaticamente com matrizes.

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 D de algo adequado para conter 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 só precisamos chamar Vector.newBuilder[String]) e, em seguida, precisamos preencher todos os tipos para que o GroupingCollection seja digitado de maneira adequada . Observe que já flutuamos em torno de um [String,Char,String] CanBuildFrom, portanto, as strings podem ser feitas a partir de coleções de caracteres.

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

Outras dicas

A partir de este commit , é muito mais fácil "enriquecer" as coleções Scala do que era quando Rex deu seuexcelente 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 a 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 se parece com, 

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)

Amostra de sessão 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)

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

A partir de este commit , o encantamento mágico é ligeiramente diferente do 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 para 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)
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top