Comment appliquer le modèle enrichir ma bibliothèque aux collections Scala?

L'un des modèles les plus puissants disponibles dans Scala est le modèle enrich-my-library *, qui utilise des conversions implicites pour apparaître pour ajouter des méthodes aux classes existantes sans nécessiter de résolution de méthode dynamique. Par exemple, si nous souhaitions que toutes les chaînes aient la méthode spacesqui compte le nombre de caractères d'espacement qu'elles contiennent, nous pourrions:

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 rencontre des problèmes lorsqu'il s'agit de collections génériques. Par exemple, un certain nombre de questions ont été posées sur le regroupement des éléments de manière séquentielle avec des collections . Il n'y a rien de intégré qui fonctionne en un seul coup, donc cela semble un candidat idéal pour le modèle enrichir ma bibliothèque en utilisant une collection générique Cet un type d'élément générique 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, ça ne marche 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 obtenir un à C[C[A]]partir d'une C[A]liste vide (ou à partir de rien)? Et comment pouvons-nous obtenir un C[C[A]]retour de lasame +: ligne au lieu d'un Seq[Seq[A]]?

* ^{Anciennement connu sous le nom de pimp-my-library.}

La clé pour comprendre ce problème est de réaliser qu'il existe deux façons différentes de créer et de travailler avec des collections dans la bibliothèque de collections. L'un est l'interface des collections publiques avec toutes ses méthodes intéressantes. L'autre, qui est largement utilisé dans la création la bibliothèque de collections, mais qui n'est presque jamais utilisé en dehors de celle-ci, ce sont les constructeurs.

Notre problème d'enrichissement est exactement le même que celui auquel la bibliothèque de collections elle-même est confrontée lorsqu'elle tente de renvoyer des collections du même type. Autrement dit, nous voulons créer des collections, mais lorsque nous travaillons de manière générique, nous n'avons pas de moyen de faire référence au "même type que la collection est déjà". Nous avons donc besoin de constructeurs .

Maintenant, la question est: d'où viennent nos constructeurs? L'endroit évident est la collection elle-même. Ça ne marche pas . Nous avons déjà décidé, en passant à une collection générique, que nous allions oublier le type de collection. Ainsi, même si la collection pourrait renvoyer un générateur qui générerait plus de collections du type souhaité, elle ne saurait pas quel était le type.

Au lieu de cela, nous obtenons nos constructeurs d' CanBuildFromimplicits qui flottent. Ceux-ci existent spécifiquement dans le but de faire correspondre les types d'entrée et de sortie et de vous donner un générateur correctement typé.

Nous avons donc deux sauts conceptuels à faire:

1. Nous n'utilisons pas d'opérations de collecte standard, nous utilisons des générateurs.
2. Nous obtenons ces générateurs à partir de CanBuildFroms implicites , pas directement de notre collection.

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 cela à part. Tout d'abord, afin de construire la collection de collections, nous savons que nous devrons créer deux types de collections: C[A]pour chaque groupe, et C[C[A]]cela rassemble tous les groupes. Ainsi, nous avons besoin de deux générateurs, l'un qui prend As et construit C[A]s, et l'autre qui prend C[A]s et construit C[C[A]]s. En regardant la signature de type de CanBuildFrom, nous voyons

CanBuildFrom[-From, -Elem, +To]

ce qui signifie que CanBuildFrom veut connaître le type de collection avec lequel nous commençons - dans notre cas, c'est C[A], puis les éléments de la collection générée et le type de cette collection. Nous les remplissons donc comme des paramètres implicites cbfccet cbfc.

Ayant réalisé cela, c'est l'essentiel du travail. Nous pouvons utiliser nos CanBuildFroms pour nous donner des constructeurs (tout ce que vous avez à faire est de les appliquer). Et un constructeur peut créer une collection avec +=, la convertir en collection avec laquelle elle est censée appartenirresult , se vider et être prêt à recommencer clear. Les générateurs commencent vide, ce qui résout notre première erreur de compilation, et puisque nous utilisons des générateurs au lieu de la récursivité, la deuxième erreur disparaît également.

Un dernier petit détail - autre que l'algorithme qui fait réellement le travail - est dans la conversion implicite. Notez que nous n'utilisons new GroupingCollection[A,C]pas [A,C[A]]. C'est parce que la déclaration de classe était pour Cavec un paramètre, qu'elle remplit elle-même avec le Apassé. Alors on lui donne juste le typeC et le laissons créer à C[A]partir de celui-ci. Détails mineurs, mais vous obtiendrez des erreurs de compilation si vous essayez une autre méthode.

Ici, j'ai rendu la méthode un peu plus générique que la collection «éléments égaux» - plutôt, la méthode coupe la collection originale à chaque fois que son test des éléments séquentiels échoue.

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

Ça marche!

Le seul problème est que nous n'avons généralement pas ces méthodes disponibles pour les tableaux, car cela nécessiterait deux conversions implicites consécutives. Il existe plusieurs façons de contourner ce problème, notamment l'écriture d'une conversion implicite distincte pour les tableaux, la conversion en WrappedArray, etc.

Edit: Mon approche préférée pour traiter les tableaux et les chaînes, etc. , consiste à rendre le code encore plus générique, puis à utiliser les conversions implicites appropriées pour les rendre plus spécifiques de manière à ce que les tableaux fonctionnent également. 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]from C- pour la plupart des collections, ce ne sera que l'identité (par exempleList[A] déjà un Iterable[A]), mais pour les tableaux, ce sera une véritable conversion implicite. Et, par conséquent, nous avons supprimé l'exigence selon C[A] <: Iterable[A]laquelle - nous avons simplement rendu l'exigence <%explicite, afin que nous puissions l'utiliser explicitement à volonté au lieu de laisser le compilateur le remplir pour nous. De plus, nous avons assoupli la restriction selon laquelle notre collection de collections est - au C[C[A]]lieu de cela, c'est n'importe D[C]laquelle, que nous remplirons plus tard pour être ce que nous voulons. Parce que nous allons le remplir plus tard, nous l'avons poussé au niveau de la classe au lieu du niveau de la méthode. Sinon, c'est fondamentalement la même chose.

Maintenant, la question est de savoir comment l'utiliser. Pour les 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 nous connectons C[A]pour Cet C[C[A]]pour D[C]. Notez que nous avons besoin des types génériques explicites lors de l'appel à new GroupingCollectionafin de pouvoir savoir quels types correspondent à quoi. Grâce à implicit c2i: C[A] => Iterable[A], cela gère automatiquement les tableaux.

Mais attendez, que faire si nous voulons utiliser des chaînes? Maintenant, nous avons des problèmes, car vous ne pouvez pas avoir de "chaîne de chaînes". C'est là que l'abstraction supplémentaire aide: nous pouvons appeler Dquelque chose qui convient pour contenir des chaînes. Choisissons Vectoret faisons ce qui suit:

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 CanBuildFrompour gérer la construction d'un vecteur de chaînes (mais c'est vraiment facile, car il suffit d'appelerVector.newBuilder[String] ), puis nous devons remplir tous les types pour que le GroupingCollectionsoit typé judicieusement. Notez que nous avons déjà flottant autour d'un[String,Char,String] CanBuildFrom, de sorte que les chaînes peuvent être créées à partir de collections de caractères.

Essayons-le:

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 ce commit, il est beaucoup plus facile «d'enrichir» les collections Scala que lorsque Rex a donné son excellente réponse. Pour les cas simples, cela 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)

qui ajoute un "même type de résultat" respectant l' filterMapopération à tous les 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)

Exemple de session 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)

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

À partir de ce commit l'incantation magique est légèrement modifiée par rapport à ce qu'elle était lorsque Miles a donné son excellente réponse.

Les œuvres suivantes, mais est-ce canonique? J'espère que l'un des canons le corrigera. (Ou plutôt, les canons, l'un des gros canons.) Si la limite de vue est une limite supérieure, vous perdez l'application à Array et String. Peu importe si la borne 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 y a plus d'une façon d'écorcher un chat avec neuf vies. Cette version dit qu'une fois que ma source est convertie en GenTraversableLike, tant que je peux construire le résultat à partir de GenTraversable, faites-le. 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 une vilaine conversion de Repr en 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)