-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A library of efficent, purely-functional data structures (API)
--   
--   Edison is a library of purely functional data structures written by
--   Chris Okasaki. It is named after Thomas Alva Edison and for the
--   mnemonic value EDiSon (Efficent Data Structures). Edison provides
--   several families of abstractions, each with multiple implementations.
--   The main abstractions provided by Edison are: Sequences such as
--   stacks, queues, and dequeues; Collections such as sets, bags and
--   heaps; and Associative Collections such as finite maps and priority
--   queues where the priority and element are distinct.
@package EdisonAPI
@version 1.2.2


-- | This module is a central depository of common definitions used
--   throughout Edison.
module Data.Edison.Prelude

-- | This class represents hashable objects. If obeys the following
--   invariant:
--   
--   <pre>
--   forall x,y :: a. (x == y) implies (hash x == hash y)
--   </pre>
class Eq a => Hash a
hash :: Hash a => a -> Int

-- | This class represents hashable objects where the hash function is
--   <i>unique</i> (injective). There are no new methods, just a stronger
--   invariant:
--   
--   <pre>
--   forall x,y :: a. (x == y) iff (hash x == hash y)
--   </pre>
class Hash a => UniqueHash a

-- | This class represents hashable objects where the hash is reversible.
--   
--   <pre>
--   forall x :: a. unhash (hash x) == x
--   </pre>
--   
--   Note that:
--   
--   <pre>
--   hash (unhash i) == i
--   </pre>
--   
--   does not necessarily hold because <a>unhash</a> is not necessarily
--   defined for all <tt>i</tt>, only for all <tt>i</tt> in the range of
--   hash.
class UniqueHash a => ReversibleHash a
unhash :: ReversibleHash a => Int -> a

-- | This class represents a quantity that can be measured. It is
--   calculated by an associative function with a unit (hence the
--   <tt>Monoid</tt> superclass, and by a function which gives the
--   measurement for an individual item. Some datastructures are able to
--   speed up the calculation of a measure by caching intermediate values
--   of the computation.
class Monoid v => Measured v a | a -> v
measure :: Measured v a => a -> v


-- | The sequence abstraction is usually viewed as a hierarchy of ADTs
--   including lists, queues, deques, catenable lists, etc. However, such a
--   hierarchy is based on efficiency rather than functionality. For
--   example, a list supports all the operations that a deque supports,
--   even though some of the operations may be inefficient. Hence, in
--   Edison, all sequence data structures are defined as instances of the
--   single Sequence class:
--   
--   <pre>
--   class (Functor s, MonadPlus s) =&gt; Sequence s
--   </pre>
--   
--   All sequences are also instances of <a>Functor</a>, <a>Monad</a>, and
--   <a>MonadPlus</a>. In addition, all sequences are expected to be
--   instances of <tt>Eq</tt>, <tt>Show</tt>, and <tt>Read</tt>, although
--   this is not enforced.
--   
--   We follow the naming convention that every module implementing
--   sequences defines a type constructor named <tt>Seq</tt>.
--   
--   For each method the "default" complexity is listed. Individual
--   implementations may differ for some methods. The documentation for
--   each implementation will list those methods for which the running time
--   differs from these.
--   
--   A description of each Sequence function appears below. In most cases
--   psudeocode is also provided. Obviously, the psudeocode is illustrative
--   only.
--   
--   Sequences are represented in psudecode between angle brackets:
--   
--   <pre>
--   &lt;x0,x1,x2...,xn-1&gt;
--   </pre>
--   
--   Such that <tt>x0</tt> is at the left (front) of the sequence and
--   <tt>xn-1</tt> is at the right (rear) of the sequence.
module Data.Edison.Seq

-- | Return the result of applying a function to every element of a
--   sequence. Identical to <tt>fmap</tt> from <tt>Functor</tt>.
--   
--   <pre>
--   map f &lt;x0,...,xn-1&gt; = &lt;f x0,...,f xn-1&gt;
--   </pre>
--   
--   <i>Axioms:</i>
--   
--   <ul>
--   <li><pre>map f empty = empty</pre></li>
--   <li><pre>map f (lcons x xs) = lcons (f x) (map f xs)</pre></li>
--   </ul>
--   
--   This function is always <i>unambiguous</i>.
--   
--   Default running time: <tt>O( t * n )</tt> where <tt>t</tt> is the
--   running time of <tt>f</tt>
map :: Sequence s => (a -> b) -> s a -> s b

-- | Create a singleton sequence. Identical to <tt>return</tt> from
--   <tt>Monad</tt>.
--   
--   <pre>
--   singleton x = &lt;x&gt;
--   </pre>
--   
--   <i>Axioms:</i>
--   
--   <ul>
--   <li><pre>singleton x = lcons x empty = rcons x empty</pre></li>
--   </ul>
--   
--   This function is always <i>unambiguous</i>.
--   
--   Default running time: <tt>O( 1 )</tt>
singleton :: Sequence s => a -> s a

-- | Apply a sequence-producing function to every element of a sequence and
--   flatten the result. <a>concatMap</a> is the bind <tt>(&gt;&gt;=)</tt>
--   operation of from <tt>Monad</tt> with the arguments in the reverse
--   order.
--   
--   <pre>
--   concatMap f xs = concat (map f xs)
--   </pre>
--   
--   <i>Axioms:</i>
--   
--   <ul>
--   <li><pre>concatMap f xs = concat (map f xs)</pre></li>
--   </ul>
--   
--   This function is always <i>unambiguous</i>.
--   
--   Default running time: <tt>O( t * n + m )</tt> where <tt>n</tt> is the
--   length of the input sequence, <tt>m</tt> is the length of the output
--   sequence, and <tt>t</tt> is the running time of <tt>f</tt>
concatMap :: Sequence s => (a -> s b) -> s a -> s b

-- | The empty sequence. Identical to <tt>mzero</tt> from
--   <tt>MonadPlus</tt>.
--   
--   <pre>
--   empty = &lt;&gt;
--   </pre>
--   
--   This function is always <i>unambiguous</i>.
--   
--   Default running time: <tt>O( 1 )</tt>
empty :: Sequence s => s a

-- | Append two sequence, with the first argument on the left and the
--   second argument on the right. Identical to <tt>mplus</tt> from
--   <tt>MonadPlus</tt>.
--   
--   <pre>
--   append &lt;x0,...,xn-1&gt; &lt;y0,...,ym-1&gt; = &lt;x0,...,xn-1,y0,...,ym-1&gt;
--   </pre>
--   
--   <i>Axioms:</i>
--   
--   <ul>
--   <li><pre>append xs ys = foldr lcons ys xs</pre></li>
--   </ul>
--   
--   This function is always <i>unambiguous</i>.
--   
--   Default running time: <tt>O( n1 )</tt>
append :: Sequence s => s a -> s a -> s a

-- | The <a>Sequence</a> class defines an interface for datatypes which
--   implement sequences. A description for each function is given below.
class (Functor s, MonadPlus s) => Sequence s
lcons :: Sequence s => a -> s a -> s a
rcons :: Sequence s => a -> s a -> s a
fromList :: Sequence s => [a] -> s a
copy :: Sequence s => Int -> a -> s a
lview :: (Sequence s, Monad m) => s a -> m (a, s a)
lhead :: Sequence s => s a -> a
lheadM :: (Sequence s, Monad m) => s a -> m a
ltail :: Sequence s => s a -> s a
ltailM :: (Sequence s, Monad m) => s a -> m (s a)
rview :: (Sequence s, Monad m) => s a -> m (a, s a)
rhead :: Sequence s => s a -> a
rheadM :: (Sequence s, Monad m) => s a -> m a
rtail :: Sequence s => s a -> s a
rtailM :: (Sequence s, Monad m) => s a -> m (s a)
null :: Sequence s => s a -> Bool
size :: Sequence s => s a -> Int
toList :: Sequence s => s a -> [a]
concat :: Sequence s => s (s a) -> s a
reverse :: Sequence s => s a -> s a
reverseOnto :: Sequence s => s a -> s a -> s a
fold :: Sequence s => (a -> b -> b) -> b -> s a -> b
fold' :: Sequence s => (a -> b -> b) -> b -> s a -> b
fold1 :: Sequence s => (a -> a -> a) -> s a -> a
fold1' :: Sequence s => (a -> a -> a) -> s a -> a
foldr :: Sequence s => (a -> b -> b) -> b -> s a -> b
foldr' :: Sequence s => (a -> b -> b) -> b -> s a -> b
foldl :: Sequence s => (b -> a -> b) -> b -> s a -> b
foldl' :: Sequence s => (b -> a -> b) -> b -> s a -> b
foldr1 :: Sequence s => (a -> a -> a) -> s a -> a
foldr1' :: Sequence s => (a -> a -> a) -> s a -> a
foldl1 :: Sequence s => (a -> a -> a) -> s a -> a
foldl1' :: Sequence s => (a -> a -> a) -> s a -> a
reducer :: Sequence s => (a -> a -> a) -> a -> s a -> a
reducer' :: Sequence s => (a -> a -> a) -> a -> s a -> a
reducel :: Sequence s => (a -> a -> a) -> a -> s a -> a
reducel' :: Sequence s => (a -> a -> a) -> a -> s a -> a
reduce1 :: Sequence s => (a -> a -> a) -> s a -> a
reduce1' :: Sequence s => (a -> a -> a) -> s a -> a
take :: Sequence s => Int -> s a -> s a
drop :: Sequence s => Int -> s a -> s a
splitAt :: Sequence s => Int -> s a -> (s a, s a)
subseq :: Sequence s => Int -> Int -> s a -> s a
filter :: Sequence s => (a -> Bool) -> s a -> s a
partition :: Sequence s => (a -> Bool) -> s a -> (s a, s a)
takeWhile :: Sequence s => (a -> Bool) -> s a -> s a
dropWhile :: Sequence s => (a -> Bool) -> s a -> s a
splitWhile :: Sequence s => (a -> Bool) -> s a -> (s a, s a)
inBounds :: Sequence s => Int -> s a -> Bool
lookup :: Sequence s => Int -> s a -> a
lookupM :: (Sequence s, Monad m) => Int -> s a -> m a
lookupWithDefault :: Sequence s => a -> Int -> s a -> a
update :: Sequence s => Int -> a -> s a -> s a
adjust :: Sequence s => (a -> a) -> Int -> s a -> s a
mapWithIndex :: Sequence s => (Int -> a -> b) -> s a -> s b
foldrWithIndex :: Sequence s => (Int -> a -> b -> b) -> b -> s a -> b
foldrWithIndex' :: Sequence s => (Int -> a -> b -> b) -> b -> s a -> b
foldlWithIndex :: Sequence s => (b -> Int -> a -> b) -> b -> s a -> b
foldlWithIndex' :: Sequence s => (b -> Int -> a -> b) -> b -> s a -> b
zip :: Sequence s => s a -> s b -> s (a, b)
zip3 :: Sequence s => s a -> s b -> s c -> s (a, b, c)
zipWith :: Sequence s => (a -> b -> c) -> s a -> s b -> s c
zipWith3 :: Sequence s => (a -> b -> c -> d) -> s a -> s b -> s c -> s d
unzip :: Sequence s => s (a, b) -> (s a, s b)
unzip3 :: Sequence s => s (a, b, c) -> (s a, s b, s c)
unzipWith :: Sequence s => (a -> b) -> (a -> c) -> s a -> (s b, s c)
unzipWith3 :: Sequence s => (a -> b) -> (a -> c) -> (a -> d) -> s a -> (s b, s c, s d)
strict :: Sequence s => s a -> s a
strictWith :: Sequence s => (a -> b) -> s a -> s a
structuralInvariant :: Sequence s => s a -> Bool
instanceName :: Sequence s => s a -> String


-- | This module packages the standard prelude list type as a sequence.
--   This is the baseline sequence implementation and all methods have the
--   default running times listed in <a>Data.Edison.Seq</a>, except for the
--   following two trivial operations:
--   
--   <ul>
--   <li>toList, fromList <tt>O( 1 )</tt></li>
--   </ul>
module Data.Edison.Seq.ListSeq
type Seq a = [a]
empty :: [a]
singleton :: a -> [a]
lcons :: a -> [a] -> [a]
rcons :: a -> [a] -> [a]
append :: [a] -> [a] -> [a]
lview :: Monad rm => [a] -> rm (a, [a])
lhead :: [a] -> a
lheadM :: Monad rm => [a] -> rm a
ltail :: [a] -> [a]
ltailM :: Monad rm => [a] -> rm [a]
rview :: Monad rm => [a] -> rm (a, [a])
rhead :: [a] -> a
rheadM :: Monad rm => [a] -> rm a
rtail :: [a] -> [a]
rtailM :: Monad rm => [a] -> rm [a]
null :: [a] -> Bool
size :: [a] -> Int
concat :: [[a]] -> [a]
reverse :: [a] -> [a]
reverseOnto :: [a] -> [a] -> [a]
fromList :: [a] -> [a]
toList :: [a] -> [a]
map :: (a -> b) -> [a] -> [b]
concatMap :: (a -> [b]) -> [a] -> [b]
fold :: (a -> b -> b) -> b -> [a] -> b
fold' :: (a -> b -> b) -> b -> [a] -> b
fold1 :: (a -> a -> a) -> [a] -> a
fold1' :: (a -> a -> a) -> [a] -> a
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr' :: (t -> a -> a) -> a -> [t] -> a
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl' :: (b -> a -> b) -> b -> [a] -> b
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1' :: (a -> a -> a) -> [a] -> a
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1' :: (a -> a -> a) -> [a] -> a
reducer :: (a -> a -> a) -> a -> [a] -> a
reducer' :: (a -> a -> a) -> a -> [a] -> a
reducel :: (a -> a -> a) -> a -> [a] -> a
reducel' :: (a -> a -> a) -> a -> [a] -> a
reduce1 :: (a -> a -> a) -> [a] -> a
reduce1' :: (a -> a -> a) -> [a] -> a
copy :: Int -> a -> [a]
inBounds :: Int -> [a] -> Bool
lookup :: Int -> [a] -> a
lookupM :: Monad m => Int -> [a] -> m a
lookupWithDefault :: a -> Int -> [a] -> a
update :: Int -> a -> [a] -> [a]
adjust :: (a -> a) -> Int -> [a] -> [a]
mapWithIndex :: (Int -> a -> b) -> [a] -> [b]
foldrWithIndex :: (Int -> a -> b -> b) -> b -> [a] -> b
foldrWithIndex' :: (Enum a, Num a) => (a -> t -> b -> b) -> b -> [t] -> b
foldlWithIndex :: (b -> Int -> a -> b) -> b -> [a] -> b
foldlWithIndex' :: (b -> Int -> a -> b) -> b -> [a] -> b
take :: Int -> [a] -> [a]
drop :: Int -> [a] -> [a]
splitAt :: Int -> [a] -> ([a], [a])
subseq :: Int -> Int -> [a] -> [a]
filter :: (a -> Bool) -> [a] -> [a]
partition :: (a -> Bool) -> [a] -> ([a], [a])
takeWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: (a -> Bool) -> [a] -> [a]
splitWhile :: (a -> Bool) -> [a] -> ([a], [a])
zip :: [a] -> [b] -> [(a, b)]
zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
unzip :: [(a, b)] -> ([a], [b])
unzip3 :: [(a, b, c)] -> ([a], [b], [c])
unzipWith :: (a -> b) -> (a -> c) -> [a] -> ([b], [c])
unzipWith3 :: (a -> b) -> (a -> c) -> (a -> d) -> [a] -> ([b], [c], [d])
strict :: [a] -> [a]
strictWith :: (a -> b) -> [a] -> [a]
structuralInvariant :: [a] -> Bool
moduleName :: String
instance Sequence []


-- | The <i>collection</i> 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 <a>CollX</a> together with seven
--   subclasses satisfying one or more of three common sub-properties:
--   
--   <ul>
--   <li><i>Uniqueness</i> Each element in the collection is unique (no two
--   elements in the collection are equal). These subclasses, indicated by
--   the name <tt>Set</tt>, represent sets rather than bags
--   (multi-sets).</li>
--   <li><i>Ordering</i> The elements have a total ordering and it is
--   possible to process the elements in non-decreasing order. These
--   subclasses, indicates by the <tt>Ord</tt> prefix, typically represent
--   either priority queues (heaps) or sets/bags implemented as binary
--   search trees.</li>
--   <li><i>Observability</i> An observable collection is one in which it
--   is possible to view the elements in a collection. The <tt>X</tt>
--   suffix indicates a lack of observability. This property is discussed
--   is greater detail below.</li>
--   </ul>
--   
--   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 <tt>Bag</tt>, <tt>Set</tt>, or <tt>Heap</tt>.
--   
--   <i>Notes on observability</i>
--   
--   Note that the equality relation defined by the <a>Eq</a> 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
--   <i>which</i> three.
--   
--   On the other hand, implementations of <i>non-observable</i>
--   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 <i>which</i> representatives from an equivalence class
--   are actually present. As another example, consider the
--   <a>UniqueHash</a> class defined in <a>Data.Edison.Prelude</a>. If we
--   know that the <a>hash</a> 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 <a>fold</a> or
--   <a>filter</a> that require the elements themselves, rather than the
--   hashed values.
module Data.Edison.Coll

-- | The empty collection. Equivalant to <tt>mempty</tt> from the
--   <tt>Monoid</tt> instance.
--   
--   This function is always <i>unambiguous</i>.
empty :: CollX c a => c

-- | Merge two collections. For sets, it is unspecified which element is
--   kept in the case of duplicates. Equivalant to <tt>mappend</tt> from
--   the <tt>Monoid</tt> instance.
--   
--   This function is <i>ambiguous</i> at set types if the sets are not
--   disjoint. Otherwise it is <i>unambiguous</i>.
union :: CollX c a => c -> c -> c

-- | 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
singleton :: CollX c a => a -> c
fromSeq :: (CollX c a, Sequence seq) => seq a -> c
unionSeq :: (CollX c a, Sequence seq) => seq c -> c
insert :: CollX c a => a -> c -> c
insertSeq :: (CollX c a, Sequence seq) => seq a -> c -> c
delete :: CollX c a => a -> c -> c
deleteAll :: CollX c a => a -> c -> c
deleteSeq :: (CollX c a, Sequence seq) => seq a -> c -> c
null :: CollX c a => c -> Bool
size :: CollX c a => c -> Int
member :: CollX c a => a -> c -> Bool
count :: CollX c a => a -> c -> Int
strict :: CollX c a => c -> c
structuralInvariant :: CollX c a => c -> Bool
instanceName :: CollX c a => c -> String

-- | Collections for which the elements have an ordering relation.
class (CollX c a, Ord a) => OrdCollX c a | c -> a
deleteMin :: OrdCollX c a => c -> c
deleteMax :: OrdCollX c a => c -> c
unsafeInsertMin :: OrdCollX c a => a -> c -> c
unsafeInsertMax :: OrdCollX c a => a -> c -> c
unsafeFromOrdSeq :: (OrdCollX c a, Sequence seq) => seq a -> c
unsafeAppend :: OrdCollX c a => c -> c -> c
filterLT :: OrdCollX c a => a -> c -> c
filterLE :: OrdCollX c a => a -> c -> c
filterGT :: OrdCollX c a => a -> c -> c
filterGE :: OrdCollX c a => a -> c -> c
partitionLT_GE :: OrdCollX c a => a -> c -> (c, c)
partitionLE_GT :: OrdCollX c a => a -> c -> (c, c)
partitionLT_GT :: OrdCollX c a => 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
--   <a>Eq</a> instance on the elements.
class CollX c a => SetX c a | c -> a
intersection :: SetX c a => c -> c -> c
difference :: SetX c a => c -> c -> c
symmetricDifference :: SetX c a => c -> c -> c
properSubset :: SetX c a => c -> c -> Bool
subset :: SetX c a => 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
--   <tt>(OrdCollX c a,SetX c a)</tt>.
class (OrdCollX c a, SetX c a) => OrdSetX c a | c -> a

-- | Collections with observable elements. See the module documentation for
--   comments on observability.
class CollX c a => Coll c a | c -> a
toSeq :: (Coll c a, Sequence seq) => c -> seq a
lookup :: Coll c a => a -> c -> a
lookupM :: (Coll c a, Monad m) => a -> c -> m a
lookupAll :: (Coll c a, Sequence seq) => a -> c -> seq a
lookupWithDefault :: Coll c a => a -> a -> c -> a
fold :: Coll c a => (a -> b -> b) -> b -> c -> b
fold' :: Coll c a => (a -> b -> b) -> b -> c -> b
fold1 :: Coll c a => (a -> a -> a) -> c -> a
fold1' :: Coll c a => (a -> a -> a) -> c -> a
filter :: Coll c a => (a -> Bool) -> c -> c
partition :: Coll c a => (a -> Bool) -> c -> (c, c)
strictWith :: Coll c a => (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
minView :: (OrdColl c a, Monad m) => c -> m (a, c)
minElem :: OrdColl c a => c -> a
maxView :: (OrdColl c a, Monad m) => c -> m (a, c)
maxElem :: OrdColl c a => c -> a
foldr :: OrdColl c a => (a -> b -> b) -> b -> c -> b
foldr' :: OrdColl c a => (a -> b -> b) -> b -> c -> b
foldl :: OrdColl c a => (b -> a -> b) -> b -> c -> b
foldl' :: OrdColl c a => (b -> a -> b) -> b -> c -> b
foldr1 :: OrdColl c a => (a -> a -> a) -> c -> a
foldr1' :: OrdColl c a => (a -> a -> a) -> c -> a
foldl1 :: OrdColl c a => (a -> a -> a) -> c -> a
foldl1' :: OrdColl c a => (a -> a -> a) -> c -> a
toOrdSeq :: (OrdColl c a, Sequence seq) => c -> seq a
unsafeMapMonotonic :: OrdColl c a => (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 <a>Eq</a> instance on the elements.
--   
--   <i>WARNING: Each of the following \"With\" functions is unsafe.</i>
--   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 <tt>x == y == z</tt>, then <tt>fromSeqWith (+)
--   [x,y,z]</tt> equals either <tt>single (x + (y + z))</tt> or <tt>single
--   ((x + y) + z)</tt>
class (Coll c a, SetX c a) => Set c a | c -> a
fromSeqWith :: (Set c a, Sequence seq) => (a -> a -> a) -> seq a -> c
insertWith :: Set c a => (a -> a -> a) -> a -> c -> c
insertSeqWith :: (Set c a, Sequence seq) => (a -> a -> a) -> seq a -> c -> c
unionl :: Set c a => c -> c -> c
unionr :: Set c a => c -> c -> c
unionWith :: Set c a => (a -> a -> a) -> c -> c -> c
unionSeqWith :: (Set c a, Sequence seq) => (a -> a -> a) -> seq (c) -> c
intersectionWith :: Set c a => (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:
--   
--   <pre>
--   (OrdColl c a,Set c a)
--   </pre>
class (OrdColl c a, Set c a) => OrdSet c a | c -> a
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


-- | This module provides implementations of several useful operations that
--   are not included in the collection classes themselves. This is usually
--   because the operation involves transforming a collection into a
--   different type of collection; such operations cannot be typed using
--   the collection classes without significantly complicating them.
--   
--   Be aware that these functions are defined using the external class
--   interfaces and may be less efficient than corresponding, but more
--   restrictively typed, functions in the collection classes.
module Data.Edison.Coll.Utils

-- | Apply a function across all the elements in a collection and transform
--   the collection type.
map :: (Coll cin a, CollX cout b) => (a -> b) -> (cin -> cout)

-- | Map a partial function across all elements of a collection and
--   transform the collection type.
mapPartial :: (Coll cin a, CollX cout b) => (a -> Maybe b) -> (cin -> cout)

-- | Map a monotonic function across all the elements of a collection and
--   transform the collection type. The function is required to satisfy the
--   following precondition:
--   
--   <pre>
--   forall x y. x &lt; y ==&gt; f x &lt; f y
--   </pre>
unsafeMapMonotonic :: (OrdColl cin a, OrdCollX cout b) => (a -> b) -> (cin -> cout)

-- | Map a collection-producing function across all elements of a
--   collection and collect the results together using <a>union</a>.
unionMap :: (Coll cin a, CollX cout b) => (a -> cout) -> (cin -> cout)


-- | The <i>associative collection</i> 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 <a>Functor</a> as a superclass of every
--   associative collection. See <a>Data.Edison.Coll</a> 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
--   <i>unambiguous</i> with respect to the key storage behavior, but that
--   methods which can observe keys are <i>ambiguous</i> with respect to
--   the actual keys returned.
--   
--   In all cases where an operation is ambiguous with respect to the key,
--   the operation is rendered <i>unambiguous</i> if the <tt>Eq</tt>
--   instance on keys corresponds to indistinguisability.
module Data.Edison.Assoc

-- | Apply a function to the elements of every binding in the associative
--   collection. Identical to <tt>fmap</tt> from <tt>Functor</tt>.
--   
--   This function is always <i>unambiguous</i>.
map :: AssocX m k => (a -> b) -> m a -> m b

-- | The root class of the associative collection hierarchy.
class (Eq k, Functor m) => AssocX m k | m -> k
empty :: AssocX m k => m a
singleton :: AssocX m k => k -> a -> m a
fromSeq :: (AssocX m k, Sequence seq) => seq (k, a) -> m a
insert :: AssocX m k => k -> a -> m a -> m a
insertSeq :: (AssocX m k, Sequence seq) => seq (k, a) -> m a -> m a
union :: AssocX m k => m a -> m a -> m a
unionSeq :: (AssocX m k, Sequence seq) => seq (m a) -> m a
delete :: AssocX m k => k -> m a -> m a
deleteAll :: AssocX m k => k -> m a -> m a
deleteSeq :: (AssocX m k, Sequence seq) => seq k -> m a -> m a
null :: AssocX m k => m a -> Bool
size :: AssocX m k => m a -> Int
member :: AssocX m k => k -> m a -> Bool
count :: AssocX m k => k -> m a -> Int
lookup :: AssocX m k => k -> m a -> a
lookupM :: (AssocX m k, Monad rm) => k -> m a -> rm a
lookupAll :: (AssocX m k, Sequence seq) => k -> m a -> seq a
lookupAndDelete :: AssocX m k => k -> m a -> (a, m a)
lookupAndDeleteM :: (AssocX m k, Monad rm) => k -> m a -> rm (a, m a)
lookupAndDeleteAll :: (AssocX m k, Sequence seq) => k -> m a -> (seq a, m a)
lookupWithDefault :: AssocX m k => a -> k -> m a -> a
adjust :: AssocX m k => (a -> a) -> k -> m a -> m a
adjustAll :: AssocX m k => (a -> a) -> k -> m a -> m a
adjustOrInsert :: AssocX m k => (a -> a) -> a -> k -> m a -> m a
adjustAllOrInsert :: AssocX m k => (a -> a) -> a -> k -> m a -> m a
adjustOrDelete :: AssocX m k => (a -> Maybe a) -> k -> m a -> m a
adjustOrDeleteAll :: AssocX m k => (a -> Maybe a) -> k -> m a -> m a
fold :: AssocX m k => (a -> b -> b) -> b -> m a -> b
fold' :: AssocX m k => (a -> b -> b) -> b -> m a -> b
fold1 :: AssocX m k => (a -> a -> a) -> m a -> a
fold1' :: AssocX m k => (a -> a -> a) -> m a -> a
filter :: AssocX m k => (a -> Bool) -> m a -> m a
partition :: AssocX m k => (a -> Bool) -> m a -> (m a, m a)
elements :: (AssocX m k, Sequence seq) => m a -> seq a
strict :: AssocX m k => m a -> m a
strictWith :: AssocX m k => (a -> b) -> m a -> m a
structuralInvariant :: AssocX m k => m a -> Bool
instanceName :: AssocX m k => 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
minView :: (OrdAssocX m k, Monad rm) => m a -> rm (a, m a)
minElem :: OrdAssocX m k => m a -> a
deleteMin :: OrdAssocX m k => m a -> m a
unsafeInsertMin :: OrdAssocX m k => k -> a -> m a -> m a
maxView :: (OrdAssocX m k, Monad rm) => m a -> rm (a, m a)
maxElem :: OrdAssocX m k => m a -> a
deleteMax :: OrdAssocX m k => m a -> m a
unsafeInsertMax :: OrdAssocX m k => k -> a -> m a -> m a
foldr :: OrdAssocX m k => (a -> b -> b) -> b -> m a -> b
foldr' :: OrdAssocX m k => (a -> b -> b) -> b -> m a -> b
foldl :: OrdAssocX m k => (b -> a -> b) -> b -> m a -> b
foldl' :: OrdAssocX m k => (b -> a -> b) -> b -> m a -> b
foldr1 :: OrdAssocX m k => (a -> a -> a) -> m a -> a
foldr1' :: OrdAssocX m k => (a -> a -> a) -> m a -> a
foldl1 :: OrdAssocX m k => (a -> a -> a) -> m a -> a
foldl1' :: OrdAssocX m k => (a -> a -> a) -> m a -> a
unsafeFromOrdSeq :: (OrdAssocX m k, Sequence seq) => seq (k, a) -> m a
unsafeAppend :: OrdAssocX m k => m a -> m a -> m a
filterLT :: OrdAssocX m k => k -> m a -> m a
filterLE :: OrdAssocX m k => k -> m a -> m a
filterGT :: OrdAssocX m k => k -> m a -> m a
filterGE :: OrdAssocX m k => k -> m a -> m a
partitionLT_GE :: OrdAssocX m k => k -> m a -> (m a, m a)
partitionLE_GT :: OrdAssocX m k => k -> m a -> (m a, m a)
partitionLT_GT :: OrdAssocX m k => 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
fromSeqWith :: (FiniteMapX m k, Sequence seq) => (a -> a -> a) -> seq (k, a) -> m a
fromSeqWithKey :: (FiniteMapX m k, Sequence seq) => (k -> a -> a -> a) -> seq (k, a) -> m a
insertWith :: FiniteMapX m k => (a -> a -> a) -> k -> a -> m a -> m a
insertWithKey :: FiniteMapX m k => (k -> a -> a -> a) -> k -> a -> m a -> m a
insertSeqWith :: (FiniteMapX m k, Sequence seq) => (a -> a -> a) -> seq (k, a) -> m a -> m a
insertSeqWithKey :: (FiniteMapX m k, Sequence seq) => (k -> a -> a -> a) -> seq (k, a) -> m a -> m a
unionl :: FiniteMapX m k => m a -> m a -> m a
unionr :: FiniteMapX m k => m a -> m a -> m a
unionWith :: FiniteMapX m k => (a -> a -> a) -> m a -> m a -> m a
unionSeqWith :: (FiniteMapX m k, Sequence seq) => (a -> a -> a) -> seq (m a) -> m a
intersectionWith :: FiniteMapX m k => (a -> b -> c) -> m a -> m b -> m c
difference :: FiniteMapX m k => m a -> m b -> m a
properSubset :: FiniteMapX m k => m a -> m b -> Bool
subset :: FiniteMapX m k => m a -> m b -> Bool
submapBy :: FiniteMapX m k => (a -> a -> Bool) -> m a -> m a -> Bool
properSubmapBy :: FiniteMapX m k => (a -> a -> Bool) -> m a -> m a -> Bool
sameMapBy :: FiniteMapX m k => (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
toSeq :: (Assoc m k, Sequence seq) => m a -> seq (k, a)
keys :: (Assoc m k, Sequence seq) => m a -> seq k
mapWithKey :: Assoc m k => (k -> a -> b) -> m a -> m b
foldWithKey :: Assoc m k => (k -> a -> b -> b) -> b -> m a -> b
foldWithKey' :: Assoc m k => (k -> a -> b -> b) -> b -> m a -> b
filterWithKey :: Assoc m k => (k -> a -> Bool) -> m a -> m a
partitionWithKey :: Assoc m k => (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
minViewWithKey :: (OrdAssoc m k, Monad rm) => m a -> rm ((k, a), m a)
minElemWithKey :: OrdAssoc m k => m a -> (k, a)
maxViewWithKey :: (OrdAssoc m k, Monad rm) => m a -> rm ((k, a), m a)
maxElemWithKey :: OrdAssoc m k => m a -> (k, a)
foldrWithKey :: OrdAssoc m k => (k -> a -> b -> b) -> b -> m a -> b
foldrWithKey' :: OrdAssoc m k => (k -> a -> b -> b) -> b -> m a -> b
foldlWithKey :: OrdAssoc m k => (b -> k -> a -> b) -> b -> m a -> b
foldlWithKey' :: OrdAssoc m k => (b -> k -> a -> b) -> b -> m a -> b
toOrdSeq :: (OrdAssoc m k, Sequence seq) => m a -> seq (k, a)

-- | Finite maps with observable keys.
class (Assoc m k, FiniteMapX m k) => FiniteMap m k | m -> k
unionWithKey :: FiniteMap m k => (k -> a -> a -> a) -> m a -> m a -> m a
unionSeqWithKey :: (FiniteMap m k, Sequence seq) => (k -> a -> a -> a) -> seq (m a) -> m a
intersectionWithKey :: FiniteMap m k => (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

-- | Specialization of <a>submapBy</a> where the comparison function is
--   given by <tt>(==)</tt>.
submap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool

-- | Specialization of <a>properSubmapBy</a> where the comparison function
--   is given by <tt>(==)</tt>.
properSubmap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool

-- | Specialization of <a>sameMapBy</a> where the comparison function is
--   given by <tt>(==)</tt>.
sameMap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool
fromList :: AssocX m k => [(k, a)] -> m a
insertList :: AssocX m k => [(k, a)] -> m a -> m a
unionList :: AssocX m k => [m a] -> m a
deleteList :: AssocX m k => [k] -> m a -> m a
lookupList :: AssocX m k => k -> m a -> [a]
elementsList :: AssocX m k => m a -> [a]
unsafeFromOrdList :: OrdAssocX m k => [(k, a)] -> m a
fromListWith :: FiniteMapX m k => (a -> a -> a) -> [(k, a)] -> m a
fromListWithKey :: FiniteMapX m k => (k -> a -> a -> a) -> [(k, a)] -> m a
insertListWith :: FiniteMapX m k => (a -> a -> a) -> [(k, a)] -> m a -> m a
insertListWithKey :: FiniteMapX m k => (k -> a -> a -> a) -> [(k, a)] -> m a -> m a
unionListWith :: FiniteMapX m k => (a -> a -> a) -> [m a] -> m a
toList :: Assoc m k => m a -> [(k, a)]
keysList :: Assoc m k => m a -> [k]
toOrdList :: OrdAssoc m k => m a -> [(k, a)]
unionListWithKey :: FiniteMap m k => (k -> a -> a -> a) -> [m a] -> m a


-- | This module introduces a number of infix symbols which are aliases for
--   some of the operations in the sequence and set abstractions. For
--   several, the argument orders are reversed to more closely match usual
--   symbolic usage.
--   
--   The symbols are intended to evoke the the operations they represent.
--   Unfortunately, ASCII is pretty limited, and Haskell 98 only allocates
--   a few symbols to the operator lexical class. Thus, some of the
--   operators are less evocative than one would like. A future version of
--   Edison may introduce unicode operators, which will allow a wider range
--   of operations to be represented symbolicly.
--   
--   Unlike most of the modules in Edison, this module is intended to be
--   imported unqualified. However, the definition of <tt>(++)</tt> will
--   conflict with the Prelude definition. Either this definition or the
--   Prelude definition will need to be imported <tt>hiding ( (++) )</tt>.
--   This definition subsumes the Prelude definition, and can be safely
--   used in place of it.
module Data.Edison.Sym

-- | Left (front) cons on a sequence. The new element appears on the left.
--   Identical to <a>lcons</a>.
(<|) :: Sequence seq => a -> seq a -> seq a

-- | Right (rear) cons on a sequence. The new element appears on the right.
--   Identical to <a>rcons</a> with reversed arguments.
(|>) :: Sequence seq => seq a -> a -> seq a

-- | Append two sequences. Identical to <a>append</a>. Subsumes the Prelude
--   definition.
(++) :: Sequence seq => seq a -> seq a -> seq a

-- | Lookup an element in a sequence. Identical to <a>lookup</a> with
--   reversed arguments.
(!) :: Sequence seq => seq a -> Int -> a

-- | Subset test operation. Identical to <a>subset</a>.
(|=) :: SetX set a => set -> set -> Bool

-- | Set difference. Identical to <a>difference</a>.
(\\) :: SetX set a => set -> set -> set

-- | Set intersection. Identical to <a>intersection</a>.
(/\) :: SetX set a => set -> set -> set

-- | Set union. Identical to <a>union</a>.
(\/) :: SetX set a => set -> set -> set


-- | Edison is a library of purely functional data structures written by
--   Chris Okasaki. It is named after Thomas Alva Edison and for the
--   mnemonic value <i>ED</i>i<i>S</i>on (<i>E</i>fficent <i>D</i>ata
--   <i>S</i>tructures).
--   
--   Edison provides several families of abstractions, each with multiple
--   implementations. The main abstractions provided by Edison are:
--   
--   <ul>
--   <li><i>Sequences</i> such as stacks, queues, and dequeues,</li>
--   <li><i>Collections</i> such as sets, bags and heaps, and</li>
--   <li><i>Associative Collections</i> such as finite maps and priority
--   queues where the priority and element are distinct.</li>
--   </ul>
--   
--   <i>Conventions:</i>
--   
--   Each data structure is implemented as a separate module. These modules
--   should always be imported <tt>qualified</tt> to prevent a flood of
--   name clashes, and it is recommended to rename the module using the
--   <tt>as</tt> keyword to reduce the overhead of qualified names and to
--   make substituting one implementation for another as painless as
--   possible.
--   
--   Names have been chosen to match standard usage as much as possible.
--   This means that operations for abstractions frequently share the same
--   name (for example, <tt>empty</tt>, <tt>null</tt>, <tt>size</tt>, etc).
--   It also means that in many cases names have been reused from the
--   Prelude. However, the use of <tt>qualified</tt> imports will prevent
--   name reuse from becoming name clashes. If for some reason you chose to
--   import an Edison data structure unqualified, you will likely need to
--   import the Prelude <tt>hiding</tt> the relevant names.
--   
--   Edison modules also frequently share type names. For example, most
--   sequence type constructors are named <tt>Seq</tt>. This additionally
--   aids substituting implementations by simply importing a different
--   module.
--   
--   Argument orders are selected with the following points in mind:
--   
--   <ul>
--   <li><i>Partial application:</i> arguments more likely to be static
--   usually appear before other arguments in order to facilitate partial
--   application.</li>
--   <li><i>Collection appears last:</i> in all cases where an operation
--   queries a single collection or modifies an existing collection, the
--   collection argument will appear last. This is something of a de facto
--   standard for Haskell datastructure libraries and lends a degree of
--   consistency to the API.</li>
--   <li><i>Most usual order:</i> where an operation represents a
--   well-known mathematical function on more than one datastructure, the
--   arguments are chosen to match the most usual argument order for the
--   function.</li>
--   </ul>
--   
--   <i>Type classes:</i>
--   
--   Each family of abstractions is defined as a set of classes: a main
--   class that every implementation of that abstraction should support and
--   several auxiliary subclasses that an implementation may or may not
--   support. However, not all applications require the power of type
--   classes, so each method is also directly accessible from the
--   implementation module. Thus you can choose to use overloading or not,
--   as appropriate for your particular application.
--   
--   Documentation about the behavior of data structure operations is
--   defined in the modules <a>Data.Edison.Seq</a>, <a>Data.Edison.Coll</a>
--   and <a>Data.Edison.Assoc</a>. Implementations are required to respect
--   the descriptions and axioms found in these modules. In some cases time
--   complexity is also given. Implementations may differ from these time
--   complexities; if so, the differences will be given in the
--   documentation for the individual implementation module.
--   
--   <i>Notes on Eq and Ord instances:</i>
--   
--   Many Edison data structures require <tt>Eq</tt> or <tt>Ord</tt>
--   contexts to define equivalence and total ordering on elements or keys.
--   Edison makes the following assumptions about all such required
--   instances:
--   
--   <ul>
--   <li>An <tt>Eq</tt> instance correctly defines an equivalence relation
--   (but not necessarily structural equality); that is, we assume
--   <tt>(==)</tt> (considered as a relation) is reflexive, symmetric and
--   transitive, but allow that equivalent items may be distinguishable by
--   other means.</li>
--   <li>An <tt>Ord</tt> instance correctly defines a total order which is
--   consistent with the <tt>Eq</tt> instance for that type.</li>
--   </ul>
--   
--   These assumptions correspond to the usual meanings assigned to these
--   classes. If an Edison data structure is used with an <tt>Eq</tt> or
--   <tt>Ord</tt> instance which violates these assumptions, then the
--   behavior of that data structure is undefined.
--   
--   <i>Notes on Read and Show instances:</i>
--   
--   The usual Haskell convention for <tt>Read</tt> and <tt>Show</tt>
--   instances (as championed by the Haskell "deriving" mechanism), is that
--   <tt>show</tt> generates a string which is a valid Haskell expression
--   built up using the data type's data constructors such that, if
--   interpreted as Haskell code, the string would generate an identical
--   data item. Furthermore, the derived <tt>Read</tt> instances are able
--   to parse such strings, such that <tt>(read . show) === id</tt>. So,
--   derived instances of <tt>Read</tt> and <tt>Show</tt> exhibit the
--   following useful properties:
--   
--   <ul>
--   <li><tt>read</tt> and <tt>show</tt> are complementary; that is,
--   <tt>read</tt> is a useful inverse for <tt>show</tt></li>
--   <li><tt>show</tt> generates a string which is legal Haskell code
--   representing the data item</li>
--   </ul>
--   
--   For concrete data types, the deriving mechanism is usually quite
--   sufficient. However, for abstract types the derived <tt>Read</tt>
--   instance may allow users to create data which violates invariants.
--   Furthermore, the strings resulting from <tt>show</tt> reference hidden
--   data constructors which violates good software engineering principles
--   and also cannot be compiled because the constructors are not available
--   outside the defining module.
--   
--   Edison avoids most of these problems and still maintains the above
--   useful properties by doing conversions to and from lists and inserting
--   explicit calls to the list conversion operations. The corresponding
--   <tt>Read</tt> instance strips the list conversion call before parsing
--   the list. In this way, private data constructors are not revealed and
--   <tt>show</tt> strings are still legal, compilable Haskell code.
--   Furthermore, the showed strings gain a degree of independence from the
--   underlying datastructure implementation.
--   
--   For example, calling <tt>show</tt> on an empty Banker's queue will
--   result in the following string:
--   
--   <pre>
--   Data.Edison.Seq.BankersQueue.fromList []
--   </pre>
--   
--   Datatypes which are not native Edison data structures (such as
--   StandardSet and StandardMap) may or may not provide <tt>Read</tt> or
--   <tt>Show</tt> instances and, if they exist, they may or may not also
--   provide the properties that Edison native <tt>Read</tt> and
--   <tt>Show</tt> instances do.
--   
--   <i>Notes on time complexities:</i>
--   
--   Some Edison data structures (only the sequences currently) have
--   detailed time complexity information. Unless otherwise stated, these
--   are amortized time complexities, assuming persistent usage of the
--   datastructure. Much of this data comes from:
--   
--   Martin Holters. <i>Efficent Data Structures in a Lazy Functional
--   Language</i>. Master's Thesis. Chalmers University of Technology,
--   Sweden. 2003.
--   
--   <i>Notes on unsafe functions:</i>
--   
--   There are a number of different notions of what constitutes an unsafe
--   function. In Haskell, a function is generally called "unsafe" if it
--   can subvert type safety or referential integrity, such as
--   <tt>unsafePerformIO</tt> or <tt>unsafeCoerce#</tt>. In Edison,
--   however, we downgrade the meaning of "unsafe" somewhat. An "unsafe"
--   Edison function is one which, if misused, can violate the structural
--   invariants of a data structure. Misusing an Edison "unsafe" function
--   should never cause your runtime to crash or break referential
--   integrity, but it may cause later uses of a data structure to behave
--   in undefined ways. Almost all unsafe functions in Edison are labeled
--   with the <tt>unsafe</tt> prefix. An exception to this rule is the
--   <tt>With</tt> functions in the <a>Set</a> class, which are also unsafe
--   but do not have the prefix. Unsafe functions will have explicit
--   preconditions listed in their documentation.
--   
--   <i>Notes on ambiguous functions:</i>
--   
--   Edison also contains some functions which are labeled "ambiguous".
--   These functions cannot violate the structural invariants of a data
--   structure, but, under some conditions, the result of applying an
--   ambiguous function is not well defined. For ambiguous functions, the
--   result of applying the function may depend on otherwise unobservable
--   internal state of the data structure, such as the actual shape of a
--   balanced tree. For example, the <a>AssocX</a> class contains the
--   <tt>fold</tt> function, which folds over the elements in the
--   collection in an arbitrary order. If the combining function passed to
--   <tt>fold</tt> is not fold-commutative (see below), then the result of
--   the fold will depend on the actual order that elements are presented
--   to the combining function, which is not defined.
--   
--   To aid programmers, each API function is labeled <i>ambiguous</i> or
--   <i>unambiguous</i> in its documentation. If a function is unambiguous
--   only under some circumstances, that will also be explicitly stated.
--   
--   An "unambiguous" operation is one where all correct implementations of
--   the operation will return "indistinguishable" results. For concrete
--   data types, "indistinguishable" means structural equality. An instance
--   of an abstract data type is considered indistinguishable from another
--   if all possible applications of unambiguous operations to both yield
--   indistinguishable results. (Note: this definition is impredicative and
--   rather imprecise. Should it become an issue, I will attempt to develop
--   a better definition. I hope the intent is sufficiently clear).
--   
--   A higher-order unambiguous operation may be rendered ambiguous if
--   passed a "function" which does not respect referential integrity (one
--   containing <tt>unsafePerformIO</tt> for example). Only do something
--   like this if you are 110% sure you know what you are doing, and even
--   then think it over two or three times.
--   
--   <i>How to choose a fold:</i>
--   
--   <i>Folds</i> are an important class of operations on data structures
--   in a functional language; they perform essentially the same role that
--   iterators perform in imperative languages. Edison provides a dizzying
--   array of folds which (hopefully) correspond to all the various ways a
--   programmer might want to fold over a data structure. However, it can
--   be difficult to know which fold to choose for a particular
--   application. In general, you should choose a fold which provides the
--   <i>fewest</i> guarantees necessary for correctness. The folds which
--   have fewer guarantees give data structure implementers more leeway to
--   provide efficient implementations. For example, if you which to fold a
--   commutative, associative function, you should chose <tt>fold</tt>
--   (which does not guarantee an order) over <tt>foldl</tt> or
--   <tt>foldr</tt>, which specify particular orders.
--   
--   Also, if your function is strict in the accumulating argument, you
--   should prefer the strict folds (eg, <tt>fold'</tt>); they will often
--   provide better space behavior. <i>Be aware</i>, however, that the
--   "strict" folds are not <i>necessarily</i> more strict than the
--   "non-strict" folds; they merely give implementers the option to
--   provide additional strictness if it improves performance.
--   
--   For associative collections, only use with <tt>WithKey</tt> folds if
--   you actually need the value of the key.
--   
--   <i>Painfully detailed information about ambiguous folds:</i>
--   
--   All of the folds that are listed ambiguous are ambiguous because they
--   do not or cannot guarantee a stable order with which the folding
--   function will be applied. However, some functions are order
--   insensitive, and the result will be unambiguous regardless of the fold
--   order chosen. Here we formalize this property, which we call "fold
--   commutativity".
--   
--   We say <tt>f :: a -&gt; b -&gt; b</tt> is <i>fold-commutative</i> iff
--   <tt>f</tt> is unambiguous and
--   
--   <pre>
--   forall w, z :: b; m, n :: a
--   
--      w = z ==&gt; f m (f n w) = f n (f m z)
--   </pre>
--   
--   where <tt>=</tt> means indistinguishability.
--   
--   This property is sufficient (but not necessary) to ensure that, for
--   any collection of elements to fold over, folds over all permutations
--   of those elements will generate indistinguishable results. In other
--   words, an ambiguous fold applied to a fold-commutative combining
--   function becomes <i>unambiguous</i>.
--   
--   Some fold combining functions take their arguments in the reverse
--   order. We straightforwardly extend the notion of fold commutativity to
--   such functions by reversing the arguments. More formally, we say <tt>g
--   :: b -&gt; a -&gt; b</tt> is fold commutative iff <tt>flip g :: a
--   -&gt; b -&gt; b</tt> is fold commutative.
--   
--   For folds which take both a key and an element value, we extend the
--   notion of fold commutativity by considering the key and element to be
--   a single, uncurried argument. More formally, we say <tt>g :: k -&gt; a
--   -&gt; b -&gt; b</tt> is fold commutative iff
--   
--   <pre>
--   \(k,x) z -&gt; g k x z :: (k,a) -&gt; b -&gt; b
--   </pre>
--   
--   is fold commutative according to the above definition.
--   
--   Note that for <tt>g :: a -&gt; a -&gt; a</tt>, if <tt>g</tt> is
--   unambiguous, commutative, and associative, then <tt>g</tt> is
--   fold-commutative.
--   
--   Proof:
--   
--   <pre>
--   let w = z, then
--   g m (g n w) = g m (g n z)     g is unambiguous
--               = g (g n z) m     commutative property of g
--               = g n (g z m)     associative property of g
--               = g n (g m z)     commutative property of g
--   </pre>
--   
--   Qed.
--   
--   Thus, many common numeric combining functions, including <tt>(+)</tt>
--   and <tt>(*)</tt> at integral types, are fold commutative and can be
--   safely used with ambiguous folds.
--   
--   <i>Be aware</i> however, that <tt>(+)</tt> and <tt>(*)</tt> at
--   floating point types are only <i>approximately</i> commutative and
--   associative due to rounding errors; using ambiguous folds with these
--   operations may result in subtle differences in the results. As always,
--   be aware of the limitations and numeric properties of floating point
--   representations.
--   
--   <i>About this module:</i>
--   
--   This module re-exports the various data structure abstraction classes,
--   but not their methods. This allows you to write type signatures which
--   have contexts that mention Edison type classes without having to
--   import the appropriate modules <tt>qualified</tt>. The class methods
--   are not exported to avoid name clashes. Obviously, to use the methods
--   of these classes, you will have to import the appropriate modules.
--   This module additionally re-exports the entire
--   <a>Data.Edison.Prelude</a> module.
--   
--   <i>Miscellaneous points:</i>
--   
--   Some implementations export a few extra functions beyond those
--   included in the relevant classes. These are typically operations that
--   are particularly efficient for that implementation, but are not
--   general enough to warrant inclusion in a class.
--   
--   Since qualified infix symbols are fairly ugly, they have been largely
--   avoided. However, the <a>Data.Edison.Sym</a> module defines a number
--   of infix operators which alias the prefix operators; this module is
--   intended to be imported unqualified.
--   
--   Most of the operations on most of the data structures are strict. This
--   is inevitable for data structures with non-trivial invariants. Even
--   given that, however, many of the operations are stricter than
--   necessary. In fact, operations are never deliberately made lazy unless
--   the laziness is required by the algorithm, as can happen with
--   amortized data structures.
--   
--   Note, however, that the various sequence implementations are always
--   lazy in their elements. Similarly, associative collections are always
--   lazy in their elements (but usually strict in their keys).
--   Non-associative collections are usually strict in their elements.
module Data.Edison

-- | The <a>Sequence</a> class defines an interface for datatypes which
--   implement sequences. A description for each function is given below.
class (Functor s, MonadPlus s) => Sequence s

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

-- | Collections for which the elements have an ordering relation.
class (CollX c a, Ord a) => OrdCollX c a | c -> a

-- | A collection where the set property is maintained; that is, a set
--   contains at most one element of the equivalence class formed by the
--   <a>Eq</a> instance on the elements.
class CollX c a => SetX c a | c -> a

-- | Sets where the elements also have an ordering relation. This class
--   contains no methods; it is only an abbreviation for the context
--   <tt>(OrdCollX c a,SetX c a)</tt>.
class (OrdCollX c a, SetX c a) => OrdSetX c a | c -> a

-- | Collections with observable elements. See the module documentation for
--   comments on observability.
class CollX c a => Coll c a | c -> a

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

-- | 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 <a>Eq</a> instance on the elements.
--   
--   <i>WARNING: Each of the following \"With\" functions is unsafe.</i>
--   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 <tt>x == y == z</tt>, then <tt>fromSeqWith (+)
--   [x,y,z]</tt> equals either <tt>single (x + (y + z))</tt> or <tt>single
--   ((x + y) + z)</tt>
class (Coll c a, SetX c a) => Set c a | c -> a

-- | 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:
--   
--   <pre>
--   (OrdColl c a,Set c a)
--   </pre>
class (OrdColl c a, Set c a) => OrdSet c a | c -> a

-- | The root class of the associative collection hierarchy.
class (Eq k, Functor m) => AssocX m k | m -> k

-- | An associative collection where the keys additionally have an ordering
--   relation.
class (AssocX m k, Ord k) => OrdAssocX m k | m -> k

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

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

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

-- | Finite maps with observable keys.
class (Assoc m k, FiniteMapX m k) => FiniteMap m k | m -> k

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