-- |
-- Module : Data.Edison.Assoc
-- 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)
--
-- 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.
module Data.Edison.Assoc (
-- * Superclass aliases
map,
-- * Non-observable associative collections
AssocX(..),
OrdAssocX(..),
FiniteMapX(..),
OrdFiniteMapX,
-- * Observable associative collections
Assoc(..),
OrdAssoc(..),
FiniteMap(..),
OrdFiniteMap,
-- * Specilizations of submap operations
submap,
properSubmap,
sameMap,
-- * Specializations of sequence operations to lists
fromList,
insertList,
unionList,
deleteList,
lookupList,
elementsList,
unsafeFromOrdList,
fromListWith,
fromListWithKey,
insertListWith,
insertListWithKey,
unionListWith,
toList,
keysList,
toOrdList,
unionListWithKey
) where
import Prelude hiding (null,map,lookup,foldr,foldl,foldr1,foldl1,filter)
import Data.Edison.Prelude
import Data.Edison.Seq(Sequence)
import Data.Edison.Seq.ListSeq()
-- | Apply a function to the elements of every binding in the associative
-- collection. Identical to @fmap@ from @Functor@.
--
-- This function is always /unambiguous/.
map :: AssocX m k => (a -> b) -> m a -> m b
map = fmap
-- | Specialization of 'submapBy' where the comparison function is
-- given by @(==)@.
submap :: (Eq a,FiniteMapX m k) => m a -> m a -> Bool
submap = submapBy (==)
-- | Specialization of 'properSubmapBy' where the comparison function
-- is given by @(==)@.
properSubmap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool
properSubmap = properSubmapBy (==)
-- | Specialization of 'sameMapBy' where the comparison function is
-- given by @(==)@.
sameMap :: (Eq a,FiniteMapX m k) => m a -> m a -> Bool
sameMap = sameMapBy (==)
-- | The root class of the associative collection hierarchy.
class (Eq k,Functor m) => AssocX m k | m -> k where
-- | The empty associative collection.
--
-- This function is always /unambiguous/.
empty :: m a
-- | Create an associative collection with a single binding.
--
-- This function is always /unambiguous/.
singleton :: k -> a -> m a
-- | 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/.
fromSeq :: Sequence seq => seq (k,a) -> m a
-- | 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/.
insert :: k -> a -> m a -> m a
-- | 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/.
insertSeq :: Sequence seq => seq (k,a) -> m a -> m a
-- | 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/.
union :: m a -> m a -> m a
-- | 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/.
unionSeq :: Sequence seq => seq (m a) -> m a
-- | 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/.
delete :: k -> m a -> m a
-- | 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/.
deleteAll :: k -> m a -> m a
-- | 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/.
deleteSeq :: Sequence seq => seq k -> m a -> m a
-- | Test whether the associative collection is empty.
--
-- /Axioms:/
--
-- * @null m = (size m == 0)@
--
-- This function is always /unambiguous/.
null :: m a -> Bool
-- | Return the number of bindings in the associative collection.
--
-- This function is always /unambiguous/.
size :: m a -> Int
-- | Test whether the given key is bound in the associative collection.
--
-- This function is always /unambiguous/.
member :: k -> m a -> Bool
-- | Returns the number of bindings with the given key. For finite maps
-- this will always return 0 or 1.
--
-- This function is always /unambiguous/.
count :: k -> m a -> Int
-- | 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/.
lookup :: k -> m a -> a
-- | 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/.
lookupM :: (Monad rm) => k -> m a -> rm a
-- | 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/.
lookupAll :: Sequence seq => k -> m a -> seq a
-- | 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/.
lookupAndDelete :: k -> m a -> (a, m a)
-- | 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/.
lookupAndDeleteM :: (Monad rm) => k -> m a -> rm (a, m a)
-- | 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/.
lookupAndDeleteAll :: (Sequence seq) => k -> m a -> (seq a,m 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/.
lookupWithDefault :: a -- ^ default element
-> k -- ^ the key to look up
-> m a -- ^ the associative collection
-> a
-- | 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/.
adjust :: (a -> a) -> k -> m a -> m a
-- | 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/.
adjustAll :: (a -> a) -> k -> m a -> m a
-- | 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/.
adjustOrInsert :: (a -> a) -> a -> k -> m a -> m a
-- | 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/.
adjustAllOrInsert :: (a -> a) -> a -> k -> m a -> m a
-- | 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/.
adjustOrDelete :: (a -> Maybe a) -> k -> m a -> m a
-- | 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/.
adjustOrDeleteAll :: (a -> Maybe a) -> k -> m a -> m a
-- | 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
-- | A strict variant of 'fold'.
--
-- @fold' f@ is /unambiguous/ iff @f@ is fold-commutative.
fold' :: (a -> b -> b) -> b -> m a -> b
-- | 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
-- | A strict variant of 'fold1'.
--
-- @fold1' f@ is /unambiguous/ iff @f@ is fold-commutative.
fold1' :: (a -> a -> a) -> m a -> a
-- | Extract all bindings whose elements satisfy the given predicate.
--
-- This function is always /unambiguous/.
filter :: (a -> Bool) -> m a -> m a
-- | Split an associative collection into those bindings which satisfy the
-- given predicate, and those which do not.
--
-- This function is always /unambiguous/.
partition :: (a -> Bool) -> m a -> (m a, m a)
-- | 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.
elements :: Sequence seq => m a -> seq a
-- | 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/.
strict :: m a -> m a
-- | 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/.
strictWith :: (a -> b) -> m a -> m a
-- | 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.
structuralInvariant :: m a -> Bool
-- | Returns the name of the module implementing this associative collection.
instanceName :: m a -> String
-- | An associative collection where the keys additionally have an ordering
-- relation.
class (AssocX m k, Ord k) => OrdAssocX m k | m -> k where
-- | 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/.
minView :: (Monad rm) => m a -> rm (a, m a)
-- | 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/.
minElem :: m a -> a
-- | 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/.
deleteMin :: m a -> m a
-- | 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.
unsafeInsertMin :: k -> a -> m a -> m a
-- | 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/.
maxView :: (Monad rm) => m a -> rm (a, m a)
-- | 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/.
maxElem :: m a -> a
-- | 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/.
deleteMax :: m a -> m a
-- | 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.
unsafeInsertMax :: k -> a -> m a -> m a
-- | 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
-- | 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/.
foldr' :: (a -> b -> b) -> b -> m a -> b
-- | 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
-- | 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/.
foldl' :: (b -> a -> b) -> b -> m a -> b
-- | 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
-- | 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/.
foldr1' :: (a -> a -> a) -> m a -> a
-- | 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
-- | 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/.
foldl1' :: (a -> a -> a) -> m a -> a
-- | 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.
unsafeFromOrdSeq :: Sequence seq => seq (k,a) -> m a
-- | 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.
unsafeAppend :: m a -> m a -> m a
-- | Extract all bindings whose keys are @\<@ the given key.
--
-- This function is always /unambiguous/.
filterLT :: k -> m a -> m a
-- | Extract all bindings whose keys are @\<=@ the given key.
--
-- This function is always /unambiguous/.
filterLE :: k -> m a -> m a
-- | Extract all bindings whose keys are @>@ the given key.
--
-- This function is always /unambiguous/.
filterGT :: k -> m a -> m a
-- | Extract all bindings whose keys are @>=@ the given key.
--
-- This function is always /unambiguous/.
filterGE :: k -> m a -> m a
-- | 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_GE :: k -> m a -> (m a, m a)
-- | 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)
-- | 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/.
partitionLT_GT :: k -> m a -> (m a, m a)
-- | An associative collection where the keys form a set; that is, each key
-- appears in the associative collection at most once.
class AssocX m k => FiniteMapX m k | m -> k where
-- | Same as 'fromSeq', but with a combining function to resolve duplicates.
--
-- This function is always /unambiguous/.
fromSeqWith :: Sequence seq => (a -> a -> a) -> seq (k,a) -> m a
-- | 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/.
fromSeqWithKey :: Sequence seq => (k -> a -> a -> a) -> seq (k,a) -> m a
-- | Same as 'insert', but with a combining function to resolve duplicates.
--
-- This function is /unambiguous/.
insertWith :: (a -> a -> a) -> k -> a -> m a -> m a
-- | 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/.
insertWithKey :: (k -> a -> a -> a) -> k -> a -> m a -> m a
-- | Same as 'insertSeq', but with a combining function to resolve duplicates.
--
-- This function is /unambiguous/.
insertSeqWith :: Sequence seq =>
(a -> a -> a) -> seq (k,a) -> m a -> m a
-- | 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/.
insertSeqWithKey :: Sequence seq =>
(k -> a -> a -> a) -> seq (k,a) -> m a -> m a
-- | Left biased union.
--
-- /Axioms:/
--
-- * @unionl = unionwith (\\x y -> x)@
--
-- This function is /unambiguous/.
unionl :: m a -> m a -> m a
-- | Right biased union.
--
-- /Axioms:/
--
-- * @unionr = unionWith (\\x y -> y)@
--
-- This function is /unambiguous/.
unionr :: m a -> m a -> m a
-- | Same as 'union', but with a combining function to resolve duplicates.
--
-- This function is /unambiguous/.
unionWith :: (a -> a -> a) -> m a -> m a -> m a
-- | Same as 'unionSeq', but with a combining function to resolve duplicates.
--
-- This function is /unambiguous/.
unionSeqWith :: Sequence seq => (a -> a -> a) -> seq (m a) -> m a
-- | 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/.
intersectionWith :: (a -> b -> c) -> m a -> m b -> m c
-- | 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/.
difference :: m a -> m b -> m a
-- | 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/.
properSubset :: m a -> m b -> Bool
-- | 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/.
subset :: m a -> m b -> Bool
-- | 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/.
submapBy :: (a -> a -> Bool) -> m a -> m a -> Bool
-- | 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/.
properSubmapBy :: (a -> a -> Bool) -> m a -> m a -> Bool
-- | 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/.
sameMapBy :: (a -> a -> Bool) -> m a -> m a -> Bool
-- | Finite maps where the keys additionally have an ordering relation.
-- This class introduces no new methods.
class (OrdAssocX m k, FiniteMapX m k) => OrdFiniteMapX m k | m -> k
-- | Associative collections where the keys are observable.
class AssocX m k => Assoc m k | m -> k where
-- | 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.
toSeq :: Sequence seq => m a -> seq (k,a)
-- | 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.
keys :: Sequence seq => m a -> seq k
-- | 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.
mapWithKey :: (k -> a -> b) -> m a -> m b
-- | 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
-- | A strict variant of 'foldWithKey'.
--
-- @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
-- | 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.
filterWithKey :: (k -> a -> Bool) -> m a -> m a
-- | 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.
partitionWithKey :: (k -> a -> Bool) -> m a -> (m a, m a)
-- | An associative collection with observable keys where the keys additionally
-- have an ordering relation.
class (Assoc m k, OrdAssocX m k) => OrdAssoc m k | m -> k where
-- | 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.
minViewWithKey :: (Monad rm) => m a -> rm ((k, a), m a)
-- | 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.
minElemWithKey :: m a -> (k,a)
-- | 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.
maxViewWithKey :: (Monad rm) => m a -> rm ((k, a), m a)
-- | 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.
maxElemWithKey :: m a -> (k,a)
-- | 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
-- | 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/.
foldrWithKey' :: (k -> a -> b -> b) -> b -> m a -> b
-- | 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
-- | 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/.
foldlWithKey' :: (b -> k -> a -> b) -> b -> m a -> b
-- | 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.
toOrdSeq :: Sequence seq => m a -> seq (k,a)
-- | Finite maps with observable keys.
class (Assoc m k, FiniteMapX m k) => FiniteMap m k | m -> k where
-- | 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.
unionWithKey :: (k -> a -> a -> a) -> m a -> m a -> m a
-- | 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.
unionSeqWithKey :: Sequence seq => (k -> a -> a -> a) -> seq (m a) -> m a
-- | 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.
intersectionWithKey :: (k -> a -> b -> c) -> m a -> m b -> m c
-- | Finite maps with observable keys where the keys additionally
-- have an ordering relation. This class introduces no new methods.
class (OrdAssoc m k, FiniteMap m k) => OrdFiniteMap m k | m -> k
-- specialize sequence operations to lists
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
fromList = fromSeq
insertList = insertSeq
unionList = unionSeq
deleteList = deleteSeq
lookupList = lookupAll
elementsList = elements
unsafeFromOrdList = unsafeFromOrdSeq
fromListWith = fromSeqWith
fromListWithKey = fromSeqWithKey
insertListWith = insertSeqWith
insertListWithKey = insertSeqWithKey
unionListWith = unionSeqWith
toList = toSeq
keysList = keys
toOrdList = toOrdSeq
unionListWithKey = unionSeqWithKey