Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
Representation of a structure mapping unique keys to values. The internal structure is an AVL tree.
Synopsis
- data Map k a
- difference :: Ord k => Map k a -> Map k b -> Map k a
- intersection :: Ord k => Map k a -> Map k b -> Map k a
- union :: Ord k => Map k a -> Map k a -> Map k a
- empty :: Map k a
- fromList :: Ord k => [(k, a)] -> Map k a
- singleton :: k -> a -> Map k a
- toAscList :: Map k a -> [(k, a)]
- toDescList :: Map k a -> [(k, a)]
- foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b
- foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
- adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a
- delete :: Ord k => k -> Map k a -> Map k a
- filter :: Ord k => (a -> Bool) -> Map k a -> Map k a
- filterWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> Map k a
- insert :: Ord k => k -> a -> Map k a -> Map k a
- update :: Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
- isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool
- lookup :: Ord k => k -> Map k a -> Maybe a
- lookupMax :: Map k a -> Maybe a
- lookupMin :: Map k a -> Maybe a
- member :: Ord k => k -> Map k a -> Bool
- null :: Map k a -> Bool
- size :: Map k a -> Int
- traverseWithKey :: Applicative f => (k -> a -> f b) -> Map k a -> f (Map k b)
- valid :: Ord k => Map k a -> Bool
Type
A map from keys of type k to values of type a.
The internal structure is an AVL tree; a tree that is always height-balanced (the absolute value of the level difference between the left and right subtrees is at most 1).
Instances
Foldable (Map k) Source # | |
Defined in Mini.Data.Map fold :: Monoid m => Map k m -> m # foldMap :: Monoid m => (a -> m) -> Map k a -> m # foldMap' :: Monoid m => (a -> m) -> Map k a -> m # foldr :: (a -> b -> b) -> b -> Map k a -> b # foldr' :: (a -> b -> b) -> b -> Map k a -> b # foldl :: (b -> a -> b) -> b -> Map k a -> b # foldl' :: (b -> a -> b) -> b -> Map k a -> b # foldr1 :: (a -> a -> a) -> Map k a -> a # foldl1 :: (a -> a -> a) -> Map k a -> a # elem :: Eq a => a -> Map k a -> Bool # maximum :: Ord a => Map k a -> a # minimum :: Ord a => Map k a -> a # | |
Traversable (Map k) Source # | |
Functor (Map k) Source # | |
Ord k => Monoid (Map k a) Source # | |
Ord k => Semigroup (Map k a) Source # | |
(Show k, Show a) => Show (Map k a) Source # | |
(Eq k, Eq a) => Eq (Map k a) Source # | |
(Ord k, Ord a) => Ord (Map k a) Source # | |
Combination
difference :: Ord k => Map k a -> Map k b -> Map k a Source #
\(O(n \log n)\) Map difference (matching only on keys)
intersection :: Ord k => Map k a -> Map k b -> Map k a Source #
\(O(n \log n)\) Left-biased map intersection (matching only on keys)
union :: Ord k => Map k a -> Map k a -> Map k a Source #
\(O(n \log n)\) Left-biased map union (matching only on keys)
Construction
fromList :: Ord k => [(k, a)] -> Map k a Source #
\(O(n \log n)\) From a tail-biased list of (key, value)
pairs to a map
with bins containing the keys and values
Conversion
toAscList :: Map k a -> [(k, a)] Source #
\(O(n)\) From a map to a list of (key, value)
pairs in key-ascending
order
toDescList :: Map k a -> [(k, a)] Source #
\(O(n)\) From a map to a list of (key, value)
pairs in key-descending
order
Fold
foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b Source #
\(O(n)\) From a left-associative operation on keys and values, a starting accumulator and a map to a thing
foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b Source #
\(O(n)\) From a right-associative operation on keys and values, a starting accumulator and a map to a thing
Modification
adjust :: Ord k => (a -> a) -> k -> Map k a -> Map k a Source #
\(O(\log n)\) From an operation, a key and a map to the map adjusted by applying the operation to the value associated with the key
delete :: Ord k => k -> Map k a -> Map k a Source #
\(O(\log n)\) From a key and a map to the map without the key
filter :: Ord k => (a -> Bool) -> Map k a -> Map k a Source #
\(O(n)\) From a predicate and a map to the map with values satisfying the predicate
filterWithKey :: Ord k => (k -> a -> Bool) -> Map k a -> Map k a Source #
\(O(n)\) From a predicate and a map to the map with keys and values satisfying the predicate
insert :: Ord k => k -> a -> Map k a -> Map k a Source #
\(O(\log n)\) From a key, a value and a map to the map including a bin containing the key and the value
Query
isSubmapOf :: (Ord k, Eq a) => Map k a -> Map k a -> Bool Source #
\(O(n \log n)\) From a map and another map to whether the former is a submap of the latter (matching on keys and values)
lookup :: Ord k => k -> Map k a -> Maybe a Source #
\(O(\log n)\) From a key and a map to the value associated with the key in the map
lookupMax :: Map k a -> Maybe a Source #
\(O(\log n)\) From a map to the value associated with the maximum key in the map
lookupMin :: Map k a -> Maybe a Source #
\(O(\log n)\) From a map to the value associated with the minimum key in the map
member :: Ord k => k -> Map k a -> Bool Source #
\(O(\log n)\) From a key and a map to whether the key is in the map
Traversal
traverseWithKey :: Applicative f => (k -> a -> f b) -> Map k a -> f (Map k b) Source #
\(O(n)\) From a lifting operation on keys and values and a map to a lifted map