Data.WeakMap

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.

Map type

type AssociationList k v = [(k, v)]

An association list is a list of pairs (key,value).

data Map k v

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.

Instances

Functor (Map k)

Defined in Data.WeakMap

Methods

fmap :: (a -> b) -> Map k a -> Map k b

(<$) :: a -> Map k b -> Map k a

(Eq k, Eq v) => Eq (Map k v)

Defined in Data.WeakMap

Methods

(==) :: Map k v -> Map k v -> Bool

(/=) :: Map k v -> Map k v -> Bool

(Show k, Show v) => Show (Map k v)

Defined in Data.WeakMap

Methods

showsPrec :: Int -> Map k v -> ShowS

show :: Map k v -> String

showList :: [Map k v] -> ShowS

Semigroup (Map k v)

Defined in Data.WeakMap

Methods

(<>) :: Map k v -> Map k v -> Map k v

sconcat :: NonEmpty (Map k v) -> Map k v

stimes :: Integral b => b -> Map k v -> Map k v

Monoid (Map k v)

Defined in Data.WeakMap

Methods

mempty :: Map k v

mappend :: Map k v -> Map k v -> Map k v

mconcat :: [Map k v] -> Map k v

Construction

weakMap :: AssociationList k v -> Map k v

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

O(1). Construct a Map from a Set of pairs (key,value).

empty :: Map k a

Alias of mempty for backward compatibility with Data.Map.

singleton :: k -> a -> Map k a

O(1). A map with a single pair (key,value).

fromSet :: (k -> a) -> Set k -> Map k a

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

O(1). Alias of weakMap for backward compatibility with Data.Map.

fromListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a

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

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

Alias for backward compatibility.

fromAscListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a

Alias for backward compatibility.

fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a

Alias for backward compatibility.

fromDistinctAscList :: [(k, a)] -> Map k a

Alias for backward compatibility.

From Descending Lists

fromDescList :: Eq k => [(k, a)] -> Map k a

Alias for backward compatibility.

fromDescListWith :: Eq k => (a -> a -> a) -> [(k, a)] -> Map k a

Alias for backward compatibility.

fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> [(k, a)] -> Map k a

Alias for backward compatibility.

fromDistinctDescList :: [(k, a)] -> Map k a

Alias for backward compatibility.

Insertion

insert :: k -> a -> Map k a -> Map k a

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

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

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)

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

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

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

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

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

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

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)

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.

alter :: Eq k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a

O(n). The expression (alter f k map) alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in a Map. In short : lookup k (alter f k m) = f (lookup k m).

alterF :: (Functor f, Eq k) => (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)

O(n). The expression (alterF f k map) alters the value x at k, or absence thereof. alterF can be used to inspect, insert, delete, or update a value in a Map.

Query

Lookup

lookup :: Eq k => k -> Map k a -> Maybe a

O(n). Just like (|?|) but the order of argument is reversed. For backward compatibility with Data.Map.

(!?) :: Eq k => Map k a -> k -> Maybe a

Alias for backward compatibility.

(!) :: Eq k => Map k a -> k -> a

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

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).

(|!|) :: Eq k => Map k v -> k -> v

O(n). Unsafe version of (|?|).

This function is like (!) in Data.Map, it is renamed to avoid name collisions.

findWithDefault :: Eq k => a -> k -> Map k a -> a

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

O(n). Is the key a member of the map? See also notMember.

notMember :: Eq k => k -> Map k a -> Bool

O(n). Negation of member.

Size

size :: Eq k => Map k a -> Int

O(n^2). The number of elements in the map.

null :: Map k a -> Bool

O(1). Return wether the map is empty.

Combine

Union

union :: Eq k => Map k a -> Map k a -> Map k a

O(n). The expression (union t1 t2) takes the left-biased union of t1 and t2. It prefers t1 when duplicate keys are encountered.

unionWith :: Eq k => (a -> a -> a) -> Map k a -> Map k a -> Map k a

O(n). Union with a combining function.

unionWithKey :: Eq k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a

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

The union of a list of maps: (unions == foldl union empty).

unionsWith :: Eq k => (a -> a -> a) -> [Map k a] -> Map k a

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

O(n*m). Difference of two maps. Return elements of the first map not existing in the second map.

(\\) :: Eq k => Map k a -> Map k b -> Map k a

See difference.

differenceWith :: Eq k => (a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a

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

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

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

O(n*m). Intersection with a combining function.

intersectionWithKey :: Eq k => (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c

O(n*m). Intersection with a combining function.

Disjoint

disjoint :: Eq k => Map k a -> Map k b -> Bool

Check whether the key sets of two maps are disjoint.

(|.|) :: Eq b => Map b c -> Map a b -> Map a c

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

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

A universal combining function.

Traversal

Map

map :: (a -> b) -> Map k a -> Map k b

O(n). Map a function over all values in the map.

mapWithKey :: (k -> a -> b) -> Map k a -> Map k b

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)

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)

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)

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)

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)

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

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

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

Alias of mapKeys defined for backward compatibility.

Folds

foldr :: Eq k => (a -> b -> b) -> b -> Map k a -> b

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

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

Fold with key.

foldlWithKey :: (Eq k, Eq a) => (b -> k -> a -> b) -> b -> Map k a -> b

foldrWithKey from the left.

foldMapWithKey :: (Eq a, Eq k, Monoid m) => (k -> a -> m) -> Map k a -> m

Fold the keys and values in the map using the given monoid.

Strict folds

foldr' :: Eq k => (a -> b -> b) -> b -> Map k a -> b

Strict foldr.

foldl' :: Eq k => (b -> a -> b) -> b -> Map k a -> b

Strict foldl.

foldrWithKey' :: (k -> a -> b -> b) -> b -> Map k a -> b

Strict foldrWithKey.

foldlWithKey' :: (b -> k -> a -> b) -> b -> Map k a -> b

Strict foldrWithKey.

Conversion

mapToList :: Eq k => Map k v -> AssociationList k v

O(n^2). Transform a function back into its underlying association list.

mapToSet :: Eq k => Map k v -> Set (k, v)

O(n^2). Transform a function back into its underlying set of pairs.

elems :: Eq k => Map k a -> [a]

O(n^2). Return all values of the map. Beware that an Eq typeclass must be added.

elems' :: Eq k => Map k a -> Set a

O(n^2). Same as elems but returns a Set. Beware that an Eq typeclass must be added.

values :: Eq k => Map k a -> Set a

O(n^2). Alias of elems`.

image :: Eq k => Map k a -> Set a

O(n^2). Alias of elems`.

keys :: Eq k => Map k v -> [k]

O(n^2). Return the keys of a map. Beware that an Eq typeclass must be added.

keys' :: Map k v -> Set k

O(n). Same as keys but returns a Set. No Eq typeclass required.

domain :: Map k a -> Set k

O(n^2). Alias of keys`.

assocs :: Eq k => Map k a -> [(k, a)]

Alias of mapToList for backward compatibility. Beware that an Eq typeclass must be added.

keysSet :: Map k a -> Set k

Alias of keys` for backward compatibility.

elemsSet :: Eq k => Map k a -> Set a

O(n^2). Return the set of values of a map.

Lists

toList :: Eq k => Map k a -> [(k, a)]

O(n^2). Alias of mapToList for backward compatibility. Beware that an Eq typeclass must be added.

Ordered lists

toAscList :: Eq k => Map k a -> [(k, a)]

Alias of toList for backward compatibility.

toDescList :: Eq k => Map k a -> [(k, a)]

Alias of toList for backward compatibility.

Filter

filter :: (a -> Bool) -> Map k a -> Map k a

O(n). Filter all values that satisfy the predicate.

filterWithKey :: (k -> a -> Bool) -> Map k a -> Map k a

O(n). Filter all keys/values that satisfy the predicate.

restrictKeys :: Eq k => Map k a -> Set k -> Map k a

O(n*m). Restrict a Map to only those keys found in a Set.

withoutKeys :: Eq k => Map k a -> Set k -> Map k a

O(n*m). Remove all keys in a Set from a Map.

partition :: (a -> Bool) -> Map k a -> (Map k a, Map k a)

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)

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

O(n). Map values and collect the Just results.

mapMaybeWithKey :: (k -> a -> Maybe b) -> Map k a -> Map k b

O(n). Map keys/values and collect the Just results.

mapEither :: (a -> Either b c) -> Map k a -> (Map k b, Map k c)

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)

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

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

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

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

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

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

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)

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

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

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

O(n^2). Take a given number of pairs to create a new map.

drop :: Eq k => Int -> Map k a -> Map k a

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)

O(n^2). Split a map at a particular index.

Others

idFromSet :: Set a -> Map a a

O(n). Return the identity function associated to a Set.

memorizeFunction :: (k -> v) -> Set k -> Map k v

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)

O(n^2). Try to construct an inverse map.

pseudoInverse :: Map k v -> Map v k

O(n). Return a pseudo inverse g of a Map f such that f |.| g |.| f == f.

enumerateMaps

Arguments

:: (Eq a, Eq b)

=> Set a

Domain.

-> Set b

Codomain.

-> Set (Map a b)

All maps from domain to codomain.

Return all Functions from a domain to a codomain.