Comment appliquer le motif enrichis-my-bibliothèque aux collections Scala?

StackOverflow https://stackoverflow.com/questions/5410846

Question

L'un des modèles les plus puissants disponibles à 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 une résolution de méthode dynamique. Par exemple, si nous souhaitons que toutes les cordes aient la méthode spaces Cela comptait le nombre de personnages blancs d'espace, 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'ils traitent des collections génériques. Par exemple, un certain nombre de questions ont été posées sur regrouper les éléments séquentiellement avec des collections. Il n'y a rien intégré qui fonctionne en un seul coup, donc cela semble un candidat idéal pour le motif enrichis-my-bibliothèque en utilisant une collection générique C et 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, ne fonctionne pas. Le REP 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]] d'un vide C[A] Liste (ou à partir de l'air mince)? Et comment pouvons-nous obtenir un C[C[A]] de retour du same +: ligne au lieu d'un Seq[Seq[A]]?

* Anciennement connu sous le nom de Pimp-My-Library.

Était-ce utile?

La solution

La clé pour comprendre ce problème est de réaliser qu'il y a Deux façons différentes de construire et de travailler avec des collections Dans la bibliothèque des collections. L'une est l'interface des collections publiques avec toutes ses belles méthodes. L'autre, qui est largement utilisé dans création La bibliothèque des collections, mais qui ne sont presque jamais utilisées en dehors de celle-ci, sont les constructeurs.

Notre problème en enrichissant est exactement le même que la bibliothèque de collections elle-même est confrontée lorsque vous essayez de retourner des collections du même type. Autrement dit, nous voulons construire des collections, mais lorsque nous travaillons génériquement, nous n'avons pas de moyen de nous référer à "le même type que la collection est déjà". Alors nous avons besoin constructeurs.

Maintenant, la question est: d'où tirons-nous nos constructeurs? L'endroit évident est de la collection elle-même. Cela ne fonctionne pas. Nous avons déjà décidé, en déménageant dans une collection générique, que nous allions oublier le type de collection. Ainsi, même si la collection pourrait retourner un constructeur qui générerait plus de collections du type que nous voulons, il ne saurait pas quel était le type.

Au lieu de cela, nous obtenons nos constructeurs de CanBuildFrom implicites 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 constructeur dactylographié de manière appropriée.

Nous avons donc deux sauts conceptuels à faire:

  1. Nous n'utilisons pas d'opérations de collections standard, nous utilisons les constructeurs.
  2. Nous obtenons ces constructeurs d'implicites 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)
}

Voyons ça. Tout d'abord, afin de construire la collection de collections, nous savons que nous devrons 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, un qui prend As et construire C[A]s, et celui qui prend C[A]s et construire 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 que 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 cbfcc et cbfc.

Après avoir réalisé cela, c'est la plupart du travail. Nous pouvons utiliser notre CanBuildFroms pour nous donner des constructeurs (tout ce que vous avez à faire est de les appliquer). Et un constructeur peut construire une collection avec +=, convertissez-le à la collection qu'il est censé être finalement avec result, et se vider et être prêt à recommencer avec clear. Les constructeurs commencent vide, qui résout notre première erreur de compilation, et comme nous utilisons les constructeurs 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 utilisons new GroupingCollection[A,C] ne pas [A,C[A]]. C'est parce que la déclaration de classe était pour C avec un paramètre, qu'il le remplit lui-même avec le A y passer. Alors nous lui remettons juste le type C, et laissez-le créer C[A] en dehors de ça. Détails mineurs, mais vous obtiendrez des erreurs de temps de compilation si vous essayez un autre moyen.

Ici, j'ai rendu la méthode un peu plus générique que la collection "Egal Elements" - Rather, la méthode coupe la collection originale à part chaque fois que son test d'é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 pas en général ces méthodes disponibles pour les tableaux, car cela nécessiterait deux conversions implicites d'affilée. Il existe plusieurs façons de contourner cela, notamment en écrivant une conversion implicite distincte pour les tableaux, en jetant en WrappedArray, etc.

Edit: mon approche préférée pour traiter les tableaux et les chaînes et tels sont de faire même le code Suite générique puis utilisez 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] de C- Pour la plupart des collections, ce ne sera que l'identité (par exemple List[A] est déjà un Iterable[A]), mais pour les tableaux, ce sera une véritable conversion implicite. Et, par conséquent, nous avons abandonné l'exigence que C[A] <: Iterable[A]- nous avons essentiellement fait l'exigence de <% Explicite, nous pouvons donc l'utiliser explicitement à volonté au lieu de faire le remplir pour le compilateur pour nous. De plus, nous avons assoupli la restriction selon laquelle notre collection de collections est C[C[A]]--intead, c'est tout D[C], que nous allons remplir plus tard pour être ce que nous voulons. Parce que nous allons le remplir plus tard, nous l'avons repoussé au niveau de la classe au lieu du niveau de 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 branchons C[A] pour C et C[C[A]] pour D[C]. Notez que nous avons besoin des types génériques explicites sur l'appel à new GroupingCollection Il peut donc garder droit quels types correspondent à quoi. Grace à implicit c2i: C[A] => Iterable[A], cela gère automatiquement les tableaux.

Mais attendez, que se passe-t-il si nous voulons utiliser des chaînes? Maintenant, nous sommes en difficulté, car vous ne pouvez pas avoir une "chaîne de chaînes". C'est là que l'abstraction supplémentaire aide: nous pouvons appeler D Quelque chose qui convient à contenir des cordes. Pick's Chick Vector, et faites 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 CanBuildFrom Pour gérer la construction d'un vecteur de cordes (mais c'est vraiment facile, car nous avons juste besoin d'appeler Vector.newBuilder[String]), puis nous devons remplir tous les types afin que le GroupingCollection est tapé raisonnablement. Notez que nous avons déjà flotté autour d'un [String,Char,String] Canbuildfrom, de sorte que des cordes peuvent être faites à 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, !!)

Autres conseils

À partir de Cet engagement Il est beaucoup plus facile de "enrichir" les collections de Scala que lorsque Rex a donné son excellente réponse. Pour des 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" concernant filterMap opération à 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)

Exemple de session de remplacement,

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 été groupIdentical été directement défini sur GenTraversableLike.

À partir de Cet engagement L'incantation magique est légèrement modifiée par rapport à ce que c'était lorsque Miles a donné son excellente réponse.

Ce qui suit fonctionne, mais est-ce canonique? J'espère que l'un des canons le corrigera. (Ou plutôt, des canons, l'un des gros canons.) Si la limite de la vue est une limite supérieure, vous perdez une application au tableau et à la chaîne. Cela ne semble pas avoir d'importance si le lien est gentrauversablelike 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 de peau un chat avec neuf vies. Cette version indique qu'une fois que ma source est convertie en gentraversablelike, tant que je pourrai construire le résultat de la gentraulable, faites-le. Je ne suis pas intéressé par mon ancien rep.

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 Rep à 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)
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top