Come posso applicare il modello arricchisci la mia biblioteca alle raccolte Scala?

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

Domanda

Uno dei modelli più potenti disponibili in Scala è il modello aware-my-library*, che utilizza conversioni implicite in apparire per aggiungere metodi alle classi esistenti senza richiedere la risoluzione dinamica del metodo.Ad esempio, se volessimo che tutte le stringhe avessero il metodo spaces che contava quanti caratteri di spazio bianco avevano, potevamo:

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

Sfortunatamente, questo modello incontra problemi quando si ha a che fare con raccolte generiche.Ad esempio, sono state poste una serie di domande raggruppare gli elementi in sequenza con le raccolte.Non c'è nulla di integrato che funzioni in un colpo solo, quindi questo sembra un candidato ideale per il modello arricchisci la mia biblioteca utilizzando una raccolta generica C e un tipo di elemento generico 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
    }
  }
}

tranne, ovviamente, esso non funziona.Il REPL ci 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
                      ^

Ci sono due problemi:come otteniamo un C[C[A]] da un vuoto C[A] elenco (o dal nulla)?E come otteniamo un C[C[A]] di ritorno dal same +: linea invece di a Seq[Seq[A]]?

* Precedentemente noto come pimp-my-library.

È stato utile?

Soluzione

La chiave per comprendere questo problema è rendersi conto che esistono due modi diversi di creare e lavorare con le raccolte nella biblioteca delle collezioni.Una è l'interfaccia delle raccolte pubbliche con tutti i suoi simpatici metodi.L'altro, che è ampiamente utilizzato in creando la biblioteca delle collezioni, ma che non vengono quasi mai utilizzate al di fuori di essa, sono i costruttori.

Il nostro problema nell'arricchimento è esattamente lo stesso che deve affrontare la stessa libreria delle raccolte quando tenta di restituire raccolte dello stesso tipo.Cioè, vogliamo creare raccolte, ma quando lavoriamo in modo generico, non abbiamo modo di fare riferimento allo "stesso tipo di cui è già la raccolta".Quindi abbiamo bisogno costruttori.

Ora la domanda è:da dove prendiamo i nostri costruttori?Il luogo ovvio è la collezione stessa. Questo non funziona.Avevamo già deciso, passando a una collezione generica, di dimenticare la tipologia della collezione.Quindi, anche se la raccolta potesse restituire un costruttore che genererebbe più raccolte del tipo desiderato, non saprebbe quale fosse il tipo.

Invece, otteniamo i nostri costruttori da CanBuildFrom impliciti che fluttuano in giro.Questi esistono specificamente allo scopo di abbinare i tipi di input e output e fornire un builder tipizzato in modo appropriato.

Dobbiamo quindi fare due passi concettuali:

  1. Non stiamo utilizzando operazioni di raccolta standard, stiamo utilizzando i builder.
  2. Otteniamo questi costruttori da implicit CanBuildFroms, non direttamente dalla nostra collezione.

Diamo un'occhiata a un esempio.

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

Analizziamolo.Innanzitutto, per creare la raccolta di raccolte, sappiamo che dovremo creare due tipi di raccolte: C[A] per ciascun gruppo e C[C[A]] che riunisce tutti i gruppi.Quindi, abbiamo bisogno di due costruttori, uno che prenda Ase costruisce C[A]s, e uno che prende C[A]se costruisce C[C[A]]S.Guardando la firma del tipo di CanBuildFrom, vediamo

CanBuildFrom[-From, -Elem, +To]

il che significa che CanBuildFrom vuole sapere il tipo di raccolta con cui stiamo iniziando: nel nostro caso lo è C[A], quindi gli elementi della raccolta generata e il tipo di tale raccolta.Quindi li inseriamo come parametri impliciti cbfcc E cbfc.

Avendo capito questo, questa è la maggior parte del lavoro.Possiamo usare il nostro CanBuildFroms per darci costruttori (tutto quello che devi fare è applicarli).E un costruttore può creare una collezione con +=, convertilo nella raccolta con cui dovrebbe essere alla fine result, e svuotarsi ed essere pronti a ricominciare clear.I builder iniziano vuoti, il che risolve il nostro primo errore di compilazione e poiché stiamo utilizzando i builder invece della ricorsione, anche il secondo errore scompare.

Un ultimo piccolo dettaglio, oltre all'algoritmo che esegue effettivamente il lavoro, è nella conversione implicita.Nota che usiamo new GroupingCollection[A,C] non [A,C[A]].Questo perché la dichiarazione della classe era for C con un parametro, che lo riempie lui stesso con il A gli è passato.Quindi gli consegniamo semplicemente il tipo C, e lascialo creare C[A] fuori di esso.Dettagli minori, ma otterrai errori in fase di compilazione se provi in ​​un altro modo.

In questo caso ho reso il metodo un po' più generico rispetto alla raccolta "elementi uguali": il metodo taglia piuttosto a parte la raccolta originale ogni volta che il test degli elementi sequenziali fallisce.

Vediamo il nostro metodo in azione:

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

Funziona!

L'unico problema è che in generale non abbiamo questi metodi disponibili per gli array, poiché ciò richiederebbe due conversioni implicite di seguito.Esistono diversi modi per aggirare questo problema, inclusa la scrittura di una conversione implicita separata per gli array, cast to WrappedArray, e così via.

Modificare:Il mio approccio preferito per gestire array, stringhe e simili è rendere uniforme il codice Di più generici e quindi utilizzare le conversioni implicite appropriate per renderli nuovamente più specifici in modo tale che anche gli array funzionino.In questo caso particolare: 

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

Qui abbiamo aggiunto un implicito che ci dà un Iterable[A] da C--per la maggior parte delle raccolte questa sarà solo l'identità (ad es. List[A] è già un Iterable[A]), ma per gli array sarà una vera conversione implicita.E, di conseguenza, abbiamo abbandonato il requisito che C[A] <: Iterable[A]--in pratica abbiamo appena stabilito il requisito per <% esplicito, quindi possiamo usarlo esplicitamente a piacimento invece di doverlo compilare per noi.Inoltre, abbiamo allentato la restrizione della nostra raccolta di collezioni C[C[A]]--invece, è qualsiasi D[C], che compileremo in seguito per essere quello che vogliamo.Poiché lo completeremo più tardi, lo abbiamo spinto al livello della classe invece che al livello del metodo.Altrimenti è fondamentalmente lo stesso.

Ora la domanda è come usarlo.Per le collezioni regolari, possiamo:

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

dove ora ci colleghiamo C[A] per C E C[C[A]] per D[C].Tieni presente che abbiamo bisogno dei tipi generici espliciti nella chiamata a new GroupingCollection in modo che possa capire quali tipi corrispondono a cosa.Grazie al implicit c2i: C[A] => Iterable[A], questo gestisce automaticamente gli array.

Ma aspetta, cosa succede se vogliamo usare le stringhe?Ora siamo nei guai, perché non si può avere una "stringa di stringhe".È qui che l'astrazione extra aiuta:possiamo chiamare D qualcosa che sia adatto a contenere le corde.Scegliamo Vector, e procedi come segue:

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

Abbiamo bisogno di un nuovo CanBuildFrom per gestire la costruzione di un vettore di stringhe (ma questo è davvero semplice, dato che basta chiamare Vector.newBuilder[String]), quindi dobbiamo compilare tutti i tipi in modo che il file GroupingCollection è digitato in modo sensato.Nota che stiamo già fluttuando intorno a a [String,Char,String] CanBuildFrom, quindi è possibile creare stringhe da raccolte di caratteri.

Proviamolo:

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

Altri suggerimenti

A partire da questo commit è molto più facile "arricchire" le collezioni Scala rispetto a quando Rex ha dato il suoottima risposta.Per casi semplici potrebbe assomigliare a questo, 

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)

che aggiunge uno "stesso tipo di risultato" rispettando l'operazione filterMap a tutti i GenTraversableLike, 

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

E per l'esempio della domanda, la soluzione ora è 

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)

Esempio di sessione 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)

Ancora una volta, nota che lo stesso principio del tipo di risultato è stato osservato esattamente nello stesso modo in cui sarebbe stato se groupIdentical fosse stato definito direttamente su GenTraversableLike.

A partire da questo commit l'incantesimo magico è leggermente cambiato rispetto a quello che era quando Miles ha dato la sua eccellente risposta.

Il seguente funziona, ma è canonico?Spero che uno dei canoni lo corregga.(O meglio, cannoni, uno dei grandi cannoni.) Se il limite della vista è un limite superiore, si perde l'applicazione a Array e String.Non sembra avere importanza se il limite è GenTraversableLike o TraversableLike;ma IsTraversableLike ti dà 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)

C'è più di un modo per scuoiare un gatto con nove vite.Questa versione dice che una volta che la mia sorgente è stata convertita in GenTraversableLike, fintanto che posso creare il risultato da GenTraversable, fallo e basta.Non mi interessa il mio vecchio 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)

Questo primo tentativo include una brutta conversione di 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)
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top