Types de collection F#

  • Article

Consultez cette rubrique pour déterminer quel type de collection F# répond le mieux à un besoin particulier. Ces types de collection diffèrent des types de collection .NET, comme ceux inclus dans l’espace de noms System.Collections.Generic, en ce sens que les types de collection F# sont conçus dans une perspective de programmation fonctionnelle plutôt que dans une perspective orientée objet. Plus précisément, seule la collection de tableaux a des éléments mutables. Par conséquent, lorsque vous modifiez une collection, vous créez un instance de la collection modifiée au lieu de modifier la collection d’origine.

Les types de collection diffèrent également par le type de structure de données dans lequel les objets sont stockés. Les structures de données telles que les tables de hachage, les listes liées et les tableaux ont des caractéristiques de performances différentes et un ensemble différent d’opérations disponibles.

Table des types de collection

Le tableau suivant montre les types de collection F#.

Type Description Liens associés
Liste Série immuable et ordonnée d’éléments du même type. Implémentée en tant que liste liée. Listes

Module List
Matrice Collection de taille fixe, de base zéro et mutable d’éléments de données consécutifs qui sont tous du même type. Tableaux

Module Array

Module Array2D

Module Array3D
seq Série logique d’éléments qui sont tous d’un seul type. Les séquences s’avèrent particulièrement utiles quand vous disposez d’une collection de données volumineuse et ordonnée, mais que vous ne vous attendez pas nécessairement à utiliser tous les éléments. Les éléments de séquence individuels sont calculés uniquement en fonction des besoins, de sorte qu’une séquence peut fonctionner mieux qu’une liste si tous les éléments ne sont pas utilisés. Les séquences sont représentées par le type seq<'T>, qui est un alias pour IEnumerable<T>. Par conséquent, tout type .NET Framework qui implémente System.Collections.Generic.IEnumerable<'T> peut être utilisé en tant que séquence. Séquences

Seq Module
Map Dictionnaire immuable d’éléments. Les éléments sont accessibles par clé. Map Module
Définir Ensemble immuable basé sur des arborescences binaires, où la comparaison correspond à la fonction de comparaison structurelle F#, qui utilise potentiellement des implémentations de l’interface System.IComparable sur des valeurs de clés. Set Module

Tableau des fonctions

Cette section compare les fonctions disponibles sur les types de collection F#. La complexité du calcul de la fonction est donnée, où N est la taille de la première collection et M la taille de la seconde collection, le cas échéant. Un tiret (-) indique que cette fonction n’est pas disponible sur la collection. Étant donné que les séquences sont évaluées lentement, une fonction comme Seq.distinct peut correspondre à O(1) car elle est immédiatement retournée, même si elle affecte toujours les performances de la séquence lorsqu’elle est énumérée.

Fonction Array List Séquence Mappage Définissez Description
append O(N) O(N) O(N) - - Renvoie une nouvelle collection qui contient les éléments de la première collection, suivis des éléments de la seconde collection.
add - - - O(log(N)) O(log(N)) Retourne une nouvelle collection avec l’élément ajouté.
average O(N) O(N) O(N) - - Retourne la moyenne des éléments inclus dans la collection.
averageBy O(N) O(N) O(N) - - Retourne la moyenne des résultats de la fonction fournie appliquée à chaque élément.
blit O(N) - - - - Copie une section d’un tableau.
cache - - O(N) - - Calcule et stocke les éléments d’une séquence.
Caster - - O(N) - - Convertit les éléments vers le type spécifié.
choose O(N) O(N) O(N) - - Applique la fonction donnée f à chaque élément x de la liste. Retourne la liste qui contient les résultats pour chaque élément où la fonction retourne Some(f(x)).
collect O(N) O(N) O(N) - - Applique la fonction donnée à chaque élément de la collection, concatène tous les résultats et retourne la liste combinée.
compareWith - - O(N) - - Compare deux séquences à l’aide de la fonction de comparaison donnée, élément par élément.
concat O(N) O(N) O(N) - - Combine l’énumération des énumérations donnée en tant qu’énumération concaténée unique.
contains - - - - O(log(N)) Retourne true si le jeu contient l’élément spécifié.
containsKey - - - O(log(N)) - Teste si un élément se trouve dans le domaine d’une carte.
count - - - - O(N) Retourne le nombre d'éléments figurant dans le jeu.
countBy - - O(N) - - Applique une fonction génératrice de clé à chaque élément d’une séquence et retourne une séquence qui produit des clés uniques et leur nombre d’occurrences dans la séquence d’origine.
copy O(N) - O(N) - - Copie la collection.
créer O(N) - - - - Crée un tableau d’éléments entiers qui sont tous initialement la valeur donnée.
delay - - O(1) - - Retourne une séquence créée à partir de la spécification différée donnée d’une séquence.
différence - - - - O(M*log(N)) Retourne un nouvel ensemble avec les éléments du second ensemble supprimés du premier.
distinct O(1)* Retourne une séquence qui ne contient aucune entrée en double selon les comparaisons de hachage générique et d’égalité sur les entrées. Si un élément se produit plusieurs fois dans la séquence, les occurrences ultérieures sont ignorées.
distinctBy O(1)* Retourne une séquence qui ne contient aucune entrée en double selon les comparaisons de hachage générique et d’égalité sur les clés retournées par la fonction génératrice de clé donnée. Si un élément se produit plusieurs fois dans la séquence, les occurrences ultérieures sont ignorées.
empty O(1) O(1) O(1) O(1) O(1) Crée une collection vide.
exists O(N) O(N) O(N) O(log(N)) O(log(N)) Teste si un élément de la séquence satisfait au prédicat donné.
exists2 O(min(N,M)) - O(min(N,M)) Teste si une paire d’éléments correspondants des séquences d’entrée satisfait au prédicat donné.
fill O(N) Définit une plage d’éléments du tableau sur la valeur donnée.
filter O(N) O(N) O(N) O(N) O(N) Retourne une nouvelle collection qui contient uniquement les éléments de la collection pour lesquels le prédicat donné retourne true.
trouver O(N) O(N) O(N) O(log(N)) - Retourne le premier élément pour lequel la fonction donnée retourne true. Retourne System.Collections.Generic.KeyNotFoundException si aucun élément de ce type n’existe.
findIndex O(N) O(N) O(N) - - Retourne l’index du premier élément dans le tableau qui satisfait au prédicat donné. Déclenche System.Collections.Generic.KeyNotFoundException si aucun élément ne satisfait au prédicat.
findKey - - - O(log(N)) - Évalue la fonction sur chaque mappage dans la collection et retourne la clé du premier mappage où la fonction retourne true. Si aucun élément de ce type n’existe, cette fonction déclenche System.Collections.Generic.KeyNotFoundException.
fold O(N) O(N) O(N) O(N) O(N) Applique une fonction à chaque élément de la collection, par le threading d’un argument d’accumulateur dans le calcul. Si la fonction d’entrée est f et que les éléments sont i0...iN, cette fonction calcule f (... (f s i0)...) iN.
fold2 O(N) O(N) - - - Applique une fonction aux éléments correspondants de deux collections, par le threading d’un argument d’accumulateur dans le calcul. Les collections doivent avoir des tailles identiques. Si la fonction d’entrée est f et que les éléments sont i0...iN et j0...jN, cette fonction calcule f (... (f s i0 j0)...) iN jN.
foldBack O(N) O(N) - O(N) O(N) Applique une fonction à chaque élément de la collection, par le threading d’un argument d’accumulateur dans le calcul. Si la fonction d’entrée est f et que les éléments sont i0...iN, cette fonction calcule f i0 (...(f iN s)).
foldBack2 O(N) O(N) - - - Applique une fonction aux éléments correspondants de deux collections, par le threading d’un argument d’accumulateur dans le calcul. Les collections doivent avoir des tailles identiques. Si la fonction d’entrée est f et que les éléments sont i0...iN et j0...jN, cette fonction calcule f i0 j0 (...(f iN jN s)).
forall O(N) O(N) O(N) O(N) O(N) Teste si tous les éléments de la collection satisfont au prédicat donné.
forall2 O(N) O(N) O(N) - - Teste si tous les éléments correspondants de la collection satisfont au prédicat donné par paire.
get / nth O(1) O(N) O(N) - - Retourne un élément de la collection en fonction de son index.
head - O(1) O(1) - - Retourne le premier élément de la collection.
init O(N) O(N) O(1) - - Crée une collection selon la dimension et une fonction de générateur pour calculer les éléments.
initInfinite - - O(1) - - Génère une séquence qui, lorsqu’elle est itérée, retourne des éléments successifs en appelant la fonction donnée.
intersect - - - - O(log(N)*log(M)) Calcule l’intersection de deux ensembles.
intersectMany - - - - O(N1*N2...) Calcule l’intersection d’une séquence d’ensembles. La séquence ne doit pas être vide.
isEmpty O(1) O(1) O(1) O(1) - Retourne true si la collection est vide.
isProperSubset - - - - O(M*log(N)) Retourne true si tous les éléments du premier ensemble se trouvent dans le deuxième ensemble et qu’au moins un élément du deuxième ensemble ne se trouve pas dans le premier.
isProperSuperset - - - - O(M*log(N)) Retourne true si tous les éléments du second ensemble se trouvent dans le premier ensemble et qu’au moins un élément du premier ensemble ne se trouve pas dans le second.
isSubset - - - - O(M*log(N)) Retourne true si tous les éléments du premier ensemble se trouvent dans le deuxième ensemble.
isSuperset - - - - O(M*log(N)) Retourne true si tous les éléments du second ensemble se trouvent dans le premier ensemble.
iter O(N) O(N) O(N) O(N) O(N) Applique la fonction donnée à chaque élément de la collection.
iteri O(N) O(N) O(N) - - Applique la fonction donnée à chaque élément de la collection. L’entier passé à la fonction indique l’index de l’élément.
iteri2 O(N) O(N) - - - Applique la fonction donnée à une paire d’éléments qui sont tirés d’index correspondants dans deux tableaux. L’entier passé à la fonction indique l’index des éléments. Les deux tableaux doivent avoir la même longueur.
iter2 O(N) O(N) O(N) - - Applique la fonction donnée à une paire d’éléments qui sont tirés d’index correspondants dans deux tableaux. Les deux tableaux doivent avoir la même longueur.
last O(1) O(N) O(N) - - Retourne le dernier élément de la collection applicable.
length O(1) O(N) O(N) - - Retourne le nombre d’éléments dans la collection.
carte O(N) O(N) O(1) - - Crée une collection dont les éléments sont les résultats de l’application de la fonction donnée à chaque élément du tableau.
map2 O(N) O(N) O(1) - - Crée une collection dont les éléments sont les résultats de l’application de la fonction donnée aux éléments correspondants des deux collections par paire. Les deux tableaux doivent avoir la même longueur.
map3 - O(N) - - - Crée une collection dont les éléments sont les résultats de l’application de la fonction donnée aux éléments correspondants des trois collections de manière simultanée.
mapi O(N) O(N) O(N) - - Crée un tableau dont les éléments sont les résultats de l’application de la fonction donnée à chaque élément du tableau. L’index entier passé à la fonction indique l’index de l’élément qui est transformé.
mapi2 O(N) O(N) - - - Crée une collection dont les éléments sont les résultats de l’application de la fonction donnée aux éléments correspondants des deux collections par paire, tout en passant également l’index des éléments. Les deux tableaux doivent avoir la même longueur.
max O(N) O(N) O(N) - - Retourne l’élément le plus grand de la collection, comparé à l’aide de l’opérateur max.
maxBy O(N) O(N) O(N) - - Retourne le plus grand élément de la collection, comparé à l’aide de max sur le résultat de la fonction.
maxElement - - - - O(log(N)) Retourne l’élément le plus grand dans l’ensemble en fonction de l’ordre utilisé pour cet ensemble.
minute(s) O(N) O(N) O(N) - - Retourne l’élément le plus petit de la collection, comparé à l’aide de l’opérateur min.
minBy O(N) O(N) O(N) - - Retourne l’élément le plus petit de la collection, comparé à l’aide de l’opérateur min sur le résultat de la fonction.
minElement - - - - O(log(N)) Retourne l’élément le plus faible dans l’ensemble en fonction de l’ordre utilisé pour cet ensemble.
ofArray - O(N) O(1) O(N) O(N) Crée une collection qui contient les mêmes éléments que le tableau donné.
ofList O(N) - O(1) O(N) O(N) Crée une collection qui contient les mêmes éléments que la liste donnée.
ofSeq O(N) O(N) - O(N) O(N) Crée une collection qui contient les mêmes éléments que la séquence donnée.
pairwise - - O(N) - - Retourne une séquence de chaque élément inclus dans la séquence d’entrée et son prédécesseur, à l’exception du premier élément, qui est retourné uniquement en tant que prédécesseur du deuxième élément.
partition O(N) O(N) - O(N) O(N) Fractionne la collection en deux collections. La première collection contient les éléments pour lesquels le prédicat donné retourne true, tandis que la seconde collection contient les éléments pour lesquels le prédicat donné retourne false.
permute O(N) O(N) - - - Retourne un tableau avec tous les éléments permutés en fonction de la permutation spécifiée.
pick O(N) O(N) O(N) O(log(N)) - Applique la fonction donnée aux éléments successifs, en retournant le premier résultat où la fonction retourne Some. Si la fonction ne retourne jamais Some, System.Collections.Generic.KeyNotFoundException est déclenché.
readonly - - O(N) - - Crée un objet de séquence qui délègue à l’objet de séquence donné. Cette opération garantit qu’un cast de type ne peut pas redécouvrir et muter la séquence d’origine. Par exemple, si un tableau est donné, la séquence retournée retourne les éléments du tableau, mais vous ne pouvez pas caster l’objet de séquence retourné en tableau.
reduce O(N) O(N) O(N) - - Applique une fonction à chaque élément de la collection, par le threading d’un argument d’accumulateur dans le calcul. Cette fonction commence par appliquer la fonction aux deux premiers éléments, puis elle passe ce résultat à la fonction avec le troisième élément, et ainsi de suite. La fonction retourne le résultat final.
reduceBack O(N) O(N) - - - Applique une fonction à chaque élément de la collection, par le threading d’un argument d’accumulateur dans le calcul. Si la fonction d’entrée est f et que les éléments sont i0...iN, cette fonction calcule f i0 (...(f iN-1 iN)).
remove - - - O(log(N)) O(log(N)) Supprime un élément du domaine de la carte. Aucune exception n’est levée si l’élément n’est pas présent.
replicate - O(N) - - - Crée une liste d’une longueur spécifiée avec chaque élément défini sur la valeur donnée.
rev O(N) O(N) - - - Retourne une nouvelle liste avec les éléments dans l’ordre inverse.
scan O(N) O(N) O(N) - - Applique une fonction à chaque élément de la collection, par le threading d’un argument d’accumulateur dans le calcul. Cette opération applique la fonction au deuxième argument et au premier élément de la liste. L’opération passe ensuite ce résultat à la fonction avec le deuxième élément, et ainsi de suite. Enfin, l’opération retourne la liste des résultats intermédiaires et le résultat final.
scanBack O(N) O(N) - - - Ressemble à l’opération foldBack, mais retourne les résultats intermédiaires et le résultat final.
singleton - - O(1) - O(1) Retourne une séquence qui ne produit qu’un seul élément.
set O(1) - - - - Définit un élément d’un tableau sur la valeur spécifiée.
skip - - O(N) - - Retourne une séquence qui ignore N éléments de la séquence sous-jacente, puis produit les éléments restants de la séquence.
skipWhile - - O(N) - - Retourne une séquence qui, en cas d’itération, ignore les éléments de la séquence sous-jacente tandis que le prédicat donné retourne true, puis produit les éléments restants de la séquence.
sort O(N*log(N)) average

O(N^2) worst case		 O(N*log(N)) O(N*log(N)) - - Trie la collection par valeur d’élément. Les éléments sont comparés à l’aide de compare.
sortBy O(N*log(N)) average

O(N^2) worst case		 O(N*log(N)) O(N*log(N)) - - Trie la liste donnée à l’aide des clés fournies par la projection donnée. Les clés sont comparées à l’aide de compare.
sortInPlace O(N*log(N)) average

O(N^2) worst case		 - - - - Trie les éléments d’un tableau en le mutant sur place et en utilisant la fonction de comparaison donnée. Les éléments sont comparés à l’aide de compare.
sortInPlaceBy O(N*log(N)) average

O(N^2) worst case		 - - - - Trie les éléments d’un tableau en le mutant sur place et en utilisant la projection donnée pour les clés. Les éléments sont comparés à l’aide de compare.
sortInPlaceWith O(N*log(N)) average

O(N^2) worst case		 - - - - Trie les éléments d’un tableau en le mutant sur place et en utilisant la fonction de comparaison donnée en tant qu’ordre.
sortWith O(N*log(N)) average

O(N^2) worst case		 O(N*log(N)) - - - Trie les éléments d’une collection, en utilisant la fonction de comparaison donnée en tant qu’ordre et en retournant une nouvelle collection.
sub O(N) - - - - Crée un tableau qui contient la sous-plage donnée spécifiée par l’index de départ et la longueur.
Sum O(N) O(N) O(N) - - Retourne la somme des éléments inclus dans la collection.
sumBy O(N) O(N) O(N) - - Retourne la somme des résultats générés en appliquant la fonction à chaque élément de la collection.
tail - O(1) - - - Retourne la liste sans son premier élément.
take - - O(N) - - Retourne les éléments de la séquence jusqu’à un nombre spécifié.
takeWhile - - O(1) - - Retourne une séquence qui, en cas d’itération, produit des éléments de la séquence sous-jacente tandis que le prédicat donné retourne true, puis ne retourne plus aucun élément.
toArray - O(N) O(N) O(N) O(N) Crée un tableau à partir de la collection donnée.
toList O(N) - O(N) O(N) O(N) Crée une liste à partir de la collection donnée.
toSeq O(1) O(1) - O(1) O(1) Crée une séquence à partir de la collection donnée.
truncate - - O(1) - - Retourne une séquence qui, lorsqu’elle est énumérée, ne retourne pas plus de N éléments.
tryFind O(N) O(N) O(N) O(log(N)) - Recherche un élément qui satisfait à un prédicat donné.
tryFindIndex O(N) O(N) O(N) - - Recherche le premier élément qui satisfait à un prédicat donné et retourne l’index de l’élément correspondant, ou None s’il n’existe aucun élément de ce type.
tryFindKey - - - O(log(N)) - Retourne la clé du premier mappage inclus dans la collection qui satisfait au prédicat donné, ou retourne None s’il n’existe aucun élément de ce type.
tryPick O(N) O(N) O(N) O(log(N)) - Applique la fonction donnée aux éléments successifs, en retournant le premier résultat où la fonction retourne Some pour une valeur. S’il n’existe aucun élément de ce type, l’opération retourne None.
unfold - - O(N) - - Retourne une séquence contenant les éléments que le calcul donné génère.
union - - - - O(M*log(N)) Calcule l’union des deux ensembles.
unionMany - - - - O(N1*N2...) Calcule l’union d’une séquence d’ensembles.
unzip O(N) O(N) O(N) - - Fractionne une liste de paires en deux listes.
unzip3 O(N) O(N) O(N) - - Fractionne une liste de triples en trois listes.
windowed - - O(N) - - Retourne une séquence qui produit des fenêtres glissantes d’éléments conteneurs qui sont tirés de la séquence d’entrée. Chaque fenêtre est retournée sous la forme d’un tableau actualisé.
zip O(N) O(N) O(N) - - Combine les deux collections dans une liste de paires. Les deux listes doivent avoir des longueurs égales.
zip3 O(N) O(N) O(N) - - Combine les trois collections dans une liste de triples. Les listes doivent avoir des longueurs égales.

Voir aussi