Scala 2.8 tutorial de conception de collections

suite de my breathless confusion , quelles sont quelques bonnes ressources qui expliquent comment le nouveau Scala 2.8 collections la bibliothèque a été structurée. Je suis intéressé de trouver quelques informations sur la façon dont les suivants s'articulent ensemble:

  • les classes/traits de collection eux-mêmes (par exemple: List , Iterable )
  • pourquoi le comme il existe des classes (par exemple TraversableLike )
  • quelles sont les méthodes d'accompagnement (par exemple List.companion )
  • Comment je sais ce que implicit les objets sont dans la portée, à un moment donné
73
demandé sur Jon Clements 2009-11-12 16:21:31

1 réponses

Avant-propos

il y a un 2.8 parcours de la collection par Martin Odersky qui devrait probablement être votre première référence. Il a été complété avec "notes architecturales , qui sera d'un intérêt particulier pour ceux qui veulent concevoir leurs propres collections.

le reste de cette réponse a été écrit bien avant qu'une telle chose existait (en fait, avant 2.8.0 lui-même a été libéré).

vous pouvez trouver un papier à ce sujet comme Scala SID #3 . D'autres documents dans ce domaine devraient être intéressants aussi bien pour les personnes intéressées par les différences entre Scala 2.7 et 2.8.

je vais citer du papier, sélectivement, et compléter avec certaines de mes pensées. Il y a aussi quelques images, générées par Matthias à decodified.com, et les fichiers SVG originaux peuvent être trouvés ici .

Les classes de collection/traits eux-mêmes

il y a en fait trois hiérarchies de traits pour les collections: une pour les collections mutables, une pour les collections immuables, et une qui ne fait aucune hypothèse sur les collections.

il y a aussi une distinction entre collections parallèles, séries et peut-être-parallèles, qui a été introduite avec Scala 2.9. Je vais en parler dans le prochain section. La hiérarchie décrite dans cette section se réfère exclusivement à des collections non parallèles .

l'image suivante montre la hiérarchie non spécifique introduite avec Scala 2.8: General collection hierarchy

tous les éléments montrés sont des traits. Dans les deux autres hiérarchies il y a aussi des classes héritant directement les traits aussi bien que des classes qui peuvent être considérées comme appartenant à cette hiérarchie à travers la conversion implicite en classes enveloppantes. La légende de ces graphiques peut être trouvée après eux.

graphe pour hiérarchie immuable: Immutable collection hierarchy

graphique pour la hiérarchie mutable: Mutable collection hierarchy

légende:

Graph legend

voici une représentation ASCII abrégée de la hiérarchie de la collection, pour ceux qui ne peuvent pas voir les images.

                    Traversable
                         |
                         |
                      Iterable
                         |
      +------------------+--------------------+
     Map                Set                  Seq
      |                  |                    |
      |             +----+----+         +-----+------+
    Sorted Map  SortedSet   BitSet   Buffer Vector LinearSeq

Collections Parallèles

lorsque Scala 2.9 a introduit les collections parallèles, L'un des objectifs de la conception était de rendre leur utilisation aussi transparente que possible. Dans les termes les plus simples, on peut remplacer une collection non-parallèle (en série) par une collection parallèle, et récolter instantanément les bénéfices.

cependant, puisque toutes les collections jusqu'alors étaient en série, de nombreux algorithmes les utilisant supposait et dépendait du fait qu'ils étaient série. Les collectes parallèles alimentées aux méthodes avec de telles hypothèses échoueraient. Pour cette raison, toute la hiérarchie décrite dans la section précédente rend obligatoire le traitement en série .

deux nouvelles hiérarchies ont été créées pour supporter les collections parallèles.

la hiérarchie des collections parallèles a les mêmes noms pour les traits, mais précédé avec Par : ParIterable , ParSeq , ParMap et ParSet . Notez qu'il n'y a pas de ParTraversable , puisque toute collection supportant l'accès parallèle est capable de supporter le trait plus fort ParIterable . Il n'a pas non plus certains des traits les plus spécialisés présents dans la hiérarchie des séries. Toute cette hiérarchie se trouve dans le répertoire scala.collection.parallel .

les classes mettant en œuvre des collections parallèles diffèrent également, avec ParHashMap et ParHashSet pour les collections parallèles mutables et immuables, plus ParRange et ParVector mettant en œuvre immutable.ParSeq et ParArray mettant en œuvre mutable.ParSeq .

il existe également une autre hiérarchie qui reflète les caractéristiques des collections en série et en parallèle, mais avec un préfixe Gen : GenTraversable , GenIterable , GenSeq , GenMap et GenSet . Ces caractéristiques sont parents à la fois parallèle et série collections. Cela signifie qu'une méthode qui prend un Seq ne peut pas recevoir une collection parallèle, mais une méthode qui prend un GenSeq est censée fonctionner avec des collections en série et en parallèle.

étant donné la façon dont ces hiérarchies étaient structurées, le code écrit pour Scala 2.8 était entièrement compatible avec Scala 2.9, et exigeait un comportement de série. Sans être réécrite, elle ne peut tirer profit des collections parallèles, mais les changements requis sont très limités.

En Utilisant En Parallèle Des Collections

toute collection peut être convertie en une collection parallèle en appelant la méthode par . De même, n'importe quelle collection peut être convertie en une série en appelant la méthode seq sur elle.

si la collecte était déjà du type demandé (parallèle ou en série), aucune conversion n'aura lieu. Si l'on appelle seq sur une collection parallèle ou par sur une collection en série, cependant, une nouvelle collection avec la caractéristique demandée sera générée.

ne confondez pas seq , qui transforme une collection en une collection non-parallèle, avec toSeq , qui renvoie une Seq créée à partir des éléments de la collection. Appeler toSeq sur une collection parallèle retournera un ParSeq , pas une collection Série.

Les Principaux Traits

Bien qu'il y ait de nombreuses classes et sous-classes de mise en œuvre, il y a quelques traits de base dans la hiérarchie, chacun fournissant plus de méthodes ou des garanties plus spécifiques, mais réduisant le nombre de classes qui pourraient les mettre en œuvre.

dans les sous-sections suivantes, je vais donner une brève description des principaux traits et l'idée derrière eux.

Trait TraversableOnce

ce trait est assez semblable au trait Traversable décrit ci-dessous, mais avec la limitation que vous ne pouvez l'utiliser qu'une fois . En d'autres termes, toute méthode appelée TraversableOnce peut la rendre inutilisable.

cette limitation permet de partager les mêmes méthodes entre les collections et Iterator . Cela permet à une méthode qui fonctionne avec un Iterator mais n'utilisant pas Iterator - méthodes spécifiques d'être réellement en mesure pour travailler avec n'importe quelle collection, plus itérateurs, si réécrit pour accepter TraversableOnce .

parce que TraversableOnce unifie les collections et les itérateurs, il n'apparaît pas dans les graphiques précédents, qui concernent eux-mêmes seulement les collections.

Trait Traversable

En haut de la collection hiérarchie est le trait Traversable . Sa seule opération abstraite est

def foreach[U](f: Elem => U)

L'opération est destinée à parcourir tous les éléments de la collection, et d'appliquer l'opération donnée f à chaque élément. L'application est faite pour son effet secondaire seulement; en fait n'importe quel résultat de fonction de f est écarté par foreach.

objets traversables peuvent être finis ou infinis. Un exemple d'un objet traversant infini est le flux de nombres naturels Stream.from(0) . La méthode hasDefiniteSize indique si une collecte est éventuellement infini. Si hasDefiniteSize retourne vrai, la collection est certainement finie. Si elle retourne false, l' la collection n'a pas été entièrement élaboré encore, de sorte qu'il pourrait être infinie ou finie.

cette classe définit des méthodes qui peuvent être mises en œuvre efficacement en termes de foreach (plus de 40 d'entre eux).

"15193560920 Des" Traits De Caractère Itératif

ce trait déclare une méthode abstraite iterator qui renvoie un itérateur qui les rendements de tous les éléments un par un. La méthode foreach dans Iterable est implémentée en termes de iterator . Les sous-classes de Iterable supplantent souvent foreach avec une implémentation directe pour l'efficacité.

Classe Iterable ajoute également quelques méthodes moins souvent utilisées à Traversable , qui ne peut être mis en œuvre efficacement que si un iterator est disponible. Ils sont résumés ci-dessous.

xs.iterator          An iterator that yields every element in xs, in the same order as foreach traverses elements.
xs takeRight n       A collection consisting of the last n elements of xs (or, some arbitrary n elements, if no order is defined).
xs dropRight n       The rest of the collection except xs takeRight n.
xs sameElements ys   A test whether xs and ys contain the same elements in the same order

autres Traits

après Iterable viennent trois traits de base qui en héritent: Seq , Set , et Map . Tous les trois ont une méthode apply et tous les trois mettent en œuvre le trait PartialFunction , mais le sens de apply est différent dans chaque cas.

je crois que le sens de Seq , Set et Map est intuitif. Après eux, les classes se divisent en implémentations spécifiques qui offrir des garanties particulières en ce qui concerne la performance, et les méthodes qu'elle met à disposition à la suite de celle-ci. Il existe aussi des traits avec d'autres raffinements, tels que LinearSeq , IndexedSeq et SortedSet .

La liste ci-dessous peut être améliorée. Laissez un commentaire avec des suggestions et je vais arranger ça.

classes de Base et Traits

  • Traversable -- base classe de collection. Peut être implémenté simplement avec foreach .
    • TraversableProxy -- Proxy pour un Traversable . Il suffit de pointer self vers la vraie collection.
    • TraversableView -- Un Traversable avec certains non-méthodes strictes.
    • TraversableForwarder -- transmet la plupart des méthodes à underlying , sauf toString , hashCode , equals , stringPrefix , newBuilder , view et tous les appels créant un nouvel objet itérable du même genre.
    • mutable.Traversable et immutable.Traversable -- même chose que Traversable , mais de restreindre le type de collection.
    • autres cas spéciaux Iterable les classes, telles que MetaData , existent.
    • Iterable -- une collection pour laquelle un Iterator peut être créé (par iterator ).
      • IterableProxy , IterableView , mutable et immutable.Iterable .
  • Iterator -- un trait qui n'est pas descendant de Traversable . Définir next et hasNext .
    • CountedIterator -- un Iterator définissant count , qui renvoie les éléments vus jusqu'à présent.
    • BufferedIterator -- définit head , qui renvoie l'élément suivant sans le consommer.
    • autres cas spéciaux Iterator classes , telles que Source , existe.

Les Cartes

  • Map -- un Iterable de Tuple2 , qui fournit également des méthodes pour récupérer une valeur (le deuxième élément du tuple) donnée une clé (le premier élément du tuple). Étend PartialFunction aussi.
    • MapProxy -- Un Proxy pour un Map .
    • DefaultMap -- Un trait de mise en œuvre de certaines Map 's méthodes abstraites.
    • SortedMap -- A Map dont les clés sont triées.
      • immutable.SortMap
        • immutable.TreeMap -- une classe implémentant immutable.SortedMap .
    • immutable.Map
      • immutable.MapProxy
      • immutable.HashMap -- d'Une classe implémentant immutable.Map grâce à une clé de hachage.
      • immutable.IntMap -- d'Une classe implémentant immutable.Map spécialisé pour les Int les clés. Utilise un arbre basé sur les chiffres binaires de clés.
      • immutable.ListMap -- d'Une classe implémentant immutable.Map par le biais de listes.
      • immutable.LongMap -- d'Une classe implémentant immutable.Map spécialisé pour clés Long . Voir IntMap .
      • il y a des classes supplémentaires optimisées pour un nombre spécifique d'éléments.
    • mutable.Map
      • mutable.HashMap -- une classe de mise en œuvre mutable.Map par le biais de clavetage.
      • mutable.ImmutableMapAdaptor -- d'Une classe implémentant une mutable.Map à partir d'un immutable.Map .
      • mutable.LinkedHashMap -- ?
      • mutable.ListMap -- d'Une classe implémentant mutable.Map par le biais de listes.
      • mutable.MultiMap -- une classe acceptant plus d'une valeur distincte pour chaque clé.
      • mutable.ObservableMap -- A mixin qui, lorsqu'il est mélangé avec un Map , publie des événements aux observateurs à travers une interface Publisher .
      • mutable.OpenHashMap -- Une classe fondé sur un algorithme de hachage.
      • mutable.SynchronizedMap -- A mixin qui doit être mélangé avec un Map pour en fournir une version avec des méthodes synchronisées.
      • mutable.MapProxy .

Les Séquences

  • Seq -- une séquence d'éléments. L'hypothèse d'une taille bien définie et répétition des éléments. Étend PartialFunction aussi.
    • IndexedSeq -- séquences supportant L'accès à l'élément O(1) et le calcul de la longueur O (1).
      • IndexedSeqView
      • immutable.PagedSeq -- une implémentation de IndexedSeq où les éléments sont produits à la demande par une fonction transmise par le constructeur.
      • immutable.IndexedSeq
        • immutable.Range -- une séquence délimitée d'entiers, fermée sur l'extrémité inférieure, ouverte sur l'extrémité supérieure, et avec un pas.
          • immutable.Range.Inclusive -- un Range fermé sur le haut aussi bien.
          • immutable.Range.ByOne -- A Range dont le pas est 1.
        • immutable.NumericRange -- une version plus générique de Range qui fonctionne avec n'importe quel Integral .
          • immutable.NumericRange.Inclusive , immutable.NumericRange.Exclusive .
          • immutable.WrappedString , immutable.RichString -- Wrappers qui permet de voir un String comme un Seq[Char] , tout en préservant les méthodes String . Je ne suis pas sûr de ce que la différence entre eux est.
      • mutable.IndexedSeq
        • mutable.GenericArray -- une structure de type tableau Seq . Notez que la "classe" Array est le Array de Java , qui est plus une méthode de stockage de mémoire qu'une classe.
        • mutable.ResizableArray -- classe interne utilisée par les classes basées sur des tableaux redimensionnables.
        • mutable.PriorityQueue , mutable.SynchronizedPriorityQueue -- Classes mettant en œuvre les files d'attente priorisées -- les files d'attente où les éléments sont classés selon un ordre de Ordering en premier et un ordre de file d'attente en dernier.
        • mutable.PriorityQueueProxy -- un résumé Proxy pour un PriorityQueue .
    • LinearSeq -- un trait pour les séquences linéaires, avec un temps efficace pour isEmpty , head et tail .
      • immutable.LinearSeq
        • immutable.List -- une mise en œuvre immuable, liée par un seul lien, d'une liste.
        • immutable.Stream -- paresseux liste. Ses éléments ne sont calculés que sur demande, mais memoized (conservé en mémoire) par la suite. Elle peut être théoriquement infinie.
      • mutable.LinearSeq
        • mutable.DoublyLinkedList -- une liste avec mutable prev , head ( elem ) et tail ( next ).
        • mutable.LinkedList -- Une liste avec mutables head ( elem ) et tail ( next ).
        • mutable.MutableList -- Classe utilisée en interne pour implémenter des classes basées sur des listes mutables.
          • mutable.Queue , mutable.QueueProxy -- une structure de données optimisée pour les opérations FIFO (First-In, First-Out).
          • mutable.QueueProxy -- Proxy pour un mutable.Queue .
    • SeqProxy , SeqView , SeqForwarder
    • immutable.Seq
      • immutable.Queue -- une classe implémentant une structure de données FIFO-optimisée (premier entré, premier sorti). Il n'y a pas de superclasse commune pour les files d'attente mutable et immutable .
      • immutable.Stack -- d'Une classe implémentant une méthode LIFO-optimisé (Last-In, First-Out) structure de données. Il n'y a pas de superclasse commune des deux piles mutable immutable .
      • immutable.Vector -- ?
      • scala.xml.NodeSeq -- Une institution spécialisée de la classe XML qui s'étend immutable.Seq .
      • immutable.IndexedSeq -- comme vu ci-dessus.
      • immutable.LinearSeq -- comme vu ci-dessus.
    • mutable.ArrayStack -- d'Une classe implémentant une méthode LIFO-optimisé la structure de données à l'aide de tableaux. Soi-disant nettement plus rapide que la normale de la pile.
    • mutable.Stack , mutable.SynchronizedStack -- les Classes mise en œuvre d'une structure de données optimisée par le principe du dernier entré, premier sorti.
    • mutable.StackProxy -- Proxy pour un mutable.Stack ..
    • mutable.Seq
      • mutable.Buffer -- séquence d'éléments pouvant être changée en ajoutant, en préparant ou en insérant de nouveaux membres.
        • mutable.ArrayBuffer -- une implémentation de la classe mutable.Buffer , avec un temps amorti constant pour l'ajout, la mise à jour et l'accès aléatoire opérations. Il comporte des sous-classes spécialisées, telles que NodeBuffer .
        • mutable.BufferProxy , mutable.SynchronizedBuffer .
        • mutable.ListBuffer -- un buffer appuyé par une liste. Il fournit le temps constant ajoute et prépare, la plupart des autres opérations étant linéaire.
        • mutable.ObservableBuffer -- A mixin trait qui, lorsqu'il est mélangé à un Buffer , fournit des événements de notification par le biais d'un Publisher interface.
        • mutable.IndexedSeq -- comme vu ci-dessus.
        • mutable.LinearSeq -- comme vu ci-dessus.

Les Ensembles

  • Set -- un ensemble est une collection qui comprend au plus un objet.
    • BitSet -- un ensemble d'entiers stockés comme un bitset.
      • immutable.BitSet
      • mutable.BitSet
    • SortedSet , Un ensemble dont les éléments sont ordonnés.
      • immutable.SortedSet
        • immutable.TreeSet -- une implémentation d'un SortedSet basé sur un arbre.
    • SetProxy -- Proxy pour un Set .
    • immutable.Set
      • immutable.HashSet -- une implémentation de Set basée sur le hachage d'éléments.
      • immutable.ListSet -- Une mise en œuvre de Set sur la base de listes.
      • les classes d'ensembles supplémentaires existent pour fournir des implémentations optimisées pour les ensembles de 0 à 4 éléments.
      • immutable.SetProxy -- Proxy pour un immuable Set .
    • mutable.Set
      • mutable.HashSet -- une implémentation de Set basée sur le hachage d'éléments.
      • mutable.ImmutableSetAdaptor -- d'Une classe implémentant une mutable Set de l'immuable Set .
      • LinkedHashSet -- Une mise en œuvre de Set sur la base de listes.
      • ObservableSet -- A mixin trait qui, lorsqu'il est mélangé avec un Set , fournit des événements de notification par l'intermédiaire d'une interface Publisher .
      • SetProxy -- Proxy pour un Set .
      • SynchronizedSet -- A mixin trait qui, lorsqu'il est mélangé avec un Set , fournit des événements de notification par l'intermédiaire d'une interface Publisher .

  • Pourquoi l', telles que les classes existent (par exemple TraversableLike)

ceci a été fait pour atteindre la réutilisation maximale du code. L'implémentation concrète Générique pour les classes avec une certaine structure (un traversable, une carte, etc.) est faite dans les classes similaires. Les classes destinées à la consommation générale, donc, priment les méthodes sélectionnées qui peuvent être optmized.

  • à quoi servent les méthodes d'accompagnement (p. ex. énumérer.companion)

le constructeur des classes, c'est-à-dire l'objet qui sait créer des instances de cette classe d'une manière qui peut être utilisée par des méthodes comme map , est créé par une méthode dans l'objet compagnon. Donc, pour construire un objet de type X, j'ai besoin d'obtenir ce builder à partir de l'objet compagnon de X. malheureusement, il n'y a aucun moyen, en Scala, de obtenez de la classe X à l'objet X. À cause de cela, il y a une méthode définie dans chaque instance de X, companion , qui renvoie l'objet compagnon de la classe X.

bien qu'il puisse y avoir une certaine utilisation pour une telle méthode dans les programmes normaux, son objectif est de permettre la réutilisation de code dans la bibliothèque de collection.

  • Comment je sais ce que les objets implicites sont dans la portée, à un moment donné

vous n'êtes pas censé de soins à ce sujet. Ils sont implicites précisément de sorte que vous n'avez pas besoin de comprendre comment le faire fonctionner.

ces implicits existent pour permettre aux méthodes sur les collections d'être définies sur les classes mères mais toujours retourner une collection du même type. Par exemple , la méthode est définie sur TraversableLike , mais si vous avez utilisé sur un List vous obtiendrez un List de retour.

188
répondu Daniel C. Sobral 2011-12-02 18:08:40