Assoc.hs

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