Retour au sommaire.
Un autre usage commun des listes est d'implémenter une structure de dictionnaire simplement, en utilisant une liste de paires (clé, valeur). Bien sûr, la complexité des opérations de recherche et de suppression n'est pas très bonne avec les listes (linéaire en la longueur de la liste), mais pour des dictionnaires de petites tailles, comme on en utilise souvent, c'est suffisant. Pour les dictionnaires plus gros, nous apprendrons à utiliser les modules Set et Map qui implémentent des arbres binaires de recherche.
Le type d'une liste associative, avec des clés de type key et des valeurs de type value est donc :
La librairie standard définie directement les opérations de dictionnaires :
l'insertion se fait comme une insertion usuelle en tête de liste,
mem_assoc implémente le test d'appartenance,
assoc recherche la valeur associée à une clé, et provoque une erreur si la clé est absente (donc il faut penser à tester si la clé est présente avant),
remove_assoc implémente la suppression d'une clé, ou plus exactement de la première occurence de la clé dans la liste.
val mem_assoc : 'key -> ('key * 'value) list -> bool
val assoc : 'key -> ('key * 'value) list -> 'value
val remove : 'key -> ('key * 'value) list -> ('key * 'value) list
Core.Std.List isole les opérations de listes associatives dans le module Core.Std.List.Assoc. Les fonctions sont plus conventionnellement nommées comme des fonctions de dictionnaires :
val List.Assoc.add :
('key * 'value) list -> 'key -> 'value -> ('key * 'value) list
val List.Assoc.find :
('key * 'value) list -> 'key -> 'value option
val List.Assoc.mem :
('key * 'value) list -> 'key -> bool
val List.Assoc.remove :
('key * 'value) list -> 'key -> ('key * 'value) list
let paradigm_of_language =
List.fold2_exn
["java"; "C"; "Ocaml"; "C++"; "python"; "Haskell"]
["object"; "procedural"; "functional strict"; "who knows?"; "script"; "purely functional lazy"]
~init:[]
~f:List.Assoc.add
let get_paradigm language_name =
List.Assoc.find paradigm_of_language language_name
|> Option.value_with_default "I don't know"
let res = get_paradigm "Ocaml"
Notons que find retourne une option, ce qui évite toute possibilité d'erreur à l'exécution. assoc fournit aussi des fonctions map et inverse, et toutes ces fonctions acceptent comme argument optionnel l'opérateur d'égalité à utiliser sur le type des clés.
Retour au sommaire.
