Wie wende ich das Muster "Meine Bibliothek anreichern" auf Scala-Sammlungen an?

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

Frage

Eines der leistungsstärksten Muster in Scala ist das Anreicherungs-My-Library * -Muster, das implizite Konvertierungen verwendet, um zu erscheinen , um Methoden zu vorhandenen Klassen hinzuzufügen, ohne dass eine dynamische Methodenauflösung erforderlich ist. Wenn wir beispielsweise wünschen würden, dass alle Zeichenfolgen die Methode spaces haben, die die Anzahl der Leerzeichen zählt, die sie haben, könnten wir: 

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

Leider stößt dieses Muster beim Umgang mit generischen Sammlungen auf Probleme. Beispielsweise wurde eine Reihe von Fragen zum Gruppieren von Elementen nacheinander mit Sammlungen gestellt . Es ist nichts eingebaut, was auf einen Schlag funktioniert. Dies scheint also ein idealer Kandidat für das Anreicherungsmuster meiner Bibliothek zu sein, das einen generischen AuflistungsC und einen generischen Elementtyp A verwendet: 

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

außer natürlich, dass es nicht funktioniert . Die REPL sagt uns: 

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

Es gibt zwei Probleme: Wie erhalten wir einen C[C[A]] aus einer leeren C[A]-Liste (oder aus der Luft)? Und wie erhalten wir einen C[C[A]] von der same +:-Zeile anstelle eines Seq[Seq[A]] zurück?

* Früher als pimp-my-library bekannt.

War es hilfreich?

Lösung

Der Schlüssel zum Verständnis dieses Problems besteht darin, zu erkennen, dass es in der Sammlungsbibliothek zwei verschiedene Möglichkeiten gibt, Sammlungen zu erstellen und damit zu arbeiten. Eine davon ist die Schnittstelle für öffentliche Sammlungen mit all ihren netten Methoden. Das andere, das beim Erstellen der Sammlungsbibliothek häufig verwendet wird, aber außerhalb der Bibliothek fast nie verwendet wird, sind die Builder.

Unser Problem bei der Anreicherung ist genau das gleiche, mit dem die Sammlungsbibliothek selbst konfrontiert ist, wenn versucht wird, Sammlungen desselben Typs zurückzugeben. Das heißt, wir möchten Sammlungen erstellen, aber wenn wir generisch arbeiten, können wir nicht auf "den gleichen Typ verweisen, der die Sammlung bereits ist". Wir brauchen also Builder .

Nun lautet die Frage: Woher bekommen wir unsere Bauherren? Der offensichtliche Ort stammt aus der Sammlung selbst. Das funktioniert nicht . Wir haben bereits beim Umzug in eine generische Sammlung beschlossen, den Typ der Sammlung zu vergessen. Obwohl die Sammlung einen Builder zurückgeben könnte, der mehr Sammlungen des gewünschten Typs generieren würde, würde sie nicht wissen, um welchen Typ es sich handelt.

Stattdessen erhalten wir unsere Builder von CanBuildFrom-Implikits, die im Umlauf sind. Diese dienen speziell dazu, Eingabe- und Ausgabetypen abzugleichen und Ihnen einen entsprechend typisierten Builder zu bieten.

Wir müssen also zwei konzeptionelle Sprünge machen:

  1. Wir verwenden keine Standard-Sammlungsoperationen, sondern Builder.
  2. Wir erhalten diese Builder von impliziten CanBuildFroms, nicht direkt aus unserer Sammlung.

    Schauen wir uns ein Beispiel an. 

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

    Nehmen wir das auseinander. Erstens müssen wir zum Erstellen der Sammlung von Sammlungen zwei Arten von Sammlungen erstellen: C[A] für jede Gruppe und C[C[A]], der alle Gruppen zusammenfasst. Daher benötigen wir zwei Builder, einen, der As verwendet und C[A]s erstellt, und einen, der C[A]s verwendet und C[C[A]]s erstellt. Wenn wir uns die Typensignatur von CanBuildFrom ansehen, sehen wir 

    CanBuildFrom[-From, -Elem, +To]

    was bedeutet, dass CanBuildFrom wissen möchte, mit welcher Art von Sammlung wir beginnen - in unserem Fall ist es C[A] und dann die Elemente der generierten Sammlung und der Typ dieser Sammlung. Also füllen wir diese als implizite Parameter cbfcc und cbfc aus.

    Nachdem ich das erkannt habe, ist das der größte Teil der Arbeit. Wir können unsere CanBuildFroms verwenden, um uns Builder zu geben (alles, was Sie tun müssen, ist sie anzuwenden). Ein Builder kann eine Sammlung mit += erstellen, in die Sammlung konvertieren, die letztendlich mit result erstellt werden soll, sich selbst leeren und bereit sein, erneut mit clear zu beginnen. Die Builder beginnen leer, wodurch unser erster Kompilierungsfehler behoben wird. Da wir Builder anstelle von Rekursion verwenden, verschwindet auch der zweite Fehler.

    Ein letztes kleines Detail - abgesehen von dem Algorithmus, der die Arbeit tatsächlich erledigt - ist die implizite Konvertierung. Beachten Sie, dass wir new GroupingCollection[A,C] verwenden, nicht [A,C[A]]. Dies liegt daran, dass die Klassendeklaration für C mit einem Parameter war, den sie selbst mit dem an sie übergebenen A füllt. Also geben wir ihm einfach den Typ C und lassen ihn daraus C[A] erstellen. Kleinere Details, aber Sie erhalten Fehler bei der Kompilierung, wenn Sie einen anderen Weg versuchen.

    Hier habe ich die Methode etwas allgemeiner gestaltet als die Sammlung "Gleiche Elemente". Stattdessen schneidet die Methode die ursprüngliche Sammlung auseinander, wenn der Test der sequentiellen Elemente fehlschlägt.

    Sehen wir uns unsere Methode in Aktion an: 

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

    Es funktioniert!

    Das einzige Problem ist, dass wir diese Methoden im Allgemeinen nicht für Arrays zur Verfügung haben, da dies zwei implizite Konvertierungen in a erfordern würde

Reihe. Es gibt verschiedene Möglichkeiten, dies zu umgehen, einschließlich des Schreibens einer separaten impliziten Konvertierung für Arrays, des Castings in WrappedArray usw.

Bearbeiten: Mein bevorzugter Ansatz für den Umgang mit Arrays und Strings besteht darin, den Code noch allgemeiner zu gestalten und dann geeignete implizite Konvertierungen zu verwenden, um sie wieder spezifischer zu machen, sodass Arrays funktionieren ebenfalls. In diesem speziellen Fall: 

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

Hier haben wir ein Implizit hinzugefügt, das uns einen Iterable[A] aus C gibt. Bei den meisten Sammlungen ist dies nur die Identität (z. B. ist List[A] bereits ein Iterable[A]), bei Arrays handelt es sich jedoch um eine echte implizite Konvertierung. Infolgedessen haben wir die Anforderung für C[A] <: Iterable[A] gestrichen. Grundsätzlich haben wir die Anforderung für <% explizit festgelegt, damit wir sie nach Belieben explizit verwenden können, anstatt sie vom Compiler ausfüllen zu lassen. Außerdem haben wir die Einschränkung gelockert, dass unsere Sammlung von Sammlungen C[C[A]] ist - stattdessen ist es jeder D[C], den wir später ausfüllen werden, um das zu sein, was wir wollen. Da wir dies später ausfüllen werden, haben wir es auf die Klassenebene anstatt auf die Methodenebene verschoben. Ansonsten ist es im Grunde das gleiche.

Nun ist die Frage, wie man das benutzt. Für reguläre Sammlungen können wir: 

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

wo wir jetzt C[A] für C und C[C[A]] für D[C] einstecken. Beachten Sie, dass wir beim Aufruf von new GroupingCollection die expliziten generischen Typen benötigen, damit klargestellt werden kann, welche Typen welchen entsprechen. Dank des implicit c2i: C[A] => Iterable[A] werden Arrays automatisch verarbeitet.

Aber warten Sie, was ist, wenn wir Zeichenfolgen verwenden möchten? Jetzt sind wir in Schwierigkeiten, weil Sie keine "Zeichenfolge" haben können. Hier hilft die zusätzliche Abstraktion: Wir können D als etwas bezeichnen, das zum Halten von Zeichenfolgen geeignet ist. Lassen Sie uns Vector auswählen und Folgendes tun: 

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

Wir benötigen einen neuen CanBuildFrom, um die Erstellung eines Vektors von Zeichenfolgen zu handhaben (dies ist jedoch sehr einfach, da wir nur Vector.newBuilder[String] aufrufen müssen), und dann müssen wir alle Typen eingeben, damit der GroupingCollection sinnvoll eingegeben wird . Beachten Sie, dass wir bereits einen [String,Char,String] CanBuildFrom haben, sodass Zeichenfolgen aus Zeichensammlungen erstellt werden können.

Probieren wir es aus: 

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

Andere Tipps

Ab diesem Commit ist es viel einfacher, Scala-Sammlungen zu "bereichern", als es Rex gabausgezeichnete Antwort.In einfachen Fällen könnte es so aussehen: 

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)

, das allen filterMaps einen "gleichen Ergebnistyp" hinzufügt, der die GenTraversableLike-Operation berücksichtigt, 

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

Und für das Beispiel aus der Frage sieht die Lösung jetzt so aus: 

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)

Beispiel einer REPL-Sitzung, 

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)

Beachten Sie erneut, dass das gleiche Prinzip des Ergebnistyps genauso beobachtet wurde, wie es gewesen wäre, wenn groupIdentical direkt auf GenTraversableLike definiert worden wäre.

Ab diesem Commit hat sich die magische Beschwörung geringfügig von der geändert, als Miles seine hervorragende Antwort gab.

Folgendes funktioniert, aber ist es kanonisch?Ich hoffe, einer der Kanonen wird es korrigieren.(Oder besser gesagt, Kanonen, eine der großen Kanonen.) Wenn die Ansichtsgrenze eine Obergrenze ist, verlieren Sie die Anwendung auf Array und String.Es scheint keine Rolle zu spielen, ob die Grenze GenTraversableLike oder TraversableLike ist.Mit IsTraversableLike erhalten Sie jedoch ein 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)

Es gibt mehr als einen Weg, eine Katze mit neun Leben zu häuten.Diese Version besagt, dass, sobald meine Quelle in ein GenTraversableLike konvertiert ist, solange ich das Ergebnis aus GenTraversable erstellen kann, dies einfach getan wird.Ich interessiere mich nicht für meinen alten 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)

Dieser erste Versuch beinhaltet eine hässliche Konvertierung von Repr in 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)

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top