| Copyright | Copyright (c) 1998 Chris Okasaki |
|---|---|
| License | MIT; see COPYRIGHT file for terms and conditions |
| Maintainer | robdockins AT fastmail DOT fm |
| Stability | stable |
| Portability | GHC, Hugs (MPTC and FD) |
| Safe Haskell | Safe |
| Language | Haskell2010 |
Data.Edison.Assoc
Contents
Description
The associative collection abstraction includes finite maps, finite relations, and priority queues where the priority is separate from the element. Associative collections are defined in Edison as a set of eight classes.
Note that this
hierarchy mirrors the hierarchy for collections, but with the addition
of Functor as a superclass of every associative collection. See
Data.Edison.Coll for a description of the class hierarchy.
In almost all cases, associative collections make no guarantees about behavior with respect to the actual keys stored and (in the case of observable maps) which keys can be retrieved. We adopt the convention that methods which create associative collections are unambiguous with respect to the key storage behavior, but that methods which can observe keys are ambiguous with respect to the actual keys returned.
In all cases where an operation is ambiguous with respect to the key,
the operation is rendered unambiguous if the Eq instance on keys
corresponds to indistinguisability.
- map :: AssocX m k => (a -> b) -> m a -> m b
- class (Eq k, Functor m) => AssocX m k | m -> k where
- class (AssocX m k, Ord k) => OrdAssocX m k | m -> k where
- class AssocX m k => FiniteMapX m k | m -> k where
- class (OrdAssocX m k, FiniteMapX m k) => OrdFiniteMapX m k | m -> k
- class AssocX m k => Assoc m k | m -> k where
- class (Assoc m k, OrdAssocX m k) => OrdAssoc m k | m -> k where
- class (Assoc m k, FiniteMapX m k) => FiniteMap m k | m -> k where
- class (OrdAssoc m k, FiniteMap m k) => OrdFiniteMap m k | m -> k
- submap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool
- properSubmap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool
- sameMap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool
- fromList :: AssocX m k => [(k, a)] -> m a
- insertList :: AssocX m k => [(k, a)] -> m a -> m a
- unionList :: AssocX m k => [m a] -> m a
- deleteList :: AssocX m k => [k] -> m a -> m a
- lookupList :: AssocX m k => k -> m a -> [a]
- elementsList :: AssocX m k => m a -> [a]
- unsafeFromOrdList :: OrdAssocX m k => [(k, a)] -> m a
- fromListWith :: FiniteMapX m k => (a -> a -> a) -> [(k, a)] -> m a
- fromListWithKey :: FiniteMapX m k => (k -> a -> a -> a) -> [(k, a)] -> m a
- insertListWith :: FiniteMapX m k => (a -> a -> a) -> [(k, a)] -> m a -> m a
- insertListWithKey :: FiniteMapX m k => (k -> a -> a -> a) -> [(k, a)] -> m a -> m a
- unionListWith :: FiniteMapX m k => (a -> a -> a) -> [m a] -> m a
- toList :: Assoc m k => m a -> [(k, a)]
- keysList :: Assoc m k => m a -> [k]
- toOrdList :: OrdAssoc m k => m a -> [(k, a)]
- unionListWithKey :: FiniteMap m k => (k -> a -> a -> a) -> [m a] -> m a
Superclass aliases
map :: AssocX m k => (a -> b) -> m a -> m b Source #
Apply a function to the elements of every binding in the associative
collection. Identical to fmap from Functor.
This function is always unambiguous.
Non-observable associative collections
class (Eq k, Functor m) => AssocX m k | m -> k where Source #
The root class of the associative collection hierarchy.
Minimal complete definition
empty, singleton, fromSeq, insert, insertSeq, union, unionSeq, delete, deleteAll, deleteSeq, null, size, member, count, lookup, lookupM, lookupAll, lookupAndDelete, lookupAndDeleteM, lookupAndDeleteAll, lookupWithDefault, adjust, adjustAll, adjustOrInsert, adjustAllOrInsert, adjustOrDelete, adjustOrDeleteAll, fold, fold', fold1, fold1', filter, partition, elements, strict, strictWith, structuralInvariant, instanceName
Methods
The empty associative collection.
This function is always unambiguous.
singleton :: k -> a -> m a Source #
Create an associative collection with a single binding.
This function is always unambiguous.
fromSeq :: Sequence seq => seq (k, a) -> m a Source #
Create an associative collection from a list of bindings. Which element and key are kept in the case of duplicate keys is unspecified.
This function is ambiguous at finite map types if the sequence contains more than one equivalent key. Otherwise it is unambiguous.
insert :: k -> a -> m a -> m a Source #
Add a binding to an associative collection. For finite maps, insert
keeps the new element in the case of duplicate keys.
This function is unambiguous.
insertSeq :: Sequence seq => seq (k, a) -> m a -> m a Source #
Add a sequence of bindings to a collection. For finite maps, which key and which element are kept in the case of duplicates is unspecified. However, if a key appears in the sequence and in the map, (one of) the elements in the list will be given preference.
This function is ambiguous at finite map types if the sequence contains more than one equivalent key. Otherwise it is unambiguous.
union :: m a -> m a -> m a Source #
Merge two associative collections. For finite maps, which element to keep in the case of duplicate keys is unspecified.
This function is ambiguous at finite map types if the map keys are not disjoint. Otherwise it is unambiguous.
unionSeq :: Sequence seq => seq (m a) -> m a Source #
Merge a sequence of associative collections. Which element to keep in the case of duplicate keys is unspecified.
This function is ambiguous at finite map types if the map keys are not mutually disjoint. Otherwise it is unambiguous.
delete :: k -> m a -> m a Source #
Delete one binding with the given key, or leave the associative collection unchanged if it does not contain the key. For bag-like associative collections, it is unspecified which binding will be removed.
This function is ambiguous at finite relation types if the key appears more than once in the relation. Otherwise it is unambiguous.
deleteAll :: k -> m a -> m a Source #
Delete all bindings with the given key, or leave the associative collection unchanged if it does not contain the key.
This function is always unambiguous.
deleteSeq :: Sequence seq => seq k -> m a -> m a Source #
Delete a single occurrence of each of the given keys from an associative collection. For bag-like associative collections containing duplicate keys, it is unspecified which bindings will be removed.
This function is ambiguous at finite relation types if any key appears both in the sequence and in the finite relation AND the number of occurrences in the sequence is less than the number of occurrences in the finite relation. Otherwise it is unambiguous.
Test whether the associative collection is empty.
Axioms:
null m = (size m == 0)
This function is always unambiguous.
Return the number of bindings in the associative collection.
This function is always unambiguous.
member :: k -> m a -> Bool Source #
Test whether the given key is bound in the associative collection.
This function is always unambiguous.
count :: k -> m a -> Int Source #
Returns the number of bindings with the given key. For finite maps this will always return 0 or 1.
This function is always unambiguous.
lookup :: k -> m a -> a Source #
Find the element associated with the given key. Signals an error if the given key is not bound. If more than one element is bound by the given key, it is unspecified which is returned.
This function is ambiguous at finite relation types if the key appears more than once in the finite relation. Otherwise, it is unambiguous.
lookupM :: Monad rm => k -> m a -> rm a Source #
Find the element associated with the given key. Calls fail if the
given key is not bound. If more than one element is bound by the given
key, it is unspecified which is returned.
This function is ambiguous at finite relation types if the key appears more than once in the finite relation. Otherwise, it is unambiguous.
lookupAll :: Sequence seq => k -> m a -> seq a Source #
Return all elements bound by the given key in an unspecified order.
This function is ambiguous at finite relation types if the key appears more than once in the finite relation. Otherwise, it is unambiguous.
lookupAndDelete :: k -> m a -> (a, m a) Source #
Find the element associated with the given key; return the element and the collection with that element deleted. Signals an error if the given key is not bound. If more than one element is bound by the given key, it is unspecified which is deleted and returned.
This function is ambiguous at finite relation types if the key appears more than once in the finite relation. Otherwise, it is unambiguous.
lookupAndDeleteM :: Monad rm => k -> m a -> rm (a, m a) Source #
Find the element associated with the given key; return the element
and the collection with that element deleted. Calls fail if
the given key is not bound. If more than one element is bound by the
given key, it is unspecified which is deleted and returned.
This function is ambiguous at finite relation types if the key appears more than once in the finite relation. Otherwise, it is unambiguous.
lookupAndDeleteAll :: Sequence seq => k -> m a -> (seq a, m a) Source #
Find all elements bound by the given key; return a sequence containing all such bound elements in an unspecified order and the collection with all such elements deleted.
This function is ambiguous at finite relation types if the key appears more than once in the finite relation. Otherwise, it is unambiguous.
lookupWithDefault :: a -> k -> m a -> a Source #
Return the element associated with the given key. If no such element is found, return the default.
This function is ambiguous at finite relation types if the key appears more than once in the finite relation. Otherwise, it is unambiguous.
adjust :: (a -> a) -> k -> m a -> m a Source #
Change a single binding for the given key by applying a function to its element. If the key binds more than one element, it is unspecified which will be modified. If the key is not found in the collection, it is returned unchanged.
This function is ambiguous at finite relation types if the key appears more than once in the finite relation. Otherwise, it is unambiguous.
adjustAll :: (a -> a) -> k -> m a -> m a Source #
Change all bindings for the given key by applying a function to its elements. If the key is not found in the collection, it is returned unchanged.
This function is always unambiguous.
adjustOrInsert :: (a -> a) -> a -> k -> m a -> m a Source #
Searches for a matching key in the collection. If the key is found, the given function is called to adjust the value. If the key is not found, a new binding is inserted with the given element. If the given key is bound more than once in the collection, it is unspecified which element is adjusted.
This function is ambiguous at finite relation types if the key appears more than once in the finite relation. Otherwise, it is unambiguous.
adjustAllOrInsert :: (a -> a) -> a -> k -> m a -> m a Source #
Searches for all matching keys in the collection. If the key is found, the given function is applied to all its elements to adjust their values. If the key is not found, a new binding is inserted with the given element.
This function is always unambiguous.
adjustOrDelete :: (a -> Maybe a) -> k -> m a -> m a Source #
Change or delete a single binding for the given key by applying a function
to its element. If the function returns Nothing, then the binding
will be deleted. If the key binds more than one element, it is unspecified which
will be modified. If the key is not found in the collection, it is returned
unchanged.
This function is ambiguous at finite relation types if the key appears more than once in the finite relation. Otherwise, it is unambiguous.
adjustOrDeleteAll :: (a -> Maybe a) -> k -> m a -> m a Source #
Change or delete all bindings for the given key by applying a function to
its elements. For any element where the function returns Nothing, the
corresponding binding is deleted. If the key is not found in the collection,
it is returned unchanged.
This function is always unambiguous.
fold :: (a -> b -> b) -> b -> m a -> b Source #
Combine all the elements in the associative collection, given a combining
function and an initial value. The elements are processed in an
unspecified order. Note that fold ignores the keys.
fold f is unambiguous iff f is fold-commutative.
fold' :: (a -> b -> b) -> b -> m a -> b Source #
A strict variant of fold.
fold' f is unambiguous iff f is fold-commutative.
fold1 :: (a -> a -> a) -> m a -> a Source #
Combine all the elements in a non-empty associative collection using the
given combining function. Signals an error if the associative collection
is empty. The elements are processed in an unspecified order. An
implementation may choose to process the elements linearly or in a
balanced fashion (like reduce1 on sequences). Note that fold1
ignores the keys.
fold1 f is unambiguous iff f is fold-commutative.
fold1' :: (a -> a -> a) -> m a -> a Source #
A strict variant of fold1.
fold1' f is unambiguous iff f is fold-commutative.
filter :: (a -> Bool) -> m a -> m a Source #
Extract all bindings whose elements satisfy the given predicate.
This function is always unambiguous.
partition :: (a -> Bool) -> m a -> (m a, m a) Source #
Split an associative collection into those bindings which satisfy the given predicate, and those which do not.
This function is always unambiguous.
elements :: Sequence seq => m a -> seq a Source #
Returns all the elements in an associative collection, in an unspecified order.
This function is ambiguous iff the associative collection contains more than one element.
Semanticly, this function is a partial identity function. If the
datastructure is infinite in size or contains exceptions or non-termination
in the structure itself, then strict will result in bottom. Operationally,
this function walks the datastructure forcing any closures. Elements contained
in the map are not forced.
This function is always unambiguous.
strictWith :: (a -> b) -> m a -> m a Source #
Similar to strict, this function walks the datastructure forcing closures.
However, strictWith will additionally apply the given function to the
map elements, force the result using seq, and then ignore it.
This function can be used to perform various levels of forcing on the
sequence elements. In particular:
strictWith id xs
will force the spine of the datastructure and reduce each element to WHNF.
This function is always unambiguous.
structuralInvariant :: m a -> Bool Source #
A method to facilitate unit testing. Returns True if the structural
invariants of the implementation hold for the given associative
collection. If this function returns False, it represents a bug;
generally, either the implementation itself is flawed, or an unsafe
operation has been used while violating the preconditions.
instanceName :: m a -> String Source #
Returns the name of the module implementing this associative collection.
class (AssocX m k, Ord k) => OrdAssocX m k | m -> k where Source #
An associative collection where the keys additionally have an ordering relation.
Minimal complete definition
minView, minElem, deleteMin, unsafeInsertMin, maxView, maxElem, deleteMax, unsafeInsertMax, foldr, foldr', foldl, foldl', foldr1, foldr1', foldl1, foldl1', unsafeFromOrdSeq, unsafeAppend, filterLT, filterLE, filterGT, filterGE, partitionLT_GE, partitionLE_GT, partitionLT_GT
Methods
minView :: Monad rm => m a -> rm (a, m a) Source #
Remove the binding with the minimum key, and return its element together
with the remaining associative collection. Calls fail if the
associative collection is empty. Which binding is removed if there
is more than one minimum is unspecified.
This function is ambiguous at finite relation types if the finite relation contains more than one minimum key. Otherwise it is unambiguous.
Find the binding with the minimum key and return its element. Signals an error if the associative collection is empty. Which element is chosen if there is more than one minimum is unspecified.
This function is ambiguous at finite relation types if the finite relation contains more than one minimum key. Otherwise it is unambiguous.
deleteMin :: m a -> m a Source #
Remove the binding with the minimum key and return the remaining associative collection, or return empty if it is already empty.
This function is ambiguous at finite relation types if the finite relation contains more than one minimum key. Otherwise it is unambiguous.
unsafeInsertMin :: k -> a -> m a -> m a Source #
Insert a binding into an associative collection with the precondition
that the given key is <= any existing keys already in the collection.
For finite maps, this precondition is strengthened to <.
This function is unambiguous under the preconditions.
maxView :: Monad rm => m a -> rm (a, m a) Source #
Remove the binding with the maximum key, and return its element together
with the remaining associative collection. Calls fail if the
associative collection is empty. Which binding is removed if there
is more than one maximum is unspecified.
This function is ambiguous at finite relation types if the finite relation contains more than one minimum key. Otherwise it is unambiguous.
Find the binding with the maximum key and return its element. Signals an error if the associative collection is empty. Which element is chosen if there is more than one maximum is unspecified.
This function is ambiguous at finite relation types if the finite relation contains more than one minimum key. Otherwise it is unambiguous.
deleteMax :: m a -> m a Source #
Remove the binding with the maximum key and return the remaining associative collection, or return empty if it is already empty.
This function is ambiguous at finite relation types if the finite relation contains more than one minimum key. Otherwise it is unambiguous.
unsafeInsertMax :: k -> a -> m a -> m a Source #
Insert a binding into an associative collection with the precondition
that the given key is >= any existing keys already in the collection.
For finite maps, this precondition is strengthened to >.
This function is unambiguous under the precondition.
foldr :: (a -> b -> b) -> b -> m a -> b Source #
Fold across the elements of an associative collection in non-decreasing order by key with right associativity. For finite maps, the order is increasing.
foldr f is unambiguous if f is fold-commutative, at finite
map types, or at finite relation types if the relation contains no
duplicate keys. Otherwise it is ambiguous.
foldr' :: (a -> b -> b) -> b -> m a -> b Source #
A strict variant of foldr.
foldr' f is unambiguous if f is fold-commutative, at finite
map types, or at finite relation types if the relation contains no
duplicate keys. Otherwise it is ambiguous.
foldl :: (b -> a -> b) -> b -> m a -> b Source #
Fold across the elements of an associative collection in non-decreasing order by key with left associativity. For finite maps, the order is increasing.
foldl f is unambiguous if f is fold-commutative, at finite
map types, or at finite relation types if the relation contains no
duplicate keys. Otherwise it is ambiguous.
foldl' :: (b -> a -> b) -> b -> m a -> b Source #
A strict variant of foldl.
foldl' f is unambiguous if f is fold-commutative, at finite
map types, or at finite relation types if the relation contains no
duplicate keys. Otherwise it is ambiguous.
foldr1 :: (a -> a -> a) -> m a -> a Source #
Fold across the elements of an associative collection in non-decreasing order by key with right associativity. Signals an error if the associative collection is empty. For finite maps, the order is increasing.
foldr1 f is unambiguous if f is fold-commutative, at finite
map types, or at finite relation types if the relation contains no
duplicate keys. Otherwise it is ambiguous.
foldr1' :: (a -> a -> a) -> m a -> a Source #
A strict variant of foldr1.
foldr1' f is unambiguous if f is fold-commutative, at finite
map types, or at finite relation types if the relation contains no
duplicate keys. Otherwise it is ambiguous.
foldl1 :: (a -> a -> a) -> m a -> a Source #
Fold across the elements of an associative collection in non-decreasing order by key with left associativity. Signals an error if the associative collection is empty. For finite maps, the order is increasing.
foldl1 f is unambiguous if f is fold-commutative, at finite
map types, or at finite relation types if the relation contains no
duplicate keys. Otherwise it is ambiguous.
foldl1' :: (a -> a -> a) -> m a -> a Source #
A strict variant of foldl1.
foldl1' f is unambiguous if f is fold-commutative, at finite
map types, or at finite relation types if the relation contains no
duplicate keys. Otherwise it is ambiguous.
unsafeFromOrdSeq :: Sequence seq => seq (k, a) -> m a Source #
Convert a sequence of bindings into an associative collection with the precondition that the sequence is sorted into non-decreasing order by key. For finite maps, this precondition is strengthened to increasing order.
This function is unambiguous under the precondition.
unsafeAppend :: m a -> m a -> m a Source #
Merge two associative collections with the precondition that every key
in the first associative collection is <= every key in the second
associative collection. For finite maps, this precondition is
strengthened to <.
This function is unambiguous under the precondition.
filterLT :: k -> m a -> m a Source #
Extract all bindings whose keys are < the given key.
This function is always unambiguous.
filterLE :: k -> m a -> m a Source #
Extract all bindings whose keys are <= the given key.
This function is always unambiguous.
filterGT :: k -> m a -> m a Source #
Extract all bindings whose keys are > the given key.
This function is always unambiguous.
filterGE :: k -> m a -> m a Source #
Extract all bindings whose keys are >= the given key.
This function is always unambiguous.
partitionLT_GE :: k -> m a -> (m a, m a) Source #
Split an associative collection into two sub-collections, containing
those bindings whose keys are < the given key and those which are >=.
This function is always unambiguous.
partitionLE_GT :: k -> m a -> (m a, m a) Source #
Split an associative collection into two sub-collections, containing
those bindings whose keys are <= the given key and those which are >.
This function is always unambiguous.
partitionLT_GT :: k -> m a -> (m a, m a) Source #
Split an associative collection into two sub-collections, containing
those bindings whose keys are < the given key and those which are >.
All bindings with keys equal to the given key are discarded.
This function is always unambiguous.
class AssocX m k => FiniteMapX m k | m -> k where Source #
An associative collection where the keys form a set; that is, each key appears in the associative collection at most once.
Minimal complete definition
fromSeqWith, fromSeqWithKey, insertWith, insertWithKey, insertSeqWith, insertSeqWithKey, unionl, unionr, unionWith, unionSeqWith, intersectionWith, difference, properSubset, subset, submapBy, properSubmapBy, sameMapBy
Methods
fromSeqWith :: Sequence seq => (a -> a -> a) -> seq (k, a) -> m a Source #
Same as fromSeq, but with a combining function to resolve duplicates.
This function is always unambiguous.
fromSeqWithKey :: Sequence seq => (k -> a -> a -> a) -> seq (k, a) -> m a Source #
Same as fromSeq, but with a combining function to resolve duplicates;
the combining function takes the key in addition to the two elements.
This function is always unambiguous.
insertWith :: (a -> a -> a) -> k -> a -> m a -> m a Source #
Same as insert, but with a combining function to resolve duplicates.
This function is unambiguous.
insertWithKey :: (k -> a -> a -> a) -> k -> a -> m a -> m a Source #
Same as insert, but with a combining function to resolve duplicates;
the combining function takes the key in addition to the two elements.
The key passed to the combining function is always the same as the
given key.
This function is unambiguous.
insertSeqWith :: Sequence seq => (a -> a -> a) -> seq (k, a) -> m a -> m a Source #
Same as insertSeq, but with a combining function to resolve duplicates.
This function is unambiguous.
insertSeqWithKey :: Sequence seq => (k -> a -> a -> a) -> seq (k, a) -> m a -> m a Source #
Same as insertSeq, but with a combining function to resolve duplicates;
the combining function takes the key in addition to the two elements.
This function is unambiguous.
unionl :: m a -> m a -> m a Source #
Left biased union.
Axioms:
unionl = unionwith (\x y -> x)
This function is unambiguous.
unionr :: m a -> m a -> m a Source #
Right biased union.
Axioms:
unionr = unionWith (\x y -> y)
This function is unambiguous.
unionWith :: (a -> a -> a) -> m a -> m a -> m a Source #
Same as union, but with a combining function to resolve duplicates.
This function is unambiguous.
unionSeqWith :: Sequence seq => (a -> a -> a) -> seq (m a) -> m a Source #
Same as unionSeq, but with a combining function to resolve duplicates.
This function is unambiguous.
intersectionWith :: (a -> b -> c) -> m a -> m b -> m c Source #
Compute the intersection of two finite maps. The resulting finite map will contain bindings where the keys are the set intersection of the keys in the argument finite maps. The combining function computes the value of the element given the bound elements from the argument finite maps.
This function is unambiguous.
difference :: m a -> m b -> m a Source #
Computes the difference of two finite maps; that is, all bindings in the first finite map whose keys to not appear in the second.
This function is always unambiguous.
properSubset :: m a -> m b -> Bool Source #
Test whether the set of keys in the first finite map is a proper subset of the set of keys of the second; that is, every key present in the first finite map is also a member of the second finite map AND there exists some key in the second finite map which is not present in the first.
This function is always unambiguous.
subset :: m a -> m b -> Bool Source #
Test whether the set of keys in the first finite map is a subset of the set of keys of the second; that is, if every key present in the first finite map is also present in the second.
This function is always unambiguous.
submapBy :: (a -> a -> Bool) -> m a -> m a -> Bool Source #
Test whether the first map is a submap of the second map given a comparison function on elements; that is, if every key present in the first map is also present in the second map and the comparison function returns true when applied two the bound elements.
This function is always unambiguous.
properSubmapBy :: (a -> a -> Bool) -> m a -> m a -> Bool Source #
Test whether the first map is a proper submap of the second map given a comparison function on elements; that is, if every key present in the first map is also present in the second map and the comparison function returns true when applied two the bound elements AND there exiss some key in the second finite map which is not present in the first.
This function is always unambiguous.
sameMapBy :: (a -> a -> Bool) -> m a -> m a -> Bool Source #
Test whether the first map is the "same" map as the second map given a comparison function on elements; that is, if the first and second maps have the same set of keys and the comparison function returns true when applied to corresponding elements.
This function is always unambiguous.
class (OrdAssocX m k, FiniteMapX m k) => OrdFiniteMapX m k | m -> k Source #
Finite maps where the keys additionally have an ordering relation. This class introduces no new methods.
Observable associative collections
class AssocX m k => Assoc m k | m -> k where Source #
Associative collections where the keys are observable.
Minimal complete definition
toSeq, keys, mapWithKey, foldWithKey, foldWithKey', filterWithKey, partitionWithKey
Methods
toSeq :: Sequence seq => m a -> seq (k, a) Source #
Extract the bindings of an associative collection into a sequence. The bindings are emitted in an unspecified order.
This function is ambiguous with respect to the sequence order
iff the associative collection contains more than one binding.
Furthermore, it is ambiguous with respect to the actual key
returned, unless the Eq instance on keys corresponds to
indistinguisability.
keys :: Sequence seq => m a -> seq k Source #
Extract the keys of an associative collection into a sequence. The keys are emitted in an unspecified order. For finite relations, keys which appear multiple times in the relation will appear as many times in the extracted sequence.
This function is ambiguous with respect to the sequence order
iff the associative collection contains more than one binding.
Furthermore, it is ambiguous with respect to the actual key
returned, unless the Eq instance on keys corresponds to
indistinguisability.
mapWithKey :: (k -> a -> b) -> m a -> m b Source #
Apply a function to every element in an associative collection. The mapped function additionally takes the value of the key.
This function is ambiguous with respect to the actual keys
observed, unless the Eq instance on keys corresponds to
indistinguisability.
foldWithKey :: (k -> a -> b -> b) -> b -> m a -> b Source #
Combine all the elements in the associative collection, given a combining function and an initial value. The elements are processed in an unspecified order. The combining function additionally takes the value of the key.
foldWithKey f is unambiguous iff f is fold-commutative and
the Eq instance on keys corresponds to indistinguisability.
foldWithKey' :: (k -> a -> b -> b) -> b -> m a -> b Source #
A strict variant of foldWithKey.
foldWithKey' f is unambiguous iff f is fold-commutative and
the Eq instance on keys corresponds to indistinguisability.
filterWithKey :: (k -> a -> Bool) -> m a -> m a Source #
Extract all bindings from an associative collection which satisfy the given predicate.
This function is ambiguous with respect to the actual keys
observed, unless the Eq instance on keys corresponds to
indistinguisability.
partitionWithKey :: (k -> a -> Bool) -> m a -> (m a, m a) Source #
Split an associative collection into two sub-collections containing those bindings which satisfy the given predicate and those which do not.
This function is ambiguous with respect to the actual keys
observed, unless the Eq instance on keys corresponds to
indistinguisability.
class (Assoc m k, OrdAssocX m k) => OrdAssoc m k | m -> k where Source #
An associative collection with observable keys where the keys additionally have an ordering relation.
Minimal complete definition
minViewWithKey, minElemWithKey, maxViewWithKey, maxElemWithKey, foldrWithKey, foldrWithKey', foldlWithKey, foldlWithKey', toOrdSeq
Methods
minViewWithKey :: Monad rm => m a -> rm ((k, a), m a) Source #
Delete the binding with the minimum key from an associative
collection and return the key, the element and the remaining
associative collection. Calls fail if the associative collection
is empty. Which binding is chosen if there are multiple minimum keys
is unspecified.
This function is ambiguous at finite relation types if more than one
minimum key exists in the relation. Furthermore, it is ambiguous
with respect to the actual key observed unless the Eq instance on
keys corresponds to indistinguisability.
minElemWithKey :: m a -> (k, a) Source #
Find the binding with the minimum key in an associative collection and return the key and the element. Signals an error if the associative collection is empty. Which binding is chosen if there are multiple minimum keys is unspecified.
This function is ambiguous at finite relation types if more than one
minimum key exists in the relation. Furthermore, it is ambiguous
with respect to the actual key observed unless the Eq instance on
keys corresponds to indistinguisability.
maxViewWithKey :: Monad rm => m a -> rm ((k, a), m a) Source #
Delete the binding with the maximum key from an associative
collection and return the key, the element and the remaining
associative collection. Calls fail if the associative collection
is empty. Which binding is chosen if there are multiple maximum keys
is unspecified.
This function is ambiguous at finite relation types if more than one
maximum key exists in the relation. Furthermore, it is ambiguous
with respect to the actual key observed unless the Eq instance on
keys corresponds to indistinguisability.
maxElemWithKey :: m a -> (k, a) Source #
Find the binding with the maximum key in an associative collection and return the key and the element. Signals an error if the associative collection is empty. Which binding is chosen if there are multiple maximum keys is unspecified.
This function is ambiguous at finite relation types if more than one
maximum key exists in the relation. Furthermore, it is ambiguous
with respect to the actual key observed unless the Eq instance on
keys corresponds to indistinguisability.
foldrWithKey :: (k -> a -> b -> b) -> b -> m a -> b Source #
Fold over all bindings in an associative collection in non-decreasing order by key with right associativity, given a combining function and an initial value. For finite maps, the order is increasing.
foldrWithKey f is ambiguous at finite relation types if
the relation contains more than one equivalent key and
f is not fold-commutative OR if the Eq instance on keys
does not correspond to indistingusihability.
foldrWithKey' :: (k -> a -> b -> b) -> b -> m a -> b Source #
A strict variant of foldrWithKey.
foldrWithKey' f is ambiguous at finite relation types if
the relation contains more than one equivalent key and
f is not fold-commutative OR if the Eq instance on keys
does not correspond to indistingusihability. Otherwise it
is unambiguous.
foldlWithKey :: (b -> k -> a -> b) -> b -> m a -> b Source #
Fold over all bindings in an associative collection in non-decreasing order by key with left associativity, given a combining function and an initial value. For finite maps, the order is increasing.
foldlWithKey f is ambiguous at finite relation types if
the relation contains more than one equivalent key and
f is not fold-commutative OR if the Eq instance on keys
does not correspond to indistingusihability. Otherwise it
is unambiguous.
foldlWithKey' :: (b -> k -> a -> b) -> b -> m a -> b Source #
A strict variant of foldlWithKey.
foldlWithKey' f is ambiguous at finite relation types if
the relation contains more than one equivalent key and
f is not fold-commutative OR if the Eq instance on keys
does not correspond to indistinguishability. Otherwise it
is unambiguous.
toOrdSeq :: Sequence seq => m a -> seq (k, a) Source #
Extract the bindings of an associative collection into a sequence, where the bindings are in non-decreasing order by key. For finite maps, this is increasing order.
This function is ambiguous at finite relation types if the relation
contains more than one equivalent key, or if the Eq instance on
keys does not correspond to indistinguishability.
class (Assoc m k, FiniteMapX m k) => FiniteMap m k | m -> k where Source #
Finite maps with observable keys.
Minimal complete definition
Methods
unionWithKey :: (k -> a -> a -> a) -> m a -> m a -> m a Source #
Same as union, but with a combining function to resolve duplicates.
The combining function additionally takes the key. Which key is kept
and passed into the combining function is unspecified.
This function is unambiguous provided that the Eq instance on keys
corresponds to indistinguishability.
unionSeqWithKey :: Sequence seq => (k -> a -> a -> a) -> seq (m a) -> m a Source #
Same as unionSeq, but with a combining function to resolve duplicates.
The combining function additionally takes the key. Which key is
kept and passed into the combining function is unspecified.
This function is unambiguous provided that the Eq instance on keys
corresponds to indistinguishability.
intersectionWithKey :: (k -> a -> b -> c) -> m a -> m b -> m c Source #
Same as intersectionWith, except that the combining function
additionally takes the key value for each binding. Which key is
kept and passed into the combining function is unspecified.
This function is unambiguous provided the Eq instance on keys
corresponds to indistinguishability.
class (OrdAssoc m k, FiniteMap m k) => OrdFiniteMap m k | m -> k Source #
Finite maps with observable keys where the keys additionally have an ordering relation. This class introduces no new methods.
Specilizations of submap operations
submap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool Source #
Specialization of submapBy where the comparison function is
given by (==).
properSubmap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool Source #
Specialization of properSubmapBy where the comparison function
is given by (==).
sameMap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool Source #
Specialization of sameMapBy where the comparison function is
given by (==).
Specializations of sequence operations to lists
insertList :: AssocX m k => [(k, a)] -> m a -> m a Source #
deleteList :: AssocX m k => [k] -> m a -> m a Source #
lookupList :: AssocX m k => k -> m a -> [a] Source #
elementsList :: AssocX m k => m a -> [a] Source #
unsafeFromOrdList :: OrdAssocX m k => [(k, a)] -> m a Source #
fromListWith :: FiniteMapX m k => (a -> a -> a) -> [(k, a)] -> m a Source #
fromListWithKey :: FiniteMapX m k => (k -> a -> a -> a) -> [(k, a)] -> m a Source #
insertListWith :: FiniteMapX m k => (a -> a -> a) -> [(k, a)] -> m a -> m a Source #
insertListWithKey :: FiniteMapX m k => (k -> a -> a -> a) -> [(k, a)] -> m a -> m a Source #
unionListWith :: FiniteMapX m k => (a -> a -> a) -> [m a] -> m a Source #
unionListWithKey :: FiniteMap m k => (k -> a -> a -> a) -> [m a] -> m a Source #