abstraction sur une collection

Question

Récemment, j'ai écrit un itérateur pour un produit cartésien d'Anys, et j'ai commencé avec une liste de liste, mais reconnu, que je peux facilement passer au trait plus abstrait Seq.

Je sais, vous aimez voir le code. :)

class Cartesian (val ll: Seq[Seq[_]]) extends Iterator [Seq[_]] { 

    def combicount: Int = (1 /: ll) (_ * _.length) 

    val last = combicount 
    var iter = 0 

    override def hasNext(): Boolean = iter < last 
    override def next(): Seq[_] = { 
    val res = combination (ll, iter) 
    iter += 1 
    res 
    } 

    def combination (xx: Seq [Seq[_]], i: Int): List[_] = xx match { 
     case Nil  => Nil 
     case x :: xs => x (i % x.length) :: combination (xs, i/x.length) 
    } 
} 

Et un client de cette classe:

object Main extends Application { 
    val illi = new Cartesian (List ("abc".toList, "xy".toList, "AB".toList)) 
    // val ivvi = new Cartesian (Vector (Vector (1, 2, 3), Vector (10, 20))) 
    val issi = new Cartesian (Seq (Seq (1, 2, 3), Seq (10, 20))) 
    // val iaai = new Cartesian (Array (Array (1, 2, 3), Array (10, 20))) 

    (0 to 5).foreach (dummy => println (illi.next())) 
    // (0 to 5).foreach (dummy => println (issi.next())) 
} 
/* 
List(a, x, A) 
List(b, x, A) 
List(c, x, A) 
List(a, y, A) 
List(b, y, A) 
List(c, y, A) 
*/ 

Le code fonctionne bien pour Seq et listes (qui sont SEQS), mais bien sûr pas pour les tableaux ou le vecteur, qui ne sont pas de type Seq, et n'ont pas une contre-méthode '::'.

Mais la logique pourrait aussi être utilisée pour de telles collections.

Je pourrais essayer d'écrire une conversion implicite vers et depuis Seq pour Vector, Array, et ainsi de suite, ou essayer d'écrire une implémentation similaire, ou écrire un Wrapper, qui transforme la collection en Seq de Seq, et appelle 'hasNext' et 'next' pour la collection interne, et convertit le résultat en un tableau, un vecteur ou autre. (J'ai essayé de mettre en œuvre de telles solutions, mais je dois reconnaître: ce n'est pas si simple.) Pour un problème du monde réel, je réécrirais probablement l'Iterator indépendamment.)

Cependant, le tout devient un peu hors de contrôle si je avoir à traiter avec des tableaux de listes ou des listes de tableaux et d'autres cas mixtes.

Quelle serait la façon la plus élégante d'écrire l'algorithme de la manière la plus large possible?

Answer 1

Il existe deux solutions. Le premier est de ne pas exiger que les conteneurs soient une sous-classe de certaines super classes génériques, mais d'être convertibles en une seule (en utilisant des arguments de fonction implicites). Si le conteneur est déjà une sous-classe du type requis, il existe une conversion d'identité prédéfinie qui ne fait que la renvoyer.

import collection.mutable.Builder 
import collection.TraversableLike 
import collection.generic.CanBuildFrom 
import collection.mutable.SeqLike 

class Cartesian[T, ST[T], TT[S]](val ll: TT[ST[T]])(implicit cbf: CanBuildFrom[Nothing, T, ST[T]], seqLike: ST[T] => SeqLike[T, ST[T]], traversableLike: TT[ST[T]] => TraversableLike[ST[T], TT[ST[T]]]) extends Iterator[ST[T]] { 

    def combicount(): Int = (1 /: ll) (_ * _.length) 

    val last = combicount - 1 
    var iter = 0 

    override def hasNext(): Boolean = iter < last 
    override def next(): ST[T] = { 
    val res = combination (ll, iter, cbf()) 
    iter += 1 
    res 
    } 

    def combination (xx: TT[ST[T]], i: Int, builder: Builder[T, ST[T]]): ST[T] = 
    if (xx.isEmpty) builder.result 
    else combination (xx.tail, i/xx.head.length, builder += xx.head (i % xx.head.length)) 
} 

Ce genre de travaux:

scala> new Cartesian[String, Vector, Vector](Vector(Vector("a"), Vector("xy"), Vector("AB"))) 
res0: Cartesian[String,Vector,Vector] = empty iterator 

scala> new Cartesian[String, Array, Array](Array(Array("a"), Array("xy"), Array("AB"))) 
res1: Cartesian[String,Array,Array] = empty iterator 

je avais besoin de passer explicitement les types à cause de bug https://issues.scala-lang.org/browse/SI-3343

Une chose à noter est que cela vaut mieux que d'utiliser des types existentiels, parce que l'appel Ensuite, l'itérateur retourne le bon type, et pas Seq [Any].

Il y a plusieurs inconvénients ici:

• Si le conteneur n'est pas une sous-classe du type requis, il est converti en un, qui coûte des performances
• L'algorithme est pas complètement générique. Nous avons besoin que les types soient convertis en SeqLike ou en TraversableLike uniquement pour utiliser un sous-ensemble de fonctionnalités que ces types offrent. Donc, faire une fonction de conversion peut être difficile.
• Et si certaines capacités pouvaient être interprétées différemment dans différents contextes? Par exemple, un rectangle a deux propriétés 'length' (largeur et hauteur)

Maintenant pour la solution alternative.Nous notons que nous ne nous soucions pas vraiment sur les types de collections, à leurs capacités:

• TT devrait avoir foldLeft, get(i: Int) (pour obtenir la tête/queue)
• ST devrait avoir length, get(i: Int) et un bâtisseur

nous pouvons les encoder:

trait HasGet[T, CC[_]] { 
    def get(cc: CC[T], i: Int): T 
} 

object HasGet { 
    implicit def seqLikeHasGet[T, CC[X] <: SeqLike[X, _]] = new HasGet[T, CC] { 
    def get(cc: CC[T], i: Int): T = cc(i) 
    } 

    implicit def arrayHasGet[T] = new HasGet[T, Array] { 
    def get(cc: Array[T], i: Int): T = cc(i) 
    } 
} 

trait HasLength[CC] { 
    def length(cc: CC): Int 
} 

object HasLength { 
    implicit def seqLikeHasLength[CC <: SeqLike[_, _]] = new HasLength[CC] { 
    def length(cc: CC) = cc.length 
    } 

    implicit def arrayHasLength[T] = new HasLength[Array[T]] { 
    def length(cc: Array[T]) = cc.length 
    } 

} 

trait HasFold[T, CC[_]] { 
    def foldLeft[A](cc: CC[T], zero: A)(op: (A, T) => A): A 
} 

object HasFold { 
    implicit def seqLikeHasFold[T, CC[X] <: SeqLike[X, _]] = new HasFold[T, CC] { 
    def foldLeft[A](cc: CC[T], zero: A)(op: (A, T) => A): A = cc.foldLeft(zero)(op) 
    } 
    implicit def arrayHasFold[T] = new HasFold[T, Array] { 
    def foldLeft[A](cc: Array[T], zero: A)(op: (A, T) => A): A = { 
     var i = 0 
     var result = zero 
     while (i < cc.length) { 
     result = op(result, cc(i)) 
     i += 1 
     } 
     result 
    } 
    } 
} 

(à proprement parler, HasFold n'est pas requi rouge depuis sa mise en œuvre est en termes de longueur et d'obtenir, mais je l'ai ajouté ici, donc l'algorithme se traduira de façon plus propre)

maintenant l'algorithme est:

class Cartesian[T, ST[_], TT[Y]](val ll: TT[ST[T]])(implicit cbf: CanBuildFrom[Nothing, T, ST[T]], stHasLength: HasLength[ST[T]], stHasGet: HasGet[T, ST], ttHasFold: HasFold[ST[T], TT], ttHasGet: HasGet[ST[T], TT], ttHasLength: HasLength[TT[ST[T]]]) extends Iterator[ST[T]] { 

    def combicount(): Int = ttHasFold.foldLeft(ll, 1)((a,l) => a * stHasLength.length(l)) 

    val last = combicount - 1 
    var iter = 0 

    override def hasNext(): Boolean = iter < last 
    override def next(): ST[T] = { 
    val res = combination (ll, 0, iter, cbf()) 
    iter += 1 
    res 
    } 

    def combination (xx: TT[ST[T]], j: Int, i: Int, builder: Builder[T, ST[T]]): ST[T] = 
    if (ttHasLength.length(xx) == j) builder.result 
    else { 
     val head = ttHasGet.get(xx, j) 
     val headLength = stHasLength.length(head) 
     combination (xx, j + 1, i/headLength, builder += stHasGet.get(head, (i % headLength))) 
    } 
} 

Et:

scala> new Cartesian[String, Vector, List](List(Vector("a"), Vector("xy"), Vector("AB"))) 
res6: Cartesian[String,Vector,List] = empty iterator 

scala> new Cartesian[String, Array, Array](Array(Array("a"), Array("xy"), Array("AB"))) 
res7: Cartesian[String,Array,Array] = empty iterator 

Scalaz a probablement tout cela prédéfini pour vous, malheureusement, je ne le connais pas bien.

(encore une fois je besoin de passer les types parce que l'inférence ne suppose pas le bon type)

L'avantage est que l'algorithme est maintenant complètement générique et qu'il n'y a pas besoin de conversions implicites de tableau à WrappedArray en pour que cela fonctionne

Excercise: définir pour de tuples