Copyright | Guillaume Sabbagh 2022 |
---|---|
License | LGPL-3.0-or-later |
Maintainer | guillaumesabbagh@protonmail.com |
Stability | experimental |
Portability | portable |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
A WeakMap
is a Data.Map which does not require the keys to implement the Ord typeclass. It is a weak set of pairs (key,value).
The datatype only assumes its keys are equatable, it is therefore slower to access data than the Data.Map datatype.
We use this datatype because most of the datatypes we care about are not orderable.
Almost all Data.WeakMap functions are implemented so that you can replace a Data.Map import such as
import Data.Map.Strict (Map) import qualified Data.Map.Strict as Map
by a Data.WeakMap import such as
import Data.WeakMap (Map) import qualified Data.WeakMap as Map
without breaking anything in your code.
The only functions for which this would fail are the functions converting maps back into list (they require the Eq typeclass unlike in Data.Map). size
is one of them.
If a function really requires the Ord typeclass to even make sense, then it is not defined in this package, you should use Data.Map.
Note that, just like in Data.Map, the implementation is generally left-biased. Functions that take two maps as arguments and combine them, such as union and intersection, prefer the entries in the first argument to those in the second.
Functions with non colliding names are defined in Data.WeakMap.Safe. Inline functions are written between pipes |
.
This module is intended to be imported qualified, to avoid name clashes with Prelude functions, except for functions in Data.WeakSet.Map, e.g.
import Data.WeakMap (Map) import qualified Data.WeakMap as Map import Data.WeakMap.Safe
Unlike Data.Map, we defer the removing of duplicate keys to the conversion back to a list.
Beware if the map is supposed to contain a lot of duplicate keys, you should purge them yourself by transforming the map into a list and back into a map. The time complexity is always given in function of the number of pairs in the map including the duplicate pairs.
Synopsis
- type AssociationList k v = [(k, v)]
- data Map k v
- weakMap :: AssociationList k v -> Map k v
- weakMapFromSet :: Set (k, v) -> Map k v
- empty :: Map k a
- singleton :: k -> a -> Map k a
- fromSet :: (k -> a) -> Set k -> Map k a
- fromList :: AssociationList k v -> Map k v
- fromListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
- fromListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
- fromAscList :: Eq k => [(k, a)] -> Map k a
- fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
- fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
- fromDistinctAscList :: [(k, a)] -> Map k a
- fromDescList :: Eq k => [(k, a)] -> Map k a
- fromDescListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a
- fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a
- fromDistinctDescList :: [(k, a)] -> Map k a
- insert :: k -> a -> Map k a -> Map k a
- insertWith :: Eq k => (v -> v -> v) -> k -> v -> Map k v -> Map k v
- insertWithKey :: Eq k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
- insertLookupWithKey :: Eq k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
- insertMaybe :: Eq k => k -> Maybe a -> Map k a -> Map k a
- delete :: Eq k => k -> Map k a -> Map k a
- adjust :: Eq k => (a -> a) -> k -> Map k a -> Map k a
- adjustWithKey :: Eq k => (k -> a -> a) -> k -> Map k a -> Map k a
- update :: Eq k => (a -> Maybe a) -> k -> Map k a -> Map k a
- updateWithKey :: Eq k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
- updateLookupWithKey :: Eq k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
- alter :: Eq k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
- alterF :: (Functor f, Eq k) => (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
- lookup :: Eq k => k -> Map k a -> Maybe a
- (!?) :: Eq k => Map k a -> k -> Maybe a
- (!) :: Eq k => Map k a -> k -> a
- (|?|) :: Eq k => Map k v -> k -> Maybe v
- (|!|) :: Eq k => Map k v -> k -> v
- findWithDefault :: Eq k => a -> k -> Map k a -> a
- member :: Eq k => k -> Map k a -> Bool
- notMember :: Eq k => k -> Map k a -> Bool
- size :: Eq k => Map k a -> Int
- null :: Map k a -> Bool
- union :: Eq k => Map k a -> Map k a -> Map k a
- unionWith :: Eq k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
- unionWithKey :: Eq k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
- unions :: Eq k => [Map k a] -> Map k a
- unionsWith :: Eq k => (a -> a -> a) -> [Map k a] -> Map k a
- difference :: Eq k => Map k a -> Map k b -> Map k a
- (\\) :: Eq k => Map k a -> Map k b -> Map k a
- differenceWith :: Eq k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
- differenceWithKey :: Eq k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
- intersection :: Eq k => Map k a -> Map k b -> Map k a
- intersectionWith :: Eq k => (a -> b -> c) -> Map k a -> Map k b -> Map k c
- intersectionWithKey :: Eq k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
- disjoint :: Eq k => Map k a -> Map k b -> Bool
- (|.|) :: Eq b => Map b c -> Map a b -> Map a c
- compose :: Eq b => Map b c -> Map a b -> Map a c
- mergeWithKey :: Eq k => (k -> a -> b -> Maybe c) -> (Map k a -> Map k c) -> (Map k b -> Map k c) -> Map k a -> Map k b -> Map k c
- map :: (a -> b) -> Map k a -> Map k b
- mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
- traverseWithKey :: (Applicative t, Eq k, Eq a) => (k -> a -> t b) -> Map k a -> t (Map k b)
- traverseMaybeWithKey :: (Applicative f, Eq k, Eq a) => (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
- mapAccum :: Eq k => (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
- mapAccumWithKey :: Eq k => (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
- mapAccumRWithKey :: Eq k => (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
- mapKeys :: (k1 -> k2) -> Map k1 a -> Map k2 a
- mapKeysWith :: (Eq k1, Eq k2) => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
- mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a
- foldr :: Eq k => (a -> b -> b) -> b -> Map k a -> b
- foldl :: Eq k => (a -> b -> a) -> a -> Map k b -> a
- foldrWithKey :: (Eq a, Eq k) => (k -> a -> b -> b) -> b -> Map k a -> b
- foldlWithKey :: (Eq k, Eq a) => (b -> k -> a -> b) -> b -> Map k a -> b
- foldMapWithKey :: (Eq a, Eq k, Monoid m) => (k -> a -> m) -> Map k a -> m
- foldr' :: Eq k => (a -> b -> b) -> b -> Map k a -> b
- foldl' :: Eq k => (b -> a -> b) -> b -> Map k a -> b
- foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b
- foldlWithKey' :: (b -> k -> a -> b) -> b -> Map k a -> b
- mapToList :: Eq k => Map k v -> AssociationList k v
- mapToSet :: Eq k => Map k v -> Set (k, v)
- elems :: Eq k => Map k a -> [a]
- elems' :: Eq k => Map k a -> Set a
- values :: Eq k => Map k a -> Set a
- image :: Eq k => Map k a -> Set a
- keys :: Eq k => Map k v -> [k]
- keys' :: Map k v -> Set k
- domain :: Map k a -> Set k
- assocs :: Eq k => Map k a -> [(k, a)]
- keysSet :: Map k a -> Set k
- elemsSet :: Eq k => Map k a -> Set a
- toList :: Eq k => Map k a -> [(k, a)]
- toAscList :: Eq k => Map k a -> [(k, a)]
- toDescList :: Eq k => Map k a -> [(k, a)]
- filter :: (a -> Bool) -> Map k a -> Map k a
- filterWithKey :: (k -> a -> Bool) -> Map k a -> Map k a
- restrictKeys :: Eq k => Map k a -> Set k -> Map k a
- withoutKeys :: Eq k => Map k a -> Set k -> Map k a
- partition :: (a -> Bool) -> Map k a -> (Map k a, Map k a)
- partitionWithKey :: (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
- mapMaybe :: (a -> Maybe b) -> Map k a -> Map k b
- mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b
- mapEither :: (a -> Either b c) -> Map k a -> (Map k b, Map k c)
- mapEitherWithKey :: (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
- isSubmapOf :: (Eq k, Eq a) => Map k a -> Map k a -> Bool
- isSubmapOfBy :: Eq k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
- isProperSubmapOf :: (Eq k, Eq a) => Map k a -> Map k a -> Bool
- isProperSubmapOfBy :: Eq k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
- lookupIndex :: Eq k => k -> Map k a -> Maybe Int
- findIndex :: Eq k => k -> Map k a -> Int
- elemAt :: Eq k => Int -> Map k a -> (k, a)
- updateAt :: Eq k => (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
- deleteAt :: Eq k => Int -> Map k a -> Map k a
- take :: Eq k => Int -> Map k a -> Map k a
- drop :: Eq k => Int -> Map k a -> Map k a
- splitAt :: Eq k => Int -> Map k a -> (Map k a, Map k a)
- idFromSet :: Set a -> Map a a
- memorizeFunction :: (k -> v) -> Set k -> Map k v
- inverse :: (Eq k, Eq v) => Map k v -> Maybe (Map v k)
- pseudoInverse :: Map k v -> Map v k
- enumerateMaps :: (Eq a, Eq b) => Set a -> Set b -> Set (Map a b)
Map type
type AssociationList k v = [(k, v)] Source #
An association list is a list of pairs (key,value).
A weak map is a weak set of pairs (key,value) such that their should only be one pair with a given key.
It is an abstract type, the smart constructor is weakMap
.
Construction
weakMap :: AssociationList k v -> Map k v Source #
O(1). The smart constructor of weak maps. This is the only way of instantiating a Map
.
Takes an association list and returns a function which maps to each key the value associated.
If several pairs have the same keys, they are kept until the user wants an association list back.
weakMapFromSet :: Set (k, v) -> Map k v Source #
fromSet :: (k -> a) -> Set k -> Map k a Source #
O(n). Build a map from a set of keys and a function which for each key computes its value.
From Unordered Lists
fromList :: AssociationList k v -> Map k v Source #
O(1). Alias of weakMap
for backward compatibility with Data.Map.
fromListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a Source #
O(n). Build a map from a list of key/value pairs with a combining function.
fromListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a Source #
O(n). Build a map from a list of key/value pairs with a combining function.
From Ascending Lists
fromAscList :: Eq k => [(k, a)] -> Map k a Source #
Alias for backward compatibility.
fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a Source #
Alias for backward compatibility.
fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a Source #
Alias for backward compatibility.
fromDistinctAscList :: [(k, a)] -> Map k a Source #
Alias for backward compatibility.
From Descending Lists
fromDescList :: Eq k => [(k, a)] -> Map k a Source #
Alias for backward compatibility.
fromDescListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a Source #
Alias for backward compatibility.
fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a Source #
Alias for backward compatibility.
fromDistinctDescList :: [(k, a)] -> Map k a Source #
Alias for backward compatibility.
Insertion
insert :: k -> a -> Map k a -> Map k a Source #
O(1). Insert a new key and value in the map. If the key is already present in the map, the associated value is replaced with the supplied value. insert
is equivalent to
. insertWith
const
insertWith :: Eq k => (v -> v -> v) -> k -> v -> Map k v -> Map k v Source #
O(n). Insert with a function, combining new value and old value. insertWith f key value mp
will insert the pair (key, value) into mp if key does not exist in the function. If the key does exist, the function will insert the pair (key, f new_value old_value).
insertWithKey :: Eq k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a Source #
O(n). Insert with a function, combining key, new value and old value. insertWithKey f key value mp
will insert the pair (key, value) into mp if key does not exist in the function. If the key does exist, the function will insert the pair (key,f key new_value old_value). Note that the key passed to f is the same key passed to insertWithKey
.
insertLookupWithKey :: Eq k => (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a) Source #
O(n). Combines insert operation with old value retrieval. The expression (insertLookupWithKey f k x map)
is a pair where the first element is equal to (lookup k map)
and the second element equal to (insertWithKey f k x map)
.
insertMaybe :: Eq k => k -> Maybe a -> Map k a -> Map k a Source #
O(1). Insert a new key and value if it is Just in the map. If the key is already present in the map, the associated value is replaced with the supplied value.
Deletion/Update
delete :: Eq k => k -> Map k a -> Map k a Source #
O(n). Delete a key and its value from the map. When the key is not a member of the map, the original map is returned.
adjust :: Eq k => (a -> a) -> k -> Map k a -> Map k a Source #
O(n). Update a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned.
adjustWithKey :: Eq k => (k -> a -> a) -> k -> Map k a -> Map k a Source #
O(n). Adjust a value at a specific key. When the key is not a member of the map, the original map is returned.
update :: Eq k => (a -> Maybe a) -> k -> Map k a -> Map k a Source #
O(n). The expression (update f k map)
updates the value x at k (if it is in the map). If (f x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y.
updateWithKey :: Eq k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a Source #
O(n). The expression (updateWithKey f k map)
updates the value x at k (if it is in the map). If (f k x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y.
updateLookupWithKey :: Eq k => (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a) Source #
O(n). Lookup and update. See also updateWithKey
. The function returns changed value, if it is updated. Returns the original key value if the map entry is deleted.
Query
Lookup
lookup :: Eq k => k -> Map k a -> Maybe a Source #
O(n). Just like (|?|)
but the order of argument is reversed. For backward compatibility with Data.Map.
(!) :: Eq k => Map k a -> k -> a Source #
O(n). Find the value at a key. Calls error
when the element can not be found.
Alias of (|!|)
for backward compatibility purposes.
(|?|) :: Eq k => Map k v -> k -> Maybe v Source #
O(n). Lookup the value at a key in the map. If the map is not defined on the given value returns Nothing
, otherwise returns Just
the image.
This function is like lookup
in Data.Map for function (beware: the order of the argument are reversed).
findWithDefault :: Eq k => a -> k -> Map k a -> a Source #
O(n). The expression (findWithDefault def k map)
returns the value at key k or returns default value def when the key is not in the map.
member :: Eq k => k -> Map k a -> Bool Source #
O(n). Is the key a member of the map? See also notMember
.
Size
Combine
Union
union :: Eq k => Map k a -> Map k a -> Map k a Source #
O(n). The expression (
takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered. union
t1 t2)
unionWith :: Eq k => (a -> a -> a) -> Map k a -> Map k a -> Map k a Source #
O(n). Union with a combining function.
unionWithKey :: Eq k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a Source #
O(n). Union with a combining function.
let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
unions :: Eq k => [Map k a] -> Map k a Source #
The union of a list of maps: (unions == foldl union empty)
.
unionsWith :: Eq k => (a -> a -> a) -> [Map k a] -> Map k a Source #
The union of a list of maps, with a combining operation: (unionsWith f == foldl (unionWith f) empty)
.
Difference
difference :: Eq k => Map k a -> Map k b -> Map k a Source #
O(n*m). Difference of two maps. Return elements of the first map not existing in the second map.
differenceWith :: Eq k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a Source #
O(n*m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y
differenceWithKey :: Eq k => (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a Source #
O(n*m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the key and both values. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y.
Intersection
intersection :: Eq k => Map k a -> Map k b -> Map k a Source #
O(n*m). Intersection of two maps. Return data in the first map for the keys existing in both maps.
intersectionWith :: Eq k => (a -> b -> c) -> Map k a -> Map k b -> Map k c Source #
O(n*m). Intersection with a combining function.
intersectionWithKey :: Eq k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c Source #
O(n*m). Intersection with a combining function.
Disjoint
disjoint :: Eq k => Map k a -> Map k b -> Bool Source #
Check whether the key sets of two maps are disjoint.
(|.|) :: Eq b => Map b c -> Map a b -> Map a c Source #
Compose two functions. If the two functions are not composable, strips the functions until they can compose.
compose :: Eq b => Map b c -> Map a b -> Map a c Source #
Relate the keys of one map to the values of the other, by using the values of the former as keys for lookups in the latter.
mergeWithKey :: Eq k => (k -> a -> b -> Maybe c) -> (Map k a -> Map k c) -> (Map k b -> Map k c) -> Map k a -> Map k b -> Map k c Source #
A universal combining function.
Traversal
Map
mapWithKey :: (k -> a -> b) -> Map k a -> Map k b Source #
O(n). Map a function over all values in the map.
traverseWithKey :: (Applicative t, Eq k, Eq a) => (k -> a -> t b) -> Map k a -> t (Map k b) Source #
Eq typeclass must be added.
It behaves much like a regular traverse except that the traversing function also has access to the key associated with a value and the values are forced before they are installed in the result map.
traverseMaybeWithKey :: (Applicative f, Eq k, Eq a) => (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b) Source #
Eq typeclass must be added. Traverse keys/values and collect the Just results.
mapAccum :: Eq k => (a -> b -> (a, c)) -> a -> Map k b -> (a, Map k c) Source #
O(n). The function mapAccum
threads an accumulating argument through the map.
mapAccumWithKey :: Eq k => (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c) Source #
O(n^2). The function mapAccumWithKey
threads an accumulating argument through the map.
mapAccumRWithKey :: Eq k => (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c) Source #
O(n). Alias of mapAccumWithKey
for backward compatibility purposes. We don't implement it because order of pairs should not matter.
mapKeys :: (k1 -> k2) -> Map k1 a -> Map k2 a Source #
O(n). mapKeys f s
is the map obtained by applying f to each key of s.
mapKeysWith :: (Eq k1, Eq k2) => (a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a Source #
O(n^2). mapKeysWith c f s
is the map obtained by applying f to each key of s.
The size of the result may be smaller if f maps two or more distinct keys to the same new key. In this case the associated values will be combined using c.
mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a Source #
Alias of mapKeys
defined for backward compatibility.
Folds
foldr :: Eq k => (a -> b -> b) -> b -> Map k a -> b Source #
O(n^2). Fold the values in the map using the given right-associative binary operator.
Note that an Eq constraint must be added.
foldl :: Eq k => (a -> b -> a) -> a -> Map k b -> a Source #
O(n^2). Fold the values in the map using the given left-associative binary operator.
Note that an Eq constraint must be added.
foldrWithKey :: (Eq a, Eq k) => (k -> a -> b -> b) -> b -> Map k a -> b Source #
Fold with key.
foldlWithKey :: (Eq k, Eq a) => (b -> k -> a -> b) -> b -> Map k a -> b Source #
foldrWithKey
from the left.
foldMapWithKey :: (Eq a, Eq k, Monoid m) => (k -> a -> m) -> Map k a -> m Source #
Fold the keys and values in the map using the given monoid.
Strict folds
foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b Source #
Strict foldrWithKey
.
foldlWithKey' :: (b -> k -> a -> b) -> b -> Map k a -> b Source #
Strict foldrWithKey
.
Conversion
mapToList :: Eq k => Map k v -> AssociationList k v Source #
O(n^2). Transform a function back into its underlying association list.
mapToSet :: Eq k => Map k v -> Set (k, v) Source #
O(n^2). Transform a function back into its underlying set of pairs.
elems :: Eq k => Map k a -> [a] Source #
O(n^2). Return all values of the map. Beware that an Eq typeclass must be added.
keys :: Eq k => Map k v -> [k] Source #
O(n^2). Return the keys of a map. Beware that an Eq typeclass must be added.
assocs :: Eq k => Map k a -> [(k, a)] Source #
Alias of mapToList
for backward compatibility. Beware that an Eq typeclass must be added.
Lists
toList :: Eq k => Map k a -> [(k, a)] Source #
O(n^2). Alias of mapToList
for backward compatibility. Beware that an Eq typeclass must be added.
Ordered lists
toDescList :: Eq k => Map k a -> [(k, a)] Source #
Alias of toList
for backward compatibility.
Filter
filter :: (a -> Bool) -> Map k a -> Map k a Source #
O(n). Filter all values that satisfy the predicate.
filterWithKey :: (k -> a -> Bool) -> Map k a -> Map k a Source #
O(n). Filter all keys/values that satisfy the predicate.
partition :: (a -> Bool) -> Map k a -> (Map k a, Map k a) Source #
O(n). Partition the map according to a predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate.
partitionWithKey :: (k -> a -> Bool) -> Map k a -> (Map k a, Map k a) Source #
O(n). Partition the map according to a predicate. The first map contains all elements that satisfy the predicate, the second all elements that fail the predicate.
mapMaybe :: (a -> Maybe b) -> Map k a -> Map k b Source #
O(n). Map values and collect the Just results.
mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b Source #
O(n). Map keys/values and collect the Just results.
mapEither :: (a -> Either b c) -> Map k a -> (Map k b, Map k c) Source #
O(n). Map values and separate the Left and Right results.
mapEitherWithKey :: (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c) Source #
O(n). Map keys/values and separate the Left and Right results.
Submap
isSubmapOf :: (Eq k, Eq a) => Map k a -> Map k a -> Bool Source #
O(max(m^2,n^2)). This function is defined as (isSubmapOf = isSubmapOfBy (==))
.
isSubmapOfBy :: Eq k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool Source #
O(max(m^2,n^2)). Returns True if the keys of the first map is included in the keys of the second and the predicate evaluation at their value is True.
isProperSubmapOf :: (Eq k, Eq a) => Map k a -> Map k a -> Bool Source #
O(max(m^2,n^2)). This function is defined as (isProperSubmapOf = isProperSubmapOfBy (==))
.
isProperSubmapOfBy :: Eq k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool Source #
O(max(m^2,n^2)). Returns True if the keys of the first map is strictly included in the keys of the second and the predicate evaluation at their value is True.
Indexed
lookupIndex :: Eq k => k -> Map k a -> Maybe Int Source #
O(n^2). Lookup the index of a key, which is its zero-based index in the sequence. The index is a number from 0 up to, but not including, the size of the map.
findIndex :: Eq k => k -> Map k a -> Int Source #
O(n^2). Return the index of a key, which is its zero-based index in the sequence. The index is a number from 0 up to, but not including, the size of the map. Calls error when the key is not a member of the map.
elemAt :: Eq k => Int -> Map k a -> (k, a) Source #
O(n^2). Retrieve an element by its index, i.e. by its zero-based index in the sequence. If the index is out of range (less than zero, greater or equal to size of the map), error is called.
updateAt :: Eq k => (k -> a -> Maybe a) -> Int -> Map k a -> Map k a Source #
O(n^2). Update the element at index. Calls error when an invalid index is used.
deleteAt :: Eq k => Int -> Map k a -> Map k a Source #
O(n^2). Delete the element at index, i.e. by its zero-based index in the sequence. If the index is out of range (less than zero, greater or equal to size of the map), error is called.
take :: Eq k => Int -> Map k a -> Map k a Source #
O(n^2). Take a given number of pairs to create a new map.
drop :: Eq k => Int -> Map k a -> Map k a Source #
O(n^2). Drop a given number of pairs to create a new map.
splitAt :: Eq k => Int -> Map k a -> (Map k a, Map k a) Source #
O(n^2). Split a map at a particular index.
Others
memorizeFunction :: (k -> v) -> Set k -> Map k v Source #
O(n). Memorize a Haskell function on a given finite domain. Alias of fromSet
.
inverse :: (Eq k, Eq v) => Map k v -> Maybe (Map v k) Source #
O(n^2). Try to construct an inverse map.