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	Haskell98

Data.Edison.Assoc

Contents

Superclass aliases
Non-observable associative collections
Observable associative collections
Specilizations of submap operations
Specializations of sequence operations to lists

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.

Synopsis

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.

Methods

empty :: m a Source

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.

null :: m a -> Bool Source

Test whether the associative collection is empty.

Axioms:

```
null m = (size m == 0)
```

This function is always unambiguous.

size :: m a -> Int Source

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 Source

Arguments

:: a	default element
-> k	the key to look up
-> m a	the associative collection
-> a

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.

strict :: m a -> m a Source

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.

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.

minElem :: m a -> a Source

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.

maxElem :: m a -> a Source

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.

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.

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.

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.

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

fromList :: AssocX m k => [(k, a)] -> m a Source

insertList :: AssocX m k => [(k, a)] -> m a -> m a Source

unionList :: AssocX m k => [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

toList :: Assoc m k => m a -> [(k, a)] Source

keysList :: Assoc m k => m a -> [k] Source

toOrdList :: OrdAssoc m k => m a -> [(k, a)] Source

unionListWithKey :: FiniteMap m k => (k -> a -> a -> a) -> [m a] -> m a Source