¿Cómo aplico el patrón enriquecer mi biblioteca a las colecciones de Scala?

https://stackoverflow.com/questions/5410846

29-10-2019
|

Pregunta

Uno de los patrones más poderosos disponibles en Scala es el patrón enrich-my-library*, que utiliza conversiones implícitas para aparecer para agregar métodos a clases existentes sin requerir resolución de método dinámico.Por ejemplo, si quisiéramos que todas las cadenas tuvieran el método spaces Contando cuántos espacios en blanco tenían, podrí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

Desafortunadamente, este patrón presenta problemas cuando se trata de colecciones genéricas.Por ejemplo, se han formulado varias preguntas sobre agrupar elementos secuencialmente con colecciones.No hay nada integrado que funcione de una sola vez, por lo que parece un candidato ideal para el patrón enriquecer mi biblioteca utilizando una colección genérica. C y un 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
    }
  }
}

excepto, por supuesto, que no funciona.La REPL nos dice:

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

Hay dos problemas:¿Cómo conseguimos un C[C[A]] de un vacío C[A] lista (o de la nada)?¿Y cómo conseguimos un C[C[A]] de regreso del same +: línea en lugar de una Seq[Seq[A]]?

*^{Anteriormente conocido como proxeneta-mi-biblioteca.}

Solución

La clave para entender este problema es darse cuenta de que hay dos formas diferentes de crear y trabajar con colecciones en la biblioteca de colecciones.Una es la interfaz de colecciones públicas con todos sus buenos métodos.El otro, que se utiliza ampliamente en creando Las colecciones de la biblioteca, pero que casi nunca se utilizan fuera de ella, son las de los constructores.

Nuestro problema al enriquecer es exactamente el mismo al que se enfrenta la propia biblioteca de colecciones cuando intenta devolver colecciones del mismo tipo.Es decir, queremos crear colecciones, pero cuando trabajamos de forma genérica, no tenemos una forma de referirnos al "mismo tipo que ya es la colección".Así que necesitamos constructores.

Ahora la pregunta es:¿De dónde sacamos a nuestros constructores?El lugar obvio es la propia colección. esto no funciona.Ya decidimos, al pasar a una colección genérica, que íbamos a olvidarnos del tipo de colección.Entonces, aunque la colección podría devolver un constructor que generaría más colecciones del tipo que queremos, no sabría cuál es el tipo.

En cambio, obtenemos a nuestros constructores de CanBuildFrom implícitos que están flotando por ahí.Estos existen específicamente con el propósito de hacer coincidir los tipos de entrada y salida y brindarle un generador con el tipo apropiado.

Entonces, tenemos dos saltos conceptuales que dar:

No utilizamos operaciones de recopilación estándar, utilizamos constructores.
Obtenemos estos constructores de forma implícita. CanBuildFroms, no directamente de nuestra colección.

Veamos un ejemplo.

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

Desarmemos esto.Primero, para crear la colección de colecciones, sabemos que necesitaremos crear dos tipos de colecciones: C[A] para cada grupo y C[C[A]] que reúne a todos los grupos.Por lo tanto, necesitamos dos constructores, uno que tome As y construye C[A]s, y uno que toma C[A]s y construye C[C[A]]s.Mirando la firma tipográfica de CanBuildFrom, vemos

CanBuildFrom[-From, -Elem, +To]

lo que significa que CanBuildFrom quiere saber con qué tipo de colección estamos comenzando; en nuestro caso, es C[A], y luego los elementos de la colección generada y el tipo de esa colección.Entonces los completamos como parámetros implícitos. cbfcc y cbfc.

Habiendo comprendido esto, esa es la mayor parte del trabajo.Podemos usar nuestro CanBuildFroms para darnos constructores (todo lo que necesitas hacer es aplicarlos).Y un constructor puede crear una colección con +=, conviértalo a la colección con la que se supone que estará en última instancia. result, y vaciarse y estar listo para comenzar de nuevo con clear.Los constructores comienzan vacíos, lo que resuelve nuestro primer error de compilación y, dado que usamos constructores en lugar de recursividad, el segundo error también desaparece.

Un último pequeño detalle, además del algoritmo que realmente hace el trabajo, está en la conversión implícita.Tenga en cuenta que utilizamos new GroupingCollection[A,C] no [A,C[A]].Esto se debe a que la declaración de clase era para C con un parámetro, que él mismo rellena con el A pasó a ello.Así que simplemente le damos el tipo C, y dejar que cree C[A] fuera de el.Detalles menores, pero obtendrá errores en tiempo de compilación si intenta de otra manera.

Aquí, he hecho el método un poco más genérico que la colección de "elementos iguales"; más bien, el método separa la colección original cada vez que falla la prueba de elementos secuenciales.

Veamos nuestro método en acción:

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!

El único problema es que, en general, no tenemos estos métodos disponibles para matrices, ya que eso requeriría dos conversiones implícitas seguidas.Hay varias formas de solucionar esto, incluida la escritura de una conversión implícita separada para matrices, la conversión a WrappedArray, etcétera.

Editar:Mi enfoque favorito para tratar con matrices y cadenas es hacer que el código sea uniforme. más genérico y luego usar conversiones implícitas apropiadas para hacerlos más específicos nuevamente de tal manera que las matrices también funcionen.En este 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
  }
}

Aquí hemos agregado un implícito que nos da una Iterable[A] de C--para la mayoría de las colecciones, esta será solo la identidad (p. ej. List[A] ya es un Iterable[A]), pero para las matrices será una conversión implícita real.Y, en consecuencia, hemos eliminado el requisito de que C[A] <: Iterable[A]--básicamente acabamos de hacer el requisito de <% explícito, por lo que podemos usarlo explícitamente a voluntad en lugar de que el compilador lo complete por nosotros.Además, hemos relajado la restricción de que nuestra colección de colecciones sea C[C[A]]--en cambio, es cualquiera D[C], que rellenaremos más adelante para que quede lo que queremos.Como vamos a completar esto más adelante, lo hemos elevado al nivel de clase en lugar del nivel de método.Por lo demás, es básicamente lo mismo.

Ahora la pregunta es cómo usar esto.Para colecciones 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)
}

donde ahora nos enchufamos C[A] para C y C[C[A]] para D[C].Tenga en cuenta que necesitamos los tipos genéricos explícitos en la llamada a new GroupingCollection para que pueda mantener claro qué tipos corresponden a qué.Gracias a implicit c2i: C[A] => Iterable[A], esto maneja automáticamente las matrices.

Pero espera, ¿y si queremos usar cadenas?Ahora estamos en problemas, porque no se puede tener una "cadena de cuerdas".Aquí es donde ayuda la abstracción adicional:podemos llamar D algo que sea adecuado para sujetar cuerdas.vamos a elegir Vector, y haga lo siguiente:

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

Necesitamos un nuevo CanBuildFrom para manejar la construcción de un vector de cadenas (pero esto es realmente fácil, ya que sólo necesitamos llamar Vector.newBuilder[String]), y luego necesitamos completar todos los tipos para que el GroupingCollection está escrito con sensatez.Tenga en cuenta que ya tenemos flotando alrededor de un [String,Char,String] CanBuildFrom, por lo que se pueden crear cadenas a partir de colecciones de caracteres.

Probémoslo:

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

Otros consejos

A partir de este compromiso Es mucho más fácil "enriquecer" las colecciones de Scala que cuando Rex dio su excelente respuesta.Para casos simples podría verse así,

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 agrega un "mismo tipo de resultado" respetando filterMap operación a todos 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

Y para el ejemplo de la pregunta, la solución ahora 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)

Sesión REPL de muestra,

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)

Nuevamente, tenga en cuenta que el mismo principio de tipo de resultado se ha observado exactamente de la misma manera que se habría groupIdentical sido definido directamente en GenTraversableLike.

A partir de este compromiso El encantamiento mágico ha cambiado ligeramente de lo que era cuando Miles dio su excelente respuesta.

Lo siguiente funciona, pero ¿es canónico?Espero que uno de los cánones lo corrija.(O más bien, cañones, una de las armas grandes). Si el límite de vista es un límite superior, pierde la aplicación a Array y String.No parece importar si el límite es GenTraversableLike o TraversableLike;pero IsTraversableLike te da un 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)

Hay más de una forma de despellejar a un gato con nueve vidas.Esta versión dice que una vez que mi fuente se convierta a GenTraversableLike, siempre que pueda generar el resultado a partir de GenTraversable, simplemente haga eso.No estoy interesado en mi antiguo 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)

Este primer intento incluye una fea conversión de Repr a 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 bajo: CC-BY-SA con atribución

No afiliado a StackOverflow