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 |

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
- empty :: m a
- singleton :: k -> a -> m a
- fromSeq :: Sequence seq => seq (k, a) -> m a
- insert :: k -> a -> m a -> m a
- insertSeq :: Sequence seq => seq (k, a) -> m a -> m a
- union :: m a -> m a -> m a
- unionSeq :: Sequence seq => seq (m a) -> m a
- delete :: k -> m a -> m a
- deleteAll :: k -> m a -> m a
- deleteSeq :: Sequence seq => seq k -> m a -> m a
- null :: m a -> Bool
- size :: m a -> Int
- member :: k -> m a -> Bool
- count :: k -> m a -> Int
- lookup :: k -> m a -> a
- lookupM :: Monad rm => k -> m a -> rm a
- lookupAll :: Sequence seq => k -> m a -> seq a
- lookupAndDelete :: k -> m a -> (a, m a)
- lookupAndDeleteM :: Monad rm => k -> m a -> rm (a, m a)
- lookupAndDeleteAll :: Sequence seq => k -> m a -> (seq a, m a)
- lookupWithDefault :: a -> k -> m a -> a
- adjust :: (a -> a) -> k -> m a -> m a
- adjustAll :: (a -> a) -> k -> m a -> m a
- adjustOrInsert :: (a -> a) -> a -> k -> m a -> m a
- adjustAllOrInsert :: (a -> a) -> a -> k -> m a -> m a
- adjustOrDelete :: (a -> Maybe a) -> k -> m a -> m a
- adjustOrDeleteAll :: (a -> Maybe a) -> k -> m a -> m a
- fold :: (a -> b -> b) -> b -> m a -> b
- fold' :: (a -> b -> b) -> b -> m a -> b
- fold1 :: (a -> a -> a) -> m a -> a
- fold1' :: (a -> a -> a) -> m a -> a
- filter :: (a -> Bool) -> m a -> m a
- partition :: (a -> Bool) -> m a -> (m a, m a)
- elements :: Sequence seq => m a -> seq a
- strict :: m a -> m a
- strictWith :: (a -> b) -> m a -> m a
- structuralInvariant :: m a -> Bool
- instanceName :: m a -> String

- class (AssocX m k, Ord k) => OrdAssocX m k | m -> k where
- minView :: Monad rm => m a -> rm (a, m a)
- minElem :: m a -> a
- deleteMin :: m a -> m a
- unsafeInsertMin :: k -> a -> m a -> m a
- maxView :: Monad rm => m a -> rm (a, m a)
- maxElem :: m a -> a
- deleteMax :: m a -> m a
- unsafeInsertMax :: k -> a -> m a -> m a
- foldr :: (a -> b -> b) -> b -> m a -> b
- foldr' :: (a -> b -> b) -> b -> m a -> b
- foldl :: (b -> a -> b) -> b -> m a -> b
- foldl' :: (b -> a -> b) -> b -> m a -> b
- foldr1 :: (a -> a -> a) -> m a -> a
- foldr1' :: (a -> a -> a) -> m a -> a
- foldl1 :: (a -> a -> a) -> m a -> a
- foldl1' :: (a -> a -> a) -> m a -> a
- unsafeFromOrdSeq :: Sequence seq => seq (k, a) -> m a
- unsafeAppend :: m a -> m a -> m a
- filterLT :: k -> m a -> m a
- filterLE :: k -> m a -> m a
- filterGT :: k -> m a -> m a
- filterGE :: k -> m a -> m a
- partitionLT_GE :: k -> m a -> (m a, m a)
- partitionLE_GT :: k -> m a -> (m a, m a)
- partitionLT_GT :: k -> m a -> (m a, m a)

- class AssocX m k => FiniteMapX m k | m -> k where
- fromSeqWith :: Sequence seq => (a -> a -> a) -> seq (k, a) -> m a
- fromSeqWithKey :: Sequence seq => (k -> a -> a -> a) -> seq (k, a) -> m a
- insertWith :: (a -> a -> a) -> k -> a -> m a -> m a
- insertWithKey :: (k -> a -> a -> a) -> k -> a -> m a -> m a
- insertSeqWith :: Sequence seq => (a -> a -> a) -> seq (k, a) -> m a -> m a
- insertSeqWithKey :: Sequence seq => (k -> a -> a -> a) -> seq (k, a) -> m a -> m a
- unionl :: m a -> m a -> m a
- unionr :: m a -> m a -> m a
- unionWith :: (a -> a -> a) -> m a -> m a -> m a
- unionSeqWith :: Sequence seq => (a -> a -> a) -> seq (m a) -> m a
- intersectionWith :: (a -> b -> c) -> m a -> m b -> m c
- difference :: m a -> m b -> m a
- properSubset :: m a -> m b -> Bool
- subset :: m a -> m b -> Bool
- submapBy :: (a -> a -> Bool) -> m a -> m a -> Bool
- properSubmapBy :: (a -> a -> Bool) -> m a -> m a -> Bool
- sameMapBy :: (a -> a -> Bool) -> m a -> m a -> Bool

- class (OrdAssocX m k, FiniteMapX m k) => OrdFiniteMapX m k | m -> k
- class AssocX m k => Assoc m k | m -> k where
- toSeq :: Sequence seq => m a -> seq (k, a)
- keys :: Sequence seq => m a -> seq k
- mapWithKey :: (k -> a -> b) -> m a -> m b
- foldWithKey :: (k -> a -> b -> b) -> b -> m a -> b
- foldWithKey' :: (k -> a -> b -> b) -> b -> m a -> b
- filterWithKey :: (k -> a -> Bool) -> m a -> m a
- partitionWithKey :: (k -> a -> Bool) -> m a -> (m a, m a)

- class (Assoc m k, OrdAssocX m k) => OrdAssoc m k | m -> k where
- minViewWithKey :: Monad rm => m a -> rm ((k, a), m a)
- minElemWithKey :: m a -> (k, a)
- maxViewWithKey :: Monad rm => m a -> rm ((k, a), m a)
- maxElemWithKey :: m a -> (k, a)
- foldrWithKey :: (k -> a -> b -> b) -> b -> m a -> b
- foldrWithKey' :: (k -> a -> b -> b) -> b -> m a -> b
- foldlWithKey :: (b -> k -> a -> b) -> b -> m a -> b
- foldlWithKey' :: (b -> k -> a -> b) -> b -> m a -> b
- toOrdSeq :: Sequence seq => m a -> seq (k, a)

- class (Assoc m k, FiniteMapX m k) => FiniteMap m k | m -> k where
- unionWithKey :: (k -> a -> a -> a) -> m a -> m a -> m a
- unionSeqWithKey :: Sequence seq => (k -> a -> a -> a) -> seq (m a) -> m a
- intersectionWithKey :: (k -> a -> b -> c) -> m a -> m b -> m c

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

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.

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

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

*ambiguous* at finite relation types if the key appears
more than once in the finite relation. Otherwise, it is *unambiguous*.

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

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

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

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

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

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.

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

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

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

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.

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.

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.

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