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

collections enrich-my-library

Question

Uno de los patrones más potentes disponibles en Scala es el patrón enrich-my-library *, que utiliza conversiones implícitas para que parezca agregar métodos a las clases existentes sin requerir una resolución dinámica de métodos. Por ejemplo, si deseamos que todas las cadenas tengan los spaces método que contaron la cantidad de caracteres en espacios en blanco que tenían, pudimos:

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

Lamentablemente, este patrón tiene problemas cuando se trata de colecciones genéricas. Por ejemplo, se han formulado una serie de preguntas sobre la agrupación de elementos secuencialmente con colecciones . No hay nada incorporado que funcione de una sola vez, por lo que parece un candidato ideal para el patrón enriquecer mi biblioteca usando una colección genérica C y un elemento genérico tipo 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, no funciona . El 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 obtenemos una C[C[A]] de una lista C[A] vacía (o de la nada)? ¿Y cómo obtenemos una C[C[A]] atrás de la same +: línea same +: lugar de una Seq[Seq[A]] ?

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

Answer 1

A partir de este compromiso , es mucho más fácil "enriquecer" las colecciones de Scala de lo que era 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 la operación filterMap a todos los GenTraversableLike ,

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)

Muestra de la sesión 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)

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

Answer 2

A partir de este compromiso, el hechizo mágico cambia 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, uno de los grandes). Si la vista enlazada es un límite superior, pierdes la aplicación a Array y String. No parece importar si el límite es GenTraversableLike o TraversableLike; pero IsTraversableLike le 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 convierte a GenTraversableLike, siempre que pueda generar el resultado de GenTraversable, simplemente hazlo. No estoy interesado en mi viejo 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)

Answer 3

La clave para entender este problema es darse cuenta de que hay dos maneras diferentes de construir 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 usa ampliamente para crear la biblioteca de colecciones, pero que casi nunca se usa fuera de él, son los constructores.

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

Ahora la pregunta es: ¿de dónde sacamos a nuestros constructores? El lugar obvio es de la colección en sí. Esto no funciona Ya decidimos, al pasar a una colección genérica, que íbamos a olvidar el tipo de la colección. Entonces, aunque la colección podría devolver un generador que generaría más colecciones del tipo que queremos, no sabría de qué tipo era.

En cambio, obtenemos nuestros constructores de CanBuildFrom implicits que están flotando. Estos existen específicamente con el propósito de hacer coincidir los tipos de entrada y salida y proporcionarle un constructor de tipo apropiado.

Entonces, tenemos dos saltos conceptuales para hacer:

1. No estamos usando operaciones de colecciones estándar, estamos usando constructores.
2. Obtenemos estos constructores de CanBuildFrom s implícitos, no de nuestra colección directamente.

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

Vamos a desmontar esto. Primero, para construir la colección de colecciones, sabemos que necesitaremos construir dos tipos de colecciones: C[A] para cada grupo y C[C[A]] que reúna a todos los grupos. Por lo tanto, necesitamos dos constructores, uno que tome A s y construya C[A] s, y uno que tome C[A] sy construya C[C[A]] s. Mirando la firma de tipo de CanBuildFrom , vemos

CanBuildFrom[-From, -Elem, +To]

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

Habiéndose dado cuenta de esto, eso es la mayor parte del trabajo. Podemos usar nuestro CanBuildFrom para darnos constructores (todo lo que necesitas hacer es aplicarlos). Y un constructor puede construir una colección con += , convertirla a la colección que se supone que finalmente debe tener el result , vaciarla y estar listo para comenzar nuevamente con la clear . Los constructores comienzan vacíos, lo que soluciona nuestro primer error de compilación, y como usamos constructores en lugar de recursividad, el segundo error también desaparece.

Un último pequeño detalle, aparte del algoritmo que realmente hace el trabajo, está en la conversión implícita. Tenga en cuenta que usamos 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 se rellena con la A pasó. Así que solo le damos el tipo C y dejamos que cree C[A] . Detalles menores, pero obtendrá errores de tiempo de compilación si intenta de otra manera.

Aquí, hice el método un poco más genérico que la colección de "elementos iguales", más bien, el método corta la colección original cuando falla la prueba de los 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 las matrices, ya que eso requeriría dos conversiones implícitas en una fila. Hay varias formas de evitar esto, incluida la escritura de una conversión implícita separada para matrices, conversión a WrappedArray , y así sucesivamente.

Editar: Mi enfoque preferido para manejar matrices y cadenas de caracteres es hacer que el código sea aún más genérico y luego usar las conversiones implícitas apropiadas para volverlas más específicas de nuevo, de modo 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 un Iterable[A] de C mayoría de las colecciones, esta solo será la identidad (por ejemplo, la List[A] ya es 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 hemos hecho que el requisito de <% explícito, por lo que podemos usarlo explícitamente a voluntad en lugar de tener el relleno del compilador para nosotros. Además, hemos relajado la restricción de que nuestra colección de colecciones es C[C[A]] , en cambio, es cualquier D[C] , que luego completaremos para que sea lo que queremos. Como vamos a completar esto más adelante, lo hemos llevado al nivel de clase en lugar del nivel de método. De lo contrario, 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 conectamos C[A] para C y C[C[A]] para D[C] . Tenga en cuenta que sí necesitamos los tipos genéricos explícitos en la llamada a la new GroupingCollection para que pueda seguir directamente qué tipos corresponden a qué. Gracias al implicit c2i: C[A] => Iterable[A] , este maneja automáticamente las matrices.

Pero espera, ¿y si queremos usar cadenas? Ahora estamos en problemas, porque no puedes tener una "cadena de cuerdas". Aquí es donde ayuda la abstracción adicional: podemos llamar D algo que sea adecuado para contener cadenas. Vamos a elegir Vector , y hagamos 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 solo necesitamos llamar a Vector.newBuilder[String] ), y luego tenemos que completar todos los tipos para que GroupingCollection sea mecanografiado sensatamente. Tenga en cuenta que ya tenemos flotando alrededor de [String,Char,String] CanBuildFrom, por lo que las cadenas se pueden hacer 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, !!)