Comment appliquer le motif enrich-my-library aux collections Scala?

Question

L'un des plus puissants motifs disponibles dans la Scala est l'enrichir ma bibliothèque* le modèle, qui utilise des conversions implicites à apparaître à ajouter des méthodes aux classes existantes, sans exiger la dynamique de la méthode de résolution. Par exemple, si nous avons souhaité que toutes les chaînes avaient la méthode spaces qui a compté combien les espaces qu'ils avaient, nous avons pu:

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

Malheureusement, ce modèle s'exécute en difficulté lorsqu'ils traitent avec des génériques de collections. Par exemple, un certain nombre de questions ont été posées à propos de regroupement d'éléments de manière séquentielle, avec des collections. Il n'y a rien de construit dans les œuvres d'un seul coup, donc cela semble être un candidat idéal pour l'enrichir ma bibliothèque de modèle à l'aide d'une collection générique C et un élément générique de type 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
    }
  }
}

sauf, bien sûr, il ne fonctionne pas. Le REPL nous dit:

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

Il y a deux problèmes: comment pouvons-nous obtenir un C[C[A]] de vide C[A] liste (ou de l'air mince)? Et comment pouvons-nous obtenir un C[C[A]] de retour de l' same +: ligne au lieu d'un Seq[Seq[A]]?

* ^{Anciennement connu sous le pimp-my-bibliothèque.}

Answer 1

La clé de la compréhension de ce problème est de se rendre compte qu'il y a deux façons de construire et de travailler avec des collections dans les collections de la bibliothèque. L'un est le public, les collections de l'interface avec tous ses beaux méthodes. L'autre, qui est largement utilisé dans la création de collections de la bibliothèque, mais qui ne sont presque jamais utilisé en dehors de cela, sont les constructeurs.

Notre problème dans l'enrichissement est exactement la même que les collections de la bibliothèque elle-même les visages lors de la tentative de retour des collections du même type. C'est, nous voulons construire des collections, mais quand on travaille de façon générique, nous n'avons pas un moyen de se référer à "du même type que la collection est déjà". Nous avons donc besoin des constructeurs.

Maintenant, la question est: où pouvons-nous obtenir nos constructeurs? L'endroit évident est de la collection elle-même. Cela ne fonctionne pas. Nous avons déjà décidé, dans le passage à une collection générique, que nous allions oublier le type de la collection. Ainsi, même si la collection pourrait revenir à un constructeur, qui permettrait de générer plus de collections du type que nous voulons, il ne sait pas ce que le type a été.

Au lieu de cela, nous obtenons nos constructeurs de CanBuildFrom implicites qui flottent autour. Il en existe spécialement pour le but de l'appariement d'entrée et de sortie de types et de vous donner de bien tapé builder.

Nous avons donc deux conceptuel des sauts à faire:

1. Nous ne sommes pas en utilisant la norme collections opérations, nous utilisons des constructeurs.
2. Nous obtenons ces bâtisseurs de l'implicite CanBuildFroms, pas de notre collection directement.

Regardons un exemple.

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

Prenons en dehors de cela. Tout d'abord, pour construire la collection de collections, nous savons que nous allons avoir besoin de construire deux types de collections: C[A] pour chaque groupe, et C[C[A]] qui rassemble tous les groupes ensemble. Ainsi, nous avons besoin de deux constructeurs, l'un qui prend As et s'appuie C[A]s, et celui qui prend C[A]s et s'appuie C[C[A]]s. En regardant le type de signature de l' CanBuildFrom, nous voir

CanBuildFrom[-From, -Elem, +To]

ce qui signifie que CanBuildFrom veut savoir le type de collection que nous commençons avec-dans notre cas, c'est C[A], puis les éléments de la collection et le type de cette collection. Nous avons donc de remplir celles-ci en tant que paramètres implicites cbfcc et cbfc.

Ayant pris conscience de cela, c'est la plupart du travail. Nous pouvons utiliser notre CanBuildFroms pour nous donner des constructeurs (tout ce que vous devez faire est de les appliquer). Et un constructeur peut constituer une collection avec +=, le convertir à la collection, il est censé être en fin de compte avec result, et le vide lui-même et être prêt à recommencer avec clear. Les constructeurs de commencer vide, ce qui résout notre première erreur de compilation, et puisque nous sommes à l'aide de constructeurs au lieu de la récursivité, la deuxième erreur va aussi loin.

Un dernier petit détail--autres que l'algorithme qui fait réellement le travail, est dans la conversion implicite. Notez que nous utilisons new GroupingCollection[A,C] pas [A,C[A]]. C'est parce que la déclaration de classe a pour C avec un paramètre, il le remplit de lui-même avec l' A passée. Donc nous avons juste à la main, il le type C, et le laisser créer C[A] . Détail mineur, mais vous obtiendrez des erreurs de compilation si vous essayez une autre façon.

Ici, j'ai fait la méthode un peu plus générique que "l'égalité des éléments de la collection"--ou plutôt, la méthode des coupures de la collection originale d'intervalle à chaque fois que son test séquentiel des éléments tombe en panne.

Nous allons voir notre méthode en action:

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

Il fonctionne!

Le seul problème est que nous n'avons pas, en général, ces méthodes disponibles pour les tableaux, car cela impliquerait de deux conversions implicites dans une rangée. Il existe plusieurs méthodes pour contourner ce problème, y compris la rédaction d'un distinct conversion implicite pour les tableaux, la conversion en WrappedArray, et ainsi de suite.

---

Edit: Mon approche privilégiée pour traiter les tableaux et chaînes de caractères et telle est de rendre le code encore plus générique et ensuite utiliser les conversions implicites pour les rendre plus spécifiques de nouveau d'une manière telle que les matrices de travail aussi. Dans ce cas particulier:

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

Ici, nous avons ajouté un implicite qui nous donne un Iterable[A] de C--pour la plupart des collections, ce sera juste l'identité (par exemple, List[A] est déjà un Iterable[A]), mais pour les tableaux, il sera un véritable conversion implicite. Et, par conséquent, nous avons abandonné l'exigence d' C[A] <: Iterable[A]--nous avons essentiellement fait de l'exigence d' <% explicites, afin que nous puissions l'utiliser explicitement à volonté au lieu d'avoir le compilateur de le remplir pour nous. Aussi, nous avons assoupli les restrictions qui notre collection de collections C[C[A]]--au lieu de cela, c'est tout D[C], ce qui nous permettra de remplir plus tard pour être ce que nous voulons. Parce que nous allons le remplir plus tard, nous avons poussé jusqu'au niveau de la classe au lieu de la méthode de niveau. Sinon, c'est fondamentalement la même.

Maintenant la question est de savoir comment les utiliser. Pour des collections régulières, nous pouvons:

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

où maintenant nous brancher C[A] pour C et C[C[A]] pour D[C]. Notez que nous n'avons besoin de l'explicite types génériques sur l'appel à la new GroupingCollection donc il peut garder la droite dont les types correspondent à ce que. Grâce à l' implicit c2i: C[A] => Iterable[A], ce gère automatiquement les tableaux.

Mais attendez, si nous voulons utiliser des chaînes? Maintenant, nous sommes en difficulté, parce que vous ne pouvez pas avoir une "chaîne de valeurs". C'est là que le supplément de l'abstraction aide: on peut l'appeler D quelque chose qui est adapté pour contenir des chaînes de caractères. Prenons Vector, et effectuez les opérations suivantes:

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

Nous avons besoin d'un nouveau CanBuildFrom pour gérer la construction d'un vecteur de chaînes de caractères (mais c'est vraiment facile, car nous avons juste besoin de faire appel Vector.newBuilder[String]), puis nous avons besoin de remplir tous les types de sorte que l' GroupingCollection est tapé la sagesse. Notez que nous avons déjà flottant autour d'un [String,Char,String] CanBuildFrom, de sorte que les chaînes peuvent être faites à partir des collections de la station.

Essayons ceci:

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

Answer 2

De ce commit , il est beaucoup plus facile à "enrichir" Scala collections qu'il ne l'était lorsque Rex a donné son excellente réponse. Pour les cas simples, il pourrait ressembler à ceci,

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)

ce qui ajoute un "même type de résultat" en respectant filterMap fonctionnement à tous 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

Et pour l'exemple de la question, la solution ressemble maintenant,

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)

L'échantillon de RÉPLICATION de session,

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)

Encore une fois, notez que le même type de résultat de principe a été observé exactement de la même manière qu'il aurait eu s'il avait groupIdentical été directement définies sur GenTraversableLike.

Answer 3

De ce commit l'incantation magique est légèrement modifiée par rapport à ce qu'il était quand Miles a donné son excellente réponse.

Les ouvrages suivants, mais est-il canonique? J'espère que l'un des chanoines de la corriger. (Ou plutôt, des canons, l'un des gros canons.) Si la vue est fixée à une limite supérieure, vous perdez de l'application de Tableau et de la Corde. Il ne semble pas à la matière, si la limite est GenTraversableLike ou TraversableLike; mais IsTraversableLike vous donne 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)

Il n'y a plus d'une façon à la peau d'un chat à neuf vies. Cette version dit qu'une fois que ma source est converti en GenTraversableLike, tant que je peux construire le résultat de GenTraversable, juste le faire. Je ne suis pas intéressé par mon ancien 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)

Cette première tentative comprend un vilain conversion des Repr de 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)