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