Map — dictionnaires finis, ordonnés et immuables
Synopsis
data Map k v = Tip | Bin Nat k v (Map k v) (Map k v)
Un dictionnaire fini des clés vers les valeurs. Les clés sont ordonnées par leur instance Ord, et l'arbre reste équilibré (un arbre binaire de recherche équilibré par poids, dans le style du Data.Map de Haskell et du Data.SortedMap d'Idris), donc lookup, insert et delete sont en O(log n). L'itération (toList, keys, replis, show) suit toujours l'ordre croissant des clés : elle est déterministe — un dictionnaire s'affiche et se compare pareil quelle que soit sa construction.
Le nombre d'entrées est mémorisé dans chaque nœud, donc size est O(1) et l'équilibrage ne recompte rien. INVARIANT (maintenu par l'API ; ne construisez pas de nœuds Bin à la main) : dans Bin _ k _ l r, toute clé de l est < k, toute clé de r est > k, et size l / size r diffèrent d'au plus un facteur constant.
size : Map k v -> Nat
Le nombre de nœuds, mémorisé (O(1)).
empty : Map k v
singleton : k -> v -> Map k v
Un dictionnaire à une seule entrée.
isEmpty : Map k v -> Bool
True si le dictionnaire n'a aucune entrée.
lookup : Ord k => k -> Map k v -> Maybe v
Cherche la valeur d'une clé. Total : Nothing quand la clé est absente.
member : Ord k => k -> Map k v -> Bool
True si la clé a une entrée.
findWithDefault : Ord k => v -> k -> Map k v -> v
La valeur d'une clé, ou la valeur par défaut fournie quand la clé est absente.
(!) : Ord k => Map k v -> k -> Maybe v
Indice sûr m[k]? — Nothing si la clé est absente.
index : Ord k => Map k v -> k -> v
Indice direct m[k] — panique si la clé est absente.
set : Ord k => Map k v -> k -> v -> Map k v
Mise à jour indexée m { [k] := v } — insère/remplace la valeur à k.
insert : Ord k => k -> v -> Map k v -> Map k v
Insère une paire clé/valeur. Si la clé est déjà présente, sa valeur est remplacée.
insertWith : Ord k => (v -> v -> v) -> k -> v -> Map k v -> Map k v
Insertion avec combinaison. Si la clé est déjà présente, stocke f newValue oldValue ; sinon insère newValue.
adjust : Ord k => (v -> v) -> k -> Map k v -> Map k v
Applique une fonction à la valeur d'une clé, si présente (structure inchangée).
delete : Ord k => k -> Map k v -> Map k v
Retire une clé (sans effet si absente).
toList : Map k v -> List (k, v)
Toutes les entrées en liste de paires, en ordre croissant des clés.
keys : Map k v -> List k
values : Map k v -> List v
Les valeurs, ordonnées par leurs clés.
fromList : Ord k => List (k, v) -> Map k v
Bâtit un dictionnaire depuis une liste de paires. Si une clé apparaît plusieurs fois, la dernière occurrence gagne (cohérent avec des insert répétés).
map : (v -> w) -> Map k v -> Map k w
Applique une fonction à chaque valeur (clés et forme inchangées).
mapWithKey : (k -> v -> w) -> Map k v -> Map k w
Applique une fonction à chaque valeur, avec accès à la clé.
foldr : (v -> b -> b) -> b -> Map k v -> b
Replie les valeurs en ordre croissant des clés.
foldl : (b -> v -> b) -> b -> Map k v -> b
Repli à gauche des valeurs, en ordre croissant des clés.
foldrWithKey : (k -> v -> b -> b) -> b -> Map k v -> b
Replie les entrées (clé et valeur) en ordre croissant des clés.
filterWithKey : Ord k => (k -> v -> Bool) -> Map k v -> Map k v
Ne garde que les entrées dont clé/valeur satisfont le prédicat.
filter : Ord k => (v -> Bool) -> Map k v -> Map k v
Ne garde que les entrées dont la valeur satisfait le prédicat.
unionWith : Ord k => (v -> v -> v) -> Map k v -> Map k v -> Map k v
Union avec combinaison. Sur une clé partagée, le résultat tient f leftValue rightValue.
union : Ord k => Map k v -> Map k v -> Map k v
Union biaisée à gauche : sur une clé partagée, on garde la valeur du dictionnaire de gauche.
intersectionWith : Ord k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
Intersection avec combinaison : les clés présentes des deux côtés, valeur f leftValue rightValue.
intersection : Ord k => Map k a -> Map k b -> Map k a
Intersection biaisée à gauche : les clés des deux côtés, la valeur de gauche.
difference : Ord k => Map k a -> Map k b -> Map k a
Les entrées du dictionnaire de gauche dont la clé n'est pas dans celui de droite.