Les Listes De Rock
De loin le plus sympathique de la structure de données pour les données séquentielles en Haskell est la Liste
data [a] = a:[a] | []
Les listes vous donner Θ(1) cons et le pattern matching. La bibliothèque standard, et d'ailleurs le prélude, est utile la liste des fonctions qui doivent litière de votre code (foldr,map,filter). Les listes sont persistantes , aka purement fonctionnel, qui est très agréable. Haskell listes ne sont pas vraiment des "listes" parce qu'ils sont coinductive (d'autres langues de l'appel de ces cours d'eau), donc les choses comme
ones :: [Integer]
ones = 1:ones
twos = map (+1) ones
tenTwos = take 10 twos
travail à merveille. Infini de structures de données rock.
Les listes en Haskell fournir une interface un peu comme les itérateurs dans des langages impératifs (à cause de la paresse). Ainsi, il est logique qu'ils sont largement utilisés.
Sur l'autre main
Le premier problème avec les listes, c'est que pour l'indice en (!!) prend Θ(k) temps, ce qui est ennuyeux. Aussi, ajoute peut être lent, ++, mais Haskell paresseux modèle d'évaluation signifie que ceux-ci peuvent être traités comme entièrement amortis, si ils arrivent à tous.
Le deuxième problème avec les listes, c'est qu'ils ont une mauvaise localisation des données. Réel processeurs impliquent des constantes lorsque les objets en mémoire ne sont pas disposés les uns à côté des autres. Donc, en C++ std::vector a plus vite "snoc" (mettre les objets à la fin) que toute pure lié structure de données de liste, je connais, mais ce n'est pas un persistant structure de données, donc moins convivial que Haskell listes.
Le troisième problème avec les listes, c'est qu'ils ont une mauvaise optimisation de l'espace. Des bouquets de extra pointeurs de pousser votre stockage (par un facteur constant).
Les Séquences Sont Fonctionnels
Data.Sequence fondé en interne sur les doigt d'arbres (je sais, vous ne voulez pas savoir ce qui signifie qu'ils ont des belles propriétés
- Purement fonctionnelle.
Data.Sequence est entièrement persistant structure de données.
- Darn accès rapide au début et à la fin de l'arbre. Θ(1) (amorti) pour obtenir le premier ou dernier élément, ou pour ajouter des arbres. À la chose listes sont les plus rapides à,
Data.Sequence est tout au plus une constante plus lent.
- Θ(log n) l'accès au milieu de la séquence. Cela comprend l'insertion de valeurs pour faire de nouvelles séquences
- De haute qualité API
D'autre part, Data.Sequence ne fait pas beaucoup pour la localité des données du problème, et ne fonctionne que pour les finis collections (c'est moins paresseux que les listes)
Les tableaux ne sont pas pour les faibles de cœur
Les tableaux sont l'une des plus importantes structures de données dans les CS, mais ils ne s'intègrent très bien avec le paresseux fonctionnels purs du monde. Les tableaux permettent Θ(1) l'accès au moyen de la collecte et exceptionnellement bon la localité des données/des facteurs constants. Mais, depuis, ils ne s'intègrent très bien dans Haskell, ils sont une douleur à utiliser. Il existe en fait une multitude de différents types de tableau dans la norme actuelle de la bibliothèque. Ces entièrement persistant tableaux, mutable tableaux pour l'IO monade, mutable tableaux pour la ST monade, et non des versions boîtes de ci-dessus. Pour plus d'découvrez le haskell wiki
Vecteur est un "meilleur" de la Matrice de
L' Data.Vector paquet fournit la totalité de la matrice de bonté, un niveau plus élevé et plus propre API. Sauf si vous savez vraiment ce que vous faites, vous devez les utiliser si vous avez besoin de la matrice de performance. Bien-sûr, quelques mises en garde s'appliquent toujours--mutable tableau comme structures de données ne sont tout simplement pas jouer gentil dans le plus pur paresseux langues. Pourtant, parfois, vous voulez que O(1) de la performance, et Data.Vector s'offre à vous dans un utilisable paquet.
Vous avez d'autres options
Si vous voulez juste des listes avec la possibilité d'insérer efficacement à la fin, vous pouvez utiliser une différence de liste. Le meilleur exemple de listes de vissage de la performance tend à provenir [Char] qui le prélude a l'alias String. Char listes convient, mais ont tendance à fonctionner sur l'ordre de 20 fois plus lent que C des chaînes, donc n'hésitez pas à utiliser Data.Text ou le très rapide, Data.ByteString. Je suis sûr qu'il ya d'autres séquence orientée vers les bibliothèques, je ne suis pas la pensée de la droite maintenant.
Conclusion
Plus de 90% du temps j'ai besoin d'un séquentielle collection en Haskell sont les listes de la droite structure de données. Les listes sont comme des itérateurs, les fonctions qui consomment des listes peut facilement être utilisé avec n'importe quel de ces autres structures de données à l'aide de l' toList fonctions qu'ils viennent avec. Dans un monde meilleur le prélude serait entièrement paramétrique de ce type de conteneur il utilise, mais actuellement, [] portées de la bibliothèque standard. Ainsi, l'utilisation de listes (presque) tous les où les est certainement d'accord.
Vous pouvez obtenir totalement paramétrique versions de la plupart des fonctions de liste (et noble)de les utiliser
Prelude.map ---> Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc ---> Data.Foldable.foldr/foldl/etc
Prelude.sequence ---> Data.Traversable.sequence
etc
En fait, Data.Traversable définit une API qui est plus ou moins universel dans toute chose de la liste des "j'aime".
Pourtant, bien que vous pouvez être bon et écrire uniquement paramétrique code, la plupart d'entre nous ne le sont pas et utiliser la liste de tous sur la place. Si vous êtes en apprentissage, je vous suggère fortement de faire trop.
EDIT: sur la Base des commentaires je réalise que je n'ai jamais expliqué lors de l'utilisation de Data.Vector vs Data.Sequence. Les matrices et les Vecteurs extrêmement rapide de l'indexation et de l'effeuillage, mais qui sont fondamentalement transitoire (impératif) structures de données. Pure fonctionnelle des structures de données comme Data.Sequence et [] laisser la plus efficace de produire de nouvelles valeurs à partir d'anciennes valeurs, comme si vous aviez modifié les anciennes valeurs.
newList oldList = 7 : drop 5 oldList
ne pas modifier ancienne liste, et il n'a pas à le copier. Donc, même si l' oldList est incroyablement longue, cette "modification" sera très rapide. De la même façon
newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence
va produire une nouvelle séquence avec un newValue à la place de ses 3000 élément. Encore une fois, il ne veut pas détruire l'ancienne séquence, il crée un nouveau. Mais, il le fait de manière très efficace, en prenant en O(log(min(k,k-n)) où n est la longueur de la séquence, et k est l'indice que vous modifiez.
Vous ne pouvez pas facilement le faire avec Vectors et Arrays. Ils peuvent être modifiés , mais qui est réel impératif de modification, et donc ne peut pas être fait régulièrement du code Haskell. Cela signifie que les opérations dans l' Vector package de faire des modifications comme snoc et cons ont copier la totalité du vecteur afin de prendre l' O(n) du temps. La seule exception à cela est que vous pouvez utiliser la mutable version (Vector.Mutable) à l'intérieur de l' ST monade (ou IO) et de faire toutes vos modifications, comme vous le feriez dans un langage impératif. Lorsque vous avez terminé, vous "bloquer" votre vecteur de tourner dans les dans les lois immuables de la structure que vous souhaitez utiliser avec le code pur.
Mon sentiment est que vous devez par défaut à l'aide d' Data.Sequence si une liste n'est pas approprié. Utiliser Data.Vector seulement si votre modèle d'utilisation n'implique pas de faire de nombreuses modifications, ou si vous avez besoin de très haute performance dans le ST/IO monades.
Si tout cela parler de la ST monade ne vous trompez pas: tous les plus de raison de s'en tenir à la pure rapide et beau Data.Sequence.
