content: -- |
  --   Module      :  Data.Edison.Coll
  --   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 /collection/ abstraction includes sets, bags and priority queues
  --   (heaps).  Collections are defined in Edison as a set of eight classes.
  --
  --   All collections assume at least an equality relation of elements, and
  --   may also assume an ordering relation.
  --
  --   The hierarchy contains a root class 'CollX' together with seven
  --   subclasses satisfying one or more of three common sub-properties:
  --
  -- * /Uniqueness/ Each element in the collection is unique (no two
  --   elements in the collection are equal).  These subclasses, indicated
  --   by the name @Set@, represent sets rather than bags (multi-sets).
  --
  -- * /Ordering/ The elements have a total ordering and it is possible to
  --   process the elements in non-decreasing order. These subclasses,
  --   indicates by the @Ord@ prefix, typically represent either priority
  --   queues (heaps) or sets\/bags implemented as binary search trees.
  --
  -- * /Observability/ An observable collection is one in which it is
  --   possible to view the elements in a collection.  The @X@ suffix
  --   indicates a lack of observability.  This property is discussed is
  --   greater detail below.
  --
  --   Because collections encompass a wide range of abstractions, there is no
  --   single name that is suitable for all collection type constructors.
  --   However, most modules implementing collections will define a type
  --   constructor named either @Bag@, @Set@, or @Heap@.
  --
  --   /Notes on observability/
  --
  --   Note that the equality relation defined by the 'Eq' class is not
  --   necessarily true equality.  Very often it is merely an equivalence
  --   relation, where two equivalent values may be distinguishable by other
  --   means.  For example, we might consider two binary trees to be equal
  --   if they contain the same elements, even if their shapes are different.
  --
  --   Because of this phenomenon, implementations of observable collections
  --   (ie, collections where it is possible to inspect the elements) are rather
  --   constrained.  Such an implementation must retain the actual elements that
  --   were inserted.  For example, it is not possible in general to represent an
  --   observable bag as a finite map from elements to counts, because even if we
  --   know that a given bag contains, say, three elements from some equivalence
  --   class, we do not necessarily know /which/ three.
  --
  --   On the other hand, implementations of /non-observable/ collections have
  --   much greater freedom to choose abstract representations of each
  --   equivalence class.  For example, representing a bag as a finite map from
  --   elements to counts works fine if we never need to know /which/
  --   representatives from an equivalence class are actually present.  As
  --   another example, consider the 'UniqueHash' class defined in
  --   "Data.Edison.Prelude".  If we know that the 'hash' function yields a 
  --   unique integer for each equivalence class, then we can represent a
  --   collection of hashable elements simply as a collection of integers.  With
  --   such a representation, we can still do many useful things like testing for
  --   membership; we just can't support functions like 'fold' or 'filter' that
  --   require the elements themselves, rather than the hashed values.
  
  module Data.Edison.Coll (
      -- * Superclass aliases
      -- ** Monoid
      empty, union,
  
      -- * Non-observable collections
      CollX(..),
      OrdCollX(..),
      SetX(..),
      OrdSetX,
  
      -- * Observable collections
      Coll(..),
      OrdColl(..),
      Set(..),
      OrdSet,
  
      -- * Specializations of all the sequence operations to lists
      fromList,
      insertList,
      unionList,
      deleteList,
      unsafeFromOrdList,
      toList,
      lookupList,
      toOrdList,
      fromListWith,
      insertListWith,
      unionListWith,
  
  ) where
  
  import Prelude hiding (null,foldr,foldl,foldr1,foldl1,lookup,filter)
  import qualified Control.Monad.Fail as Fail
  import Data.Monoid
  
  import Data.Edison.Prelude
  import Data.Edison.Seq(Sequence)
  import Data.Edison.Seq.ListSeq()
  
  
  -- | The empty collection.  Equivalent to @mempty@ from
  --   the @Monoid@ instance.
  --
  --   This function is always /unambiguous/.
  empty :: CollX c a => c
  empty = mempty
  
  -- | Merge two collections.  For sets, it is unspecified which element is
  --   kept in the case of duplicates.  Equivalent to @mappend@ from the
  --   @Monoid@ instance.
  --
  --   This function is /ambiguous/ at set types if the sets are not disjoint.
  --   Otherwise it is /unambiguous/.
  union :: CollX c a => c -> c -> c
  union = mappend
  
  
  -- | This is the root class of the collection hierarchy.  However, it
  --   is perfectly adequate for many applications that use sets or bags.
  class (Eq a,Monoid c) => CollX c a | c -> a where
    -- | create a singleton collection
    --
    --   This function is always /unambiguous/.
    singleton      :: a -> c
  
    -- | Convert a sequence to a collection.  For sets, it is unspecified
    --   which element is kept in case of duplicates.
    --
    --   This function is /ambiguous/ at set types if more than one
    --   equivalent item is in the sequence.  Otherwise it is /unambiguous/.
    fromSeq        :: Sequence seq => seq a -> c
  
    -- | Merge a sequence of collections.  For sets, it is unspecified which
    --   element is kept in the case of duplicates.
    --
    --   This function is /ambiguous/ at set types if the sets in the sequence
    --   are not mutually disjoint. Otherwise it is /unambiguous/.
    unionSeq :: Sequence seq => seq c -> c
  
    -- | Insert an element into a collection.  For sets, if an equal element
    --   is already in the set, the newly inserted element is kept, and the
    --   old element is discarded.
    --
    --   This function is always /unambiguous/.
    insert         :: a -> c -> c
  
    -- | Insert a sequence of elements into a collection.  For sets,
    --   the behavior with regard to multiple equal elements is unspecified.
    --
    --   This function is /ambiguous/ at set types if the sequence contains
    --   more than one equivalent item or an item which is already in the set.
    --   Otherwise it is /unambiguous/.
    insertSeq      :: Sequence seq => seq a -> c -> c
  
    -- | Delete a single occurrence of the given element from a collection.
    --   For bags, it is unspecified which element will be deleted.
    --
    --   This function is /ambiguous/ at bag types if more than one item exists
    --   in the bag equivalent to the given item.  Otherwise it is /unambiguous/.
    delete         :: a -> c -> c
  
    -- | Delete all occurrences of an element from a collection.  For sets
    --   this operation is identical to 'delete'.
    --
    --   This function is always /unambiguous/.
    deleteAll      :: a -> c -> c
  
    -- | Delete a single occurrence of each of the given elements from
    --   a collection.  For bags, there may be multiple occurrences of a
    --   given element in the collection, in which case it is unspecified
    --   which is deleted.
    --
    --   This function is /ambiguous/ at bag types if more than one item
    --   exists in the bag equivalent to any item in the list and the number
    --   of equivalent occurrences of that item in the sequence is less than
    --   the number of occurrences in the bag.  Otherwise it is /unambiguous/.
    deleteSeq      :: Sequence seq => seq a -> c -> c
  
    -- | Test whether the collection is empty.
    --
    -- /Axioms:/
    --
    -- * @null xs = (size xs == 0)@
    --
    --   This function is always /unambiguous/.
    null           :: c -> Bool
  
    -- | Return the number of elements in the collection.
    --
    --   This function is always /unambiguous/.
    size           :: c -> Int
  
    -- | Test whether the given element is in the collection.
    --
    -- /Axioms:/
    --
    -- * @member x xs = (count x xs > 0)@
    --
    --   This function is always /unambiguous/.
    member         :: a -> c -> Bool
  
    -- | Count how many copies of the given element are in the collection.
    --   For sets, this will always return 0 or 1.
    --
    --   This function is always /unambiguous/.
    count          :: a -> c -> Int
  
    -- | 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.  In many
    --   collections, the collction \"shape\" depends on the value of the elements;
    --   in such cases, the values of the elements will be forced to the extent
    --   necessary to force the structure of the collection, but no further.
    --
    --   This function is always /unambiguous/.
    strict         :: c -> c
  
    -- | A method to facilitate unit testing.  Returns 'True' if the structural
    --   invariants of the implementation hold for the given 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 :: c -> Bool
  
    -- | The name of the module implementing @c@
    instanceName   :: c -> String
  
  
  -- | Collections for which the elements have an ordering relation.
  
  class (CollX c a, Ord a) => OrdCollX c a | c -> a where
  
    -- | Delete the minimum element from the collection.  If there is more
    --   than one minimum, it is unspecified which is deleted.  If the collection
    --   is empty, it will be returned unchanged.
    --
    --   This function is /ambiguous/ at bag types if more than one minimum
    --   element exists in the bag.  Otherwise it is /unambiguous/.
    deleteMin          :: c -> c
  
    -- | Delete the maximum element from the collection.  If there is more
    --   than one maximum, it is unspecified which is deleted.  If the collection
    --   is empty, it will be returned unchanged.
    --
    --   This function is /ambiguous/ at bag types if more than one maximum
    --   element exists in the bag.  Otherwise it is /unambiguous/.
    deleteMax          :: c -> c
  
    -- | Insert an element into a collection which is guaranteed to be
    --   @\<=@ any existing elements in the collection.  For sets, the
    --   precondition is strengthened to @\<@.
    --
    --   This function is /unambiguous/, under the above preconditions.
    unsafeInsertMin    :: a -> c -> c
  
    -- | Insert an element into a collection which is guaranteed to be
    --   @>=@ any existing elements in the collection.  For sets, the 
    --   precondition is strengthened to @>@.
    --
    --   This function is /unambiguous/, under the above preconditions.
    unsafeInsertMax    :: a -> c -> c
  
    -- | Convert a sequence in non-decreasing order into a collection.
    --   For sets, the sequence must be in increasing order.
    --
    --   This function is /unambiguous/, under the above preconditions.
    unsafeFromOrdSeq   :: Sequence seq => seq a -> c
  
    -- | Union two collections where every element in the first
    --   collection is @\<=@ every element in the second collection.
    --   For sets, this precondition is strengthened to @\<@.
    --
    --   This function is /unambiguous/, under the above preconditions.
    unsafeAppend       :: c -> c -> c
  
    -- | Extract the sub-collection of elements @\<@ the given element.
    --
    -- /Axioms:/
    --
    -- * @filterLT x xs = filter (\< x) xs@
    --
    --  This function is always /unambiguous/.
    filterLT           :: a -> c -> c
  
    -- | Extract the sub-collection of elements @\<=@ the given element.
    --
    -- /Axioms:/
    --
    -- * @filterLE x xs = filter (\<= x) xs@
    --
    --  This function is always /unambiguous/.
    filterLE           :: a -> c -> c
  
    -- | Extract the sub-collection of elements @>@ the given element.
    --
    -- /Axioms:/
    --
    -- * @filterGT x xs = filter (> x) xs@
    --
    --  This function is always /unambiguous/.
    filterGT           :: a -> c -> c
  
    -- | Extract the sub-collection of elements @>=@ the given element.
    --
    -- /Axioms:/
    --
    -- * @filterGE x xs = filter (>= x) xs@
    --
    --  This function is always /unambiguous/.
    filterGE           :: a -> c -> c
  
    -- | Split a collection into those elements @\<@ a given element and
    --   those @>=@.
    --
    -- /Axioms:/
    --
    -- * @partitionLT_GE xs = partition (\<) xs@
    --
    --  This function is always /unambiguous/.
    partitionLT_GE     :: a -> c -> (c, c)
  
    -- | Split a collection into those elements @\<=@ a given element and
    --   those @>@.
    --
    -- /Axioms:/
    --
    -- * @partitionLE_GT xs = partition (\<=) xs@
    --
    --  This function is always /unambiguous/.
    partitionLE_GT     :: a -> c -> (c, c)
  
    -- | Split a collection into those elements @\<@ a given element and
    --   those @>@.  All elements equal to the given element are discarded.
    --
    -- /Axioms:/
    --
    -- *@partitionLT_GT x xs = (filterLT x xs,filterGT x xs)@
    --
    --  This function is always /unambiguous/.
    partitionLT_GT     :: a -> c -> (c, c)
  
  
  -- | A collection where the set property is maintained; that is, a set
  --   contains at most one element of the equivalence class formed by the
  --   'Eq' instance on the elements.
  class CollX c a => SetX c a | c -> a where
  
    -- | Computes the intersection of two sets.  It is unspecified which 
    --   element is kept when equal elements appear in each set.
    --
    --   This function is /ambiguous/, except when the sets are disjoint.
    intersection :: c -> c -> c
  
    -- | Computes the difference of two sets; that is, all elements in
    --   the first set which are not in the second set.
    --
    --   This function is always /unambiguous/.
    difference  :: c -> c -> c
  
    -- | Computes the symmetric difference of two sets; that is, all elements
    --   which appear in exactily one of the two sets.
    --
    --   This function is always /unambiguous/.
    symmetricDifference :: c -> c -> c
  
    -- | Test whether the first set is a proper subset of the second set;
    --   that is, if every element in the first set is also a member of the
    --   second set AND there exists some element in the second set which
    --   is not present in the first.
    --
    --   This function is always /unambiguous/.
    properSubset  :: c -> c -> Bool
  
    -- | Test whether the first set is a subset of the second set; that is, if
    --   every element in the first set is also a member of the second set.
    --
    --   This function is always /unambiguous/.
    subset        :: c -> c -> Bool
  
  
  -- | Sets where the elements also have an ordering relation.
  --   This class contains no methods; it is only an abbreviation for
  --   the context @(OrdCollX c a,SetX c a)@.
  
  class (OrdCollX c a, SetX c a) => OrdSetX c a | c -> a
    -- no methods
  
  -- | Collections with observable elements.  See the module documentation for
  --   comments on observability.
  
  class CollX c a => Coll c a | c -> a where
  
    -- | List the elements of the collection in an unspecified order.
    --
    --   This function is /ambiguous/ iff the collection contains more
    --   than one element.
    toSeq      :: Sequence seq => c -> seq a
  
    -- | Lookup one element equal to the given element.  If no elements
    --   exist in the collection equal to the given element, an error is
    --   signaled.  If multiple copies of the given element exist in the
    --   collection, it is unspecified which is returned.
    --
    --   This function is /ambiguous/ at bag types, when more than one
    --   element equivalent to the given item is in the bag.  Otherwise
    --   it is /unambiguous/.
    lookup     :: a -> c -> a
  
    -- | Lookup one element equal to the given element.  If no elements
    --   exist in the collection equal to the given element, 'fail' is called.
    --   If multiple copies of the given element exist in the collection, it
    --   is unspecified which is returned.
    --
    --   This function is /ambiguous/ at bag types, when more than one
    --   element equivalent to the given item is in the bag.  Otherwise
    --   it is /unambiguous/.
    lookupM    :: (Fail.MonadFail m) => a -> c -> m a
  
    -- | Return a sequence containing all elements in the collection equal to
    --   the given element in an unspecified order.
    --
    --   This function is /ambiguous/ at bag types, when more than one
    --   element equivalent to the given item is in the bag.  Otherwise
    --   it is /unambiguous/.
    lookupAll  :: Sequence seq => a -> c -> seq a
  
    -- | Lookup one element equal to the (second) given element in the collection.
    --   If no elements exist in the collection equal to the given element, then
    --   the default element is returned.
    --
    --   This function is /ambiguous/ at bag types, when more than one
    --   element equivalent to the given item is in the bag.  Otherwise
    --   it is /unambiguous/.
    lookupWithDefault  :: a -- ^ default element
                       -> a -- ^ element to lookup
                       -> c -- ^ collection
                       -> a
  
    -- | Fold over all the elements in a collection in an unspecified order.
    --
    --   @fold f@ is /unambiguous/ iff @f@ is fold-commutative.
    fold       :: (a -> b -> b) -> b -> c -> b
  
    -- | A strict variant of 'fold'.
    --
    --   @fold' f@ is /unambiguous/ iff @f@ is fold-commutative.
    fold'      :: (a -> b -> b) -> b -> c -> b
  
    -- | Fold over all the elements in a collection in an unspecified order.
    --   An error is signaled if the collection is empty.
    --
    --   @fold1 f@ is /unambiguous/ iff @f@ is fold-commutative.
    fold1      :: (a -> a -> a) -> c -> a
  
    -- | A strict variant of 'fold1'.
    --
    --   @fold1' f@ is /unambiguous/ iff @f@ is fold-commutative.
    fold1'     :: (a -> a -> a) -> c -> a
  
    -- | Remove all elements not satisfying the predicate.
    --
    --   This function is always /unambiguous/.
    filter     :: (a -> Bool) -> c -> c
  
    -- | Returns two collections, the first containing all the elements
    --   satisfying the predicate, and the second containing all the
    --   elements not satisfying the predicate.
    --
    --   This function is always /unambiguous/.
    partition  :: (a -> Bool) -> c -> (c, c)
  
    -- | Similar to 'strict', this function walks the datastructure forcing closures.
    --   However, @strictWith@ will additionally apply the given function to the
    --   collection 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) -> c -> c
  
  
  -- | Collections with observable elements where the elements additionally
  --   have an ordering relation.  See the module documentation for comments
  --   on observability.
  
  class (Coll c a, OrdCollX c a) => OrdColl c a | c -> a where
  
    -- | Return the minimum element in the collection, together with
    --   the collection without that element.  If there are multiple
    --   copies of the minimum element, it is unspecified which is chosen.
    --   /Note/ that 'minView', 'minElem', and 'deleteMin' may make different
    --   choices.  Calls 'fail' if the collection is empty.
    --
    --   This function is /ambiguous/ at bag types, if more than one minimum
    --   element exists in the bag.  Otherwise, it is /unambiguous/.
    minView    :: (Fail.MonadFail m) => c -> m (a, c)
  
    -- | Return the minimum element in the collection.  If there are multiple
    --   copies of the minimum element, it is unspecified which is chosen.
    --   /Note/ that 'minView', 'minElem', and 'deleteMin' may make different
    --   choices.  Signals an error if the collection is empty.
    --
    --   This function is /ambiguous/ at bag types, if more than one minimum
    --   element exists in the bag.  Otherwise, it is /unambiguous/.
    minElem    :: c -> a
  
    -- | Return the maximum element in the collection, together with 
    --   the collection without that element.  If there are multiple
    --   copies of the maximum element, it is unspecified which is chosen.
    --   /Note/ that 'maxView', 'maxElem' and 'deleteMax' may make different
    --   choices.  Calls 'fail' if the collection is empty.
    --
    --   This function is /ambiguous/ at bag types, if more than one maximum
    --   element exists in the bag.  Otherwise, it is /unambiguous/.
    maxView    :: (Fail.MonadFail m) => c -> m (a, c)
  
    -- | Return the maximum element in the collection.  If there are multiple
    --   copies of the maximum element, it is unspecified which is chosen.
    --   /Note/ that 'maxView', 'maxElem' and 'deleteMax' may make different
    --   choices.  Signals an error if the collection is empty.
    --
    --   This function is /ambiguous/ at bag types, if more than one maximum
    --   element exists in the bag.  Otherwise, it is /unambiguous/.
    maxElem    :: c -> a
  
    -- | Fold across the elements in non-decreasing order with right
    --   associativity. (For sets, this will always be increasing order)
    --
    --   This function is /unambiguous/ if the combining function is
    --   fold-commutative, at all set types, and at bag types
    --   where no two equivalent elements exist in the bag.  Otherwise
    --   it is /ambiguous/.
    foldr      :: (a -> b -> b) -> b -> c -> b
  
    -- | A strict variant of 'foldr'.
    --
    --   This function is /unambiguous/ if the combining function is
    --   fold-commutative, at all set types, and at bag types
    --   where no two equivalent elements exist in the bag.  Otherwise
    --   it is /ambiguous/.
    foldr'     :: (a -> b -> b) -> b -> c -> b
  
    -- | Fold across the elements in non-decreasing order with left
    --   associativity. (For sets, this will always be increasing order)
    --
    --   This function is /unambiguous/ if the combining function is
    --   fold-commutative, at all set types, and at bag types
    --   where no two equivalent elements exist in the bag.  Otherwise
    --   it is /ambiguous/.
    foldl      :: (b -> a -> b) -> b -> c -> b
  
    -- | A strict variant of 'foldl'.
    --
    --   This function is /unambiguous/ if the combining function is
    --   fold-commutative, at all set types, and at bag types
    --   where no two equivalent elements exist in the bag.  Otherwise
    --   it is /ambiguous/.
    foldl'     :: (b -> a -> b) -> b -> c -> b
  
    -- | Fold across the elements in non-decreasing order with right
    --   associativity, or signal an error if the collection is empty.
    --   (For sets, this will always be increasing order)
    --
    --   This function is /unambiguous/ if the combining function is
    --   fold-commutative, at all set types, and at bag types
    --   where no two equivalent elements exist in the bag.  Otherwise
    --   it is /ambiguous/.
    foldr1     :: (a -> a -> a) -> c -> a
  
    -- | A strict variant of 'foldr1'.
    --
    --   This function is /unambiguous/ if the combining function is
    --   fold-commutative, at all set types, and at bag types
    --   where no two equivalent elements exist in the bag.  Otherwise
    --   it is /ambiguous/.
    foldr1'    :: (a -> a -> a) -> c -> a
  
    -- | Fold across the elements in non-decreasing order with left
    --   associativity, or signal an error if the collection is empty.
    --   (For sets, this will always be increasing order)
    --
    --   This function is /unambiguous/ if the combining function is
    --   fold-commutative, at all set types, and at bag types
    --   where no two equivalent elements exist in the bag.  Otherwise
    --   it is /ambiguous/.
    foldl1     :: (a -> a -> a) -> c -> a
  
    -- | A strict variant of 'foldl1'.
    --
    --   This function is /unambiguous/ if the combining function is
    --   fold-commutative, at all set types, and at bag types
    --   where no two equivalent elements exist in the bag.  Otherwise
    --   it is /ambiguous/.
    foldl1'    :: (a -> a -> a) -> c -> a
  
    -- | List the elements in non-decreasing order. (For sets, this will always
    --   be increasing order)
    --
    --   At set types, this function is /unambiguous/.  At bag types, it
    --   is /unambiguous/ if no two equivalent elements exist in the bag;
    --   otherwise it is /ambiguous/.
    toOrdSeq   :: Sequence seq => c -> seq a
  
    -- | Map a monotonic function across all elements of a collection.  The 
    --   function is required to satisfy the following precondition:
    --
    -- > forall x y. x < y ==> f x < f y
    --
    --   This function is /unambiguous/, under the precondition.
    unsafeMapMonotonic :: (a -> a) -> c -> c
  
  
  
  -- | Collections with observable elements where the set property is maintained;
  --   that is, a set contains at most one element of the equivalence class
  --   formed by the 'Eq' instance on the elements.
  --
  --   /WARNING: Each of the following \"With\" functions is unsafe./ 
  --   The passed in combining functions are used to choose which element is kept
  --   in the case of duplicates. They are required to satisfy the precondition
  --   that, given two equal elements, they return a third element equal to the
  --   other two.  Usually, the combining function just returns its first or
  --   second argument, but it can combine elements in non-trivial ways.
  --
  --   The combining function should usually be associative.  Where the function
  --   involves a sequence of elements, the elements will be combined from
  --   left-to-right, but with an unspecified associativity.
  --
  --   For example, if @x == y == z@,
  --   then @fromSeqWith (+) [x,y,z]@ equals either
  --     @single (x + (y + z))@
  --   or
  --     @single ((x + y) + z)@
  
  class (Coll c a, SetX c a) => Set c a | c -> a where
  
    -- | Same as 'fromSeq' but with a combining function to resolve duplicates.  
    --
    --   This function is /unambiguous/ under the \"with\" precondition
    --   if the combining function is associative.  Otherwise it is /ambiguous/.
    fromSeqWith     :: Sequence seq => (a -> a -> a) -> seq a -> c
  
    -- | Same as 'insert' but with a combining function to resolve duplicates.
    --
    --   This function is /unambiguous/ under the \"with\" precondition.
    insertWith      :: (a -> a -> a) -> a -> c -> c
  
    -- | Same as 'insertSeq' but with a combining function to resolve duplicates.
    --
    --   This function is /unambiguous/ under the \"with\" precondition
    --   if the combining function is associative.  Otherwise it is /ambiguous/.
    insertSeqWith   :: Sequence seq => (a -> a -> a) -> seq a -> c -> c
  
    -- | Left biased union.
    --
    --   /Axioms:/
    --
    -- * @unionl = unionWith (\\x y -> x)@
    --
    --   This function is always /unambiguous/.
    unionl          :: c -> c -> c
   
    -- | Right biased union.
    --
    --   /Axioms:/
    --
    -- * @unionr = unionWith (\\x y -> y)@
    --
    --  This function is always /unambiguous/.
    unionr          :: c -> c -> c
  
    -- | Same as 'union', but with a combining function to resolve duplicates.    
    --
    --   This function is /unambiguous/ under the \"with\" precondition.
    unionWith       :: (a -> a -> a) -> c -> c -> c
  
    -- | Same as 'unionSeq', but with a combining function to resolve duplicates.
    --
    --   This function is /unambiguous/ under the \"with\" precondition
    --   if the combining function is associative.  Otherwise it is /ambiguous/.
    unionSeqWith    :: Sequence seq => (a -> a -> a) -> seq (c) -> c
  
    -- | Same as 'intersection', but with a combining function to resolve duplicates.
    --
    --  This function is /unambiguous/ under the \"with\" precondition.
    intersectionWith   :: (a -> a -> a) -> c -> c -> c
  
  
  
  
  -- | Collections with observable elements where the set property is maintained
  --   and where additionally, there is an ordering relation on the elements.
  --   This class introduces no new methods, and is simply an abbreviation 
  --   for the context:
  --
  --   @(OrdColl c a,Set c a)@
  
  class (OrdColl c a, Set c a) => OrdSet c a | c -> a
    -- no methods
  
  
  -- specialize all the sequence operations to lists
  
  fromList          :: CollX c a => [a] -> c
  insertList        :: CollX c a => [a] -> c -> c
  unionList         :: CollX c a => [c] -> c
  deleteList        :: CollX c a => [a] -> c -> c
  unsafeFromOrdList :: OrdCollX c a => [a] -> c
  toList            :: Coll c a => c -> [a]
  lookupList        :: Coll c a => a -> c -> [a]
  toOrdList         :: OrdColl c a => c -> [a]
  fromListWith      :: Set c a => (a -> a -> a) -> [a] -> c
  insertListWith    :: Set c a => (a -> a -> a) -> [a] -> c -> c
  unionListWith     :: Set c a => (a -> a -> a) -> [c] -> c
  
  fromList = fromSeq
  insertList = insertSeq
  unionList = unionSeq
  deleteList = deleteSeq
  unsafeFromOrdList = unsafeFromOrdSeq
  toList = toSeq
  lookupList = lookupAll
  toOrdList = toOrdSeq
  fromListWith = fromSeqWith
  insertListWith = insertSeqWith
  unionListWith = unionSeqWith
  