-- 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.1 -- | 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: -- -- 
--   forall x,y :: a. (x == y) implies (hash x == hash y)
--
class Eq a => Hash a hash :: Hash a => a -> Int -- | This class represents hashable objects where the hash function is -- unique (injective). There are no new methods, just a stronger -- invariant: -- -- 
--   forall x,y :: a. (x == y) iff (hash x == hash y)
--
class Hash a => UniqueHash a -- | This class represents hashable objects where the hash is reversible. -- -- 
--   forall x :: a. unhash (hash x) == x
--
-- -- Note that: -- -- 
--   hash (unhash i) == i
--
-- -- does not necessarily hold because unhash is not necessarily -- defined for all i, only for all i 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 -- Monoid 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: -- -- 
--   class (Functor s, MonadPlus s) => Sequence s
--
-- -- All sequences are also instances of Functor, Monad, and -- MonadPlus. In addition, all sequences are expected to be -- instances of Eq, Show, and Read, although -- this is not enforced. -- -- We follow the naming convention that every module implementing -- sequences defines a type constructor named Seq. -- -- 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: -- -- 
--   <x0,x1,x2...,xn-1>
--
-- -- Such that x0 is at the left (front) of the sequence and -- xn-1 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 fmap from Functor. -- -- 
--   map f <x0,...,xn-1> = <f x0,...,f xn-1>
--
-- -- Axioms: -- -- -- -- This function is always unambiguous. -- -- Default running time: O( t * n ) where t is the -- running time of f map :: Sequence s => (a -> b) -> s a -> s b -- | Create a singleton sequence. Identical to return from -- Monad. -- -- 
--   singleton x = <x>
--
-- -- Axioms: -- -- -- -- This function is always unambiguous. -- -- Default running time: O( 1 ) singleton :: Sequence s => a -> s a -- | Apply a sequence-producing function to every element of a sequence and -- flatten the result. concatMap is the bind (>>=) -- operation of from Monad with the arguments in the reverse -- order. -- -- 
--   concatMap f xs = concat (map f xs)
--
-- -- Axioms: -- -- -- -- This function is always unambiguous. -- -- Default running time: O( t * n + m ) where n is the -- length of the input sequence, m is the length of the output -- sequence, and t is the running time of f concatMap :: Sequence s => (a -> s b) -> s a -> s b -- | The empty sequence. Identical to mzero from -- MonadPlus. -- -- 
--   empty = <>
--
-- -- This function is always unambiguous. -- -- Default running time: O( 1 ) empty :: Sequence s => s a -- | Append two sequence, with the first argument on the left and the -- second argument on the right. Identical to mplus from -- MonadPlus. -- -- 
--   append <x0,...,xn-1> <y0,...,ym-1> = <x0,...,xn-1,y0,...,ym-1>
--
-- -- Axioms: -- -- -- -- This function is always unambiguous. -- -- Default running time: O( n1 ) append :: Sequence s => s a -> s a -> s a -- | The Sequence 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 Data.Edison.Seq, except for the -- following two trivial operations: -- -- 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 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: -- -- -- -- 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 -- | The empty collection. Equivalant to mempty from the -- Monoid instance. -- -- This function is always unambiguous. empty :: CollX c a => c -- | Merge two collections. For sets, it is unspecified which element is -- kept in the case of duplicates. Equivalant 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 -- | 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 -- Eq 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 -- (OrdCollX c a,SetX c a). 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 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 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: -- -- 
--   (OrdColl c a,Set c a)
--
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: -- -- 
--   forall x y. x < y ==> f x < f y
--
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 union. unionMap :: (Coll cin a, CollX cout b) => (a -> cout) -> (cin -> cout) -- | 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 -- | 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 -- | 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 submapBy where the comparison function is -- given by (==). submap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool -- | Specialization of properSubmapBy where the comparison function -- is given by (==). properSubmap :: (Eq a, FiniteMapX m k) => m a -> m a -> Bool -- | Specialization of sameMapBy where the comparison function is -- given by (==). 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 (++) will -- conflict with the Prelude definition. Either this definition or the -- Prelude definition will need to be imported hiding ( (++) ). -- 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 lcons. (<|) :: Sequence seq => a -> seq a -> seq a -- | Right (rear) cons on a sequence. The new element appears on the right. -- Identical to rcons with reversed arguments. (|>) :: Sequence seq => seq a -> a -> seq a -- | Append two sequences. Identical to append. Subsumes the Prelude -- definition. (++) :: Sequence seq => seq a -> seq a -> seq a -- | Lookup an element in a sequence. Identical to lookup with -- reversed arguments. (!) :: Sequence seq => seq a -> Int -> a -- | Subset test operation. Identical to subset. (|=) :: SetX set a => set -> set -> Bool -- | Set difference. Identical to difference. (\\) :: SetX set a => set -> set -> set -- | Set intersection. Identical to intersection. (/\) :: SetX set a => set -> set -> set -- | Set union. Identical to union. (\/) :: 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 EDiSon (Efficent Data -- Structures). -- -- Edison provides several families of abstractions, each with multiple -- implementations. The main abstractions provided by Edison are: -- -- -- -- Conventions: -- -- Each data structure is implemented as a separate module. These modules -- should always be imported qualified to prevent a flood of -- name clashes, and it is recommended to rename the module using the -- as 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, empty, null, size, etc). -- It also means that in many cases names have been reused from the -- Prelude. However, the use of qualified 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 hiding the relevant names. -- -- Edison modules also frequently share type names. For example, most -- sequence type constructors are named Seq. This additionally -- aids substituting implementations by simply importing a different -- module. -- -- Argument orders are selected with the following points in mind: -- -- -- -- Type classes: -- -- 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 Data.Edison.Seq, Data.Edison.Coll -- and Data.Edison.Assoc. 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. -- -- Notes on Eq and Ord instances: -- -- Many Edison data structures require Eq or Ord -- contexts to define equivalence and total ordering on elements or keys. -- Edison makes the following assumptions about all such required -- instances: -- -- -- -- These assumptions correspond to the usual meanings assigned to these -- classes. If an Edison data structure is used with an Eq or -- Ord instance which violates these assumptions, then the -- behavior of that data structure is undefined. -- -- Notes on Read and Show instances: -- -- The usual Haskell convention for Read and Show -- instances (as championed by the Haskell "deriving" mechanism), is that -- show 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 Read instances are able -- to parse such strings, such that (read . show) === id. So, -- derived instances of Read and Show exhibit the -- following useful properties: -- -- -- -- For concrete data types, the deriving mechanism is usually quite -- sufficient. However, for abstract types the derived Read -- instance may allow users to create data which violates invariants. -- Furthermore, the strings resulting from show 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 -- Read instance strips the list conversion call before parsing -- the list. In this way, private data constructors are not revealed and -- show strings are still legal, compilable Haskell code. -- Furthermore, the showed strings gain a degree of independence from the -- underlying datastructure implementation. -- -- For example, calling show on an empty Banker's queue will -- result in the following string: -- -- 
--   Data.Edison.Seq.BankersQueue.fromList []
--
-- -- Datatypes which are not native Edison data structures (such as -- StandardSet and StandardMap) may or may not provide Read or -- Show instances and, if they exist, they may or may not also -- provide the properties that Edison native Read and -- Show instances do. -- -- Notes on time complexities: -- -- 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. Efficent Data Structures in a Lazy Functional -- Language. Master's Thesis. Chalmers University of Technology, -- Sweden. 2003. -- -- Notes on unsafe functions: -- -- 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 -- unsafePerformIO or unsafeCoerce#. 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 unsafe prefix. An exception to this rule is the -- With functions in the Set class, which are also unsafe -- but do not have the prefix. Unsafe functions will have explicit -- preconditions listed in their documentation. -- -- Notes on ambiguous functions: -- -- 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 AssocX class contains the -- fold function, which folds over the elements in the -- collection in an arbitrary order. If the combining function passed to -- fold 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 ambiguous or -- unambiguous 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 unsafePerformIO 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. -- -- How to choose a fold: -- -- Folds 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 -- fewest 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 fold -- (which does not guarantee an order) over foldl or -- foldr, which specify particular orders. -- -- Also, if your function is strict in the accumulating argument, you -- should prefer the strict folds (eg, fold'); they will often -- provide better space behavior. Be aware, however, that the -- "strict" folds are not necessarily 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 WithKey folds if -- you actually need the value of the key. -- -- Painfully detailed information about ambiguous folds: -- -- 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 f :: a -> b -> b is fold-commutative iff -- f is unambiguous and -- -- 
--   forall w, z :: b; m, n :: a
--   
--      w = z ==> f m (f n w) = f n (f m z)
--
-- -- where = 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 unambiguous. -- -- 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 g -- :: b -> a -> b is fold commutative iff flip g :: a -- -> b -> b 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 g :: k -> a -- -> b -> b is fold commutative iff -- -- 
--   \(k,x) z -> g k x z :: (k,a) -> b -> b
--
-- -- is fold commutative according to the above definition. -- -- Note that for g :: a -> a -> a, if g is -- unambiguous, commutative, and associative, then g is -- fold-commutative. -- -- Proof: -- -- 
--   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
--
-- -- Qed. -- -- Thus, many common numeric combining functions, including (+) -- and (*) at integral types, are fold commutative and can be -- safely used with ambiguous folds. -- -- Be aware however, that (+) and (*) at -- floating point types are only approximately 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. -- -- About this module: -- -- 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 qualified. 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 -- Data.Edison.Prelude module. -- -- Miscellaneous points: -- -- 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 Data.Edison.Sym 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 Sequence 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 -- Eq 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 -- (OrdCollX c a,SetX c a). 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 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 -- | 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 -- | 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