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

Uno de los patrones más poderosos disponibles en Scala es el patrón enrich-my-library *, que usa conversiones implícitas para parecer que agregan métodos a clases existentes sin requerir una resolución dinámica de métodos. Por ejemplo, si quisiéramos que todas las cadenas tuvieran el método spacesque contara cuántos caracteres de 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 tiene problemas cuando se trata de colecciones genéricas. Por ejemplo, se han formulado varias preguntas sobre la agrupación de 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 Cy 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 . 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 un C[C[A]]de una C[A]lista vacía (o de la nada)? ¿Y cómo obtenemos un C[C[A]]respaldo de la same +:línea en lugar de un Seq[Seq[A]]?

* ^{Anteriormente conocido como pimp-my-library.}

La clave para comprender este problema es darse cuenta de que hay dos formas diferentes de construir y trabajar con colecciones en la biblioteca de colecciones. Uno es la interfaz de colecciones públicas con todos sus buenos métodos. El otro, que se utiliza ampliamente en la creación de la biblioteca de colecciones, pero que casi nunca se utiliza fuera de ella, son los constructores.

Nuestro problema de enriquecimiento es exactamente el mismo que enfrenta la propia biblioteca de colecciones cuando intenta devolver colecciones del mismo tipo. Es decir, queremos construir colecciones, pero cuando trabajamos de forma genérica, no tenemos forma de referirnos al "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 propia colección. Esto no funciona . Ya decidimos, al pasar a una colección genérica, que nos íbamos a olvidar 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 era el tipo.

En cambio, obtenemos nuestros constructores de los CanBuildFromimplícitos que flotan alrededor. Estos existen específicamente con el propósito de hacer coincidir los tipos de entrada y salida y brindarle un constructor debidamente tipificado.

Entonces, tenemos dos saltos conceptuales que dar:

1. No estamos usando operaciones de cobranza estándar, estamos usando constructores.
2. Obtenemos estos constructores de CanBuildFroms implícitos , 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 construir la colección de colecciones, sabemos que necesitaremos construir dos tipos de colecciones: C[A]para cada grupo, y C[C[A]]eso reúne a todos los grupos. Por lo tanto, necesitamos dos constructores, uno que toma Asy construye C[A]s, y otro que toma C[A]sy construye 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 comenzando, en nuestro caso, es C[A], y luego los elementos de la colección generada y el tipo de esa colección. Así que los completamos como parámetros implícitos cbfccy cbfc.

Habiéndome dado cuenta de esto, eso es la mayor parte del trabajo. Podemos usar nuestros CanBuildFroms para darnos constructores (todo lo que necesita hacer es aplicarlos). Y un constructor puede crear una colección +=, convertirla en la colección con la que se supone que debe estar en última instancia result, vaciarse y estar listo para empezar de nuevo clear. Los constructores comienzan vacíos, lo que resuelve nuestro primer error de compilación, y dado que estamos usando 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. En cuenta que utilizamos new GroupingCollection[A,C]no [A,C[A]]. Esto se debe a que la declaración de la clase fue para Ccon un parámetro, que lo llena él mismo con el Apasado. Así que le damos el tipo Cy dejamos que se cree a C[A]partir de él. 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 corta la colección original cada vez que falla su 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 este problema, incluida la escritura de una conversión implícita separada para matrices, la conversión a WrappedArray, etc.

Editar: Mi enfoque favorito para tratar con matrices y cadenas es hacer que el código sea aún más genérico y luego usar las conversiones implícitas apropiadas para hacerlas más específicas 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 un Iterable[A]desde C- para la mayoría de las colecciones, esto será solo la identidad (por ejemplo, List[A]ya es un Iterable[A]), pero para los arreglos 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 <%explícito el requisito para que podamos 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 es C[C[A]], en cambio, es cualquiera D[C], que completaremos más adelante para que sea lo que queremos. Debido a que vamos a completar esto más adelante, lo subimos 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 Cy C[C[A]]para D[C]. Tenga en cuenta que necesitamos los tipos genéricos explícitos en la llamada a new GroupingCollectionpara poder aclarar 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 puedes tener una "cadena de cuerdas". Aquí es donde la abstracción adicional ayuda: podemos llamar a Dalgo que sea adecuado para contener cadenas. Escojamos Vectory 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 una nueva CanBuildFrompara manejar la construcción de un vector de cadenas (pero esto es realmente fácil, ya que solo necesitamos llamar Vector.newBuilder[String]), y luego necesitamos completar todos los tipos para que GroupingCollectionse escriba con sensatez. Tenga en cuenta que ya tenemos flotando alrededor de un [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, !!)

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" con respecto a la filterMapoperación a todos los 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 se ve así,

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 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 el mismo principio de tipo de resultado se ha observado exactamente de la misma manera en que se hubiera groupIdenticaldefinido directamente GenTraversableLike.

A partir de este compromiso el encantamiento 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, una de las armas grandes). Si el límite de la 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 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 convierta a GenTraversableLike, siempre que pueda generar el resultado desde GenTraversable, simplemente hágalo. 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 conversión fea 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)