-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Various set implementations in Haskell -- -- This also includes overloaded functions for common set operations. See -- Data.Set.Class. @package sets @version 0.0.2 module Data.Set.Ordered.Unique.Finite newtype FiniteSet a FiniteSet :: (Set a, Set a) -> FiniteSet a [unFiniteSet] :: FiniteSet a -> (Set a, Set a) -- | O(n+m) (\\) :: Ord a => FiniteSet a -> FiniteSet a -> FiniteSet a -- | O(1) null :: Eq a => FiniteSet a -> Bool -- | O(1) size :: FiniteSet a -> Int -- | O(log n) member :: Ord a => a -> FiniteSet a -> Bool -- | O(log n) notMember :: Ord a => a -> FiniteSet a -> Bool -- | O(n+m+t1+t2) isSubsetOf :: Ord a => FiniteSet a -> FiniteSet a -> Bool -- | O(n+m+t1+t2) isProperSubsetOf :: Ord a => FiniteSet a -> FiniteSet a -> Bool -- | O(1) empty :: Set a -> FiniteSet a total :: FiniteSet a -> Set a -- | O(1) singleton :: Set a -> a -> FiniteSet a -- | O(log n) insert :: Ord a => a -> FiniteSet a -> FiniteSet a -- | O(log n) delete :: Ord a => a -> FiniteSet a -> FiniteSet a -- | O(n+m) union :: Ord a => FiniteSet a -> FiniteSet a -> FiniteSet a -- | O(n+m) difference :: Ord a => FiniteSet a -> FiniteSet a -> FiniteSet a -- | O(n+m) intersection :: Ord a => FiniteSet a -> FiniteSet a -> FiniteSet a -- | /O(n+t) complement :: Ord a => FiniteSet a -> FiniteSet a -- | O(n) filter :: (a -> Bool) -> FiniteSet a -> FiniteSet a -- | O(n) - Guaranteed to be disjoint partition :: (a -> Bool) -> FiniteSet a -> (FiniteSet a, FiniteSet a) -- | O(n) map :: Ord b => (a -> b) -> FiniteSet a -> FiniteSet b module Data.Set.Ordered.Unique type OUSet = Set -- | Unique, unordered sets. The semantics for "unordering" is based on the -- idea that we will not know what order the elements are in at any -- point, and we are free to re-order elements in any way. module Data.Set.Unordered.Unique -- | Pronounced "Unordered Unique Set" newtype UUSet a UUSet :: [a] -> UUSet a [unUUSet] :: UUSet a -> [a] (\\) :: Eq a => UUSet a -> UUSet a -> UUSet a -- | O(1) null :: Eq a => UUSet a -> Bool -- | O(n) size :: UUSet a -> Int -- | O(n) member :: Eq a => a -> UUSet a -> Bool -- | O(n) notMember :: Eq a => a -> UUSet a -> Bool -- | O(n) lookup :: Eq a => a -> UUSet a -> Maybe a -- | O(n*m) isSubsetOf :: Eq a => UUSet a -> UUSet a -> Bool -- | O(n*(m^2)) isProperSubsetOf :: Eq a => UUSet a -> UUSet a -> Bool -- | O(1) empty :: UUSet a -- | O(1) singleton :: a -> UUSet a -- | O(n) insert :: Eq a => a -> UUSet a -> UUSet a -- | O(n) delete :: Eq a => a -> UUSet a -> UUSet a -- | O(n*m) union :: Eq a => UUSet a -> UUSet a -> UUSet a -- | O(n*m) difference :: Eq a => UUSet a -> UUSet a -> UUSet a -- | O(n*m) intersection :: Eq a => UUSet a -> UUSet a -> UUSet a -- | O(n) filter :: (a -> Bool) -> UUSet a -> UUSet a -- | O(n) - Guaranteed to be disjoint partition :: (a -> Bool) -> UUSet a -> (UUSet a, UUSet a) -- | O(n) map :: (a -> b) -> UUSet a -> UUSet b -- | O(?) mapMaybe :: (a -> Maybe b) -> UUSet a -> UUSet b instance GHC.Base.Functor Data.Set.Unordered.Unique.UUSet instance Data.Mergeable.Mergeable Data.Set.Unordered.Unique.UUSet module Data.Set.Unordered.Many -- | Unordered sets with duplicate elements. The semantics for "unordering" -- is based on the idea that we will not know what order the elements are -- in at any point, and we are free to re-order elements in any way. -- -- Most binary functions are algorithmically heavier on the right -- arguments. -- -- Pronounced "Unordered Many Set" newtype UMSet a UMSet :: [a] -> UMSet a [unUMSet] :: UMSet a -> [a] (\\) :: Eq a => UMSet a -> UMSet a -> UMSet a -- | O(1) null :: Eq a => UMSet a -> Bool -- | O(n) size :: UMSet a -> Int -- | O(n) member :: Eq a => a -> UMSet a -> Bool -- | O(n) notMember :: Eq a => a -> UMSet a -> Bool -- | O(n) lookup :: Eq a => a -> UMSet a -> Maybe a -- | O(n*m) isSubsetOf :: Eq a => UMSet a -> UMSet a -> Bool -- | O(n*(m^3)) isProperSubsetOf :: Eq a => UMSet a -> UMSet a -> Bool -- | O(1) empty :: UMSet a -- | O(1) singleton :: a -> UMSet a -- | O(1) insert :: a -> UMSet a -> UMSet a -- | O(n) delete :: Eq a => a -> UMSet a -> UMSet a -- | O(n) union :: Eq a => UMSet a -> UMSet a -> UMSet a -- | O(n*m) difference :: Eq a => UMSet a -> UMSet a -> UMSet a -- | O(n*(m^4)) - Combines all elements of both intersection :: Eq a => UMSet a -> UMSet a -> UMSet a -- | O(n) filter :: (a -> Bool) -> UMSet a -> UMSet a -- | O(n) partition :: (a -> Bool) -> UMSet a -> (UMSet a, UMSet a) -- | O(n) map :: (a -> b) -> UMSet a -> UMSet b -- | O(?) mapMaybe :: (a -> Maybe b) -> UMSet a -> UMSet b instance GHC.Base.Functor Data.Set.Unordered.Many.UMSet instance Data.Mergeable.Mergeable Data.Set.Unordered.Many.UMSet module Data.Set.Ordered.Many -- | Ordered sets with duplicate elements. newtype OMSet a OMSet :: [a] -> OMSet a [unOMSet] :: OMSet a -> [a] (\\) :: Eq a => OMSet a -> OMSet a -> OMSet a -- | O(1) null :: Eq a => OMSet a -> Bool -- | O(n) size :: OMSet a -> Int -- | O(n) member :: Eq a => a -> OMSet a -> Bool -- | O(n) notMember :: Eq a => a -> OMSet a -> Bool -- | O(n) lookup :: Eq a => a -> OMSet a -> Maybe a -- | O(n*m) isSubsetOf :: Eq a => OMSet a -> OMSet a -> Bool -- | O(n*(m^3)) isProperSubsetOf :: Eq a => OMSet a -> OMSet a -> Bool -- | O(1) empty :: OMSet a -- | O(1) singleton :: a -> OMSet a -- | O(n) insert :: Ord a => a -> OMSet a -> OMSet a -- | O(n) delete :: Eq a => a -> OMSet a -> OMSet a -- | O(n+m) union :: Sorting a => OMSet a -> OMSet a -> OMSet a -- | O(n*m) difference :: Eq a => OMSet a -> OMSet a -> OMSet a -- | O(min(n,m)) - Combines all elements of both intersection :: Ord a => OMSet a -> OMSet a -> OMSet a -- | O(n) filter :: (a -> Bool) -> OMSet a -> OMSet a -- | O(n) partition :: (a -> Bool) -> OMSet a -> (OMSet a, OMSet a) -- | O(n) map :: (a -> b) -> OMSet a -> OMSet b -- | O(?) mapMaybe :: (a -> Maybe b) -> OMSet a -> OMSet b instance GHC.Base.Functor Data.Set.Ordered.Many.OMSet instance Data.Mergeable.Mergeable Data.Set.Ordered.Many.OMSet -- | Convenience operators overloaded for arbitrary use. There are no laws -- associated with these classes, just duck-typed so we don't have to use -- the qualified versions of each function. module Data.Set.Class class HasUnion s union :: HasUnion s => s -> s -> s class HasDifference s difference :: HasDifference s => s -> s -> s class HasIntersection s intersection :: HasIntersection s => s -> s -> s class HasComplement s complement :: HasComplement s => s -> s class HasSingleton s a singleton :: HasSingleton s a => a -> s class HasSingletonWith s k a singletonWith :: HasSingletonWith s k a => k -> a -> s class HasEmpty s empty :: HasEmpty s => s class HasEmptyWith s k emptyWith :: HasEmptyWith s k => k -> s class HasTotal s total :: HasTotal s => s class HasTotalWith s k totalWith :: HasTotalWith s k => k -> s class HasSize s size :: HasSize s => s -> Int class CanBeSubset s isSubsetOf :: CanBeSubset s => s -> s -> Bool class CanBeProperSubset s isProperSubsetOf :: CanBeProperSubset s => s -> s -> Bool newtype Union a Union :: a -> Union a [unUnion] :: Union a -> a newtype Intersection a Intersection :: a -> Intersection a [unIntersection] :: Intersection a -> a instance Data.Set.Class.HasUnion a => Data.Set.Class.HasUnion (Data.Set.Class.Union a) instance Data.Set.Class.HasDifference a => Data.Set.Class.HasDifference (Data.Set.Class.Union a) instance Data.Set.Class.HasIntersection a => Data.Set.Class.HasIntersection (Data.Set.Class.Union a) instance Data.Set.Class.HasComplement a => Data.Set.Class.HasComplement (Data.Set.Class.Union a) instance Data.Set.Class.HasSingleton x a => Data.Set.Class.HasSingleton x (Data.Set.Class.Union a) instance Data.Set.Class.HasSingletonWith k x a => Data.Set.Class.HasSingletonWith k x (Data.Set.Class.Union a) instance Data.Set.Class.HasEmpty a => Data.Set.Class.HasEmpty (Data.Set.Class.Union a) instance Data.Set.Class.HasEmptyWith k a => Data.Set.Class.HasEmptyWith k (Data.Set.Class.Union a) instance Data.Set.Class.HasTotal a => Data.Set.Class.HasTotal (Data.Set.Class.Union a) instance Data.Set.Class.HasTotalWith k a => Data.Set.Class.HasTotalWith k (Data.Set.Class.Union a) instance Data.Set.Class.HasSize a => Data.Set.Class.HasSize (Data.Set.Class.Union a) instance Data.Set.Class.CanBeSubset a => Data.Set.Class.CanBeSubset (Data.Set.Class.Union a) instance Data.Set.Class.CanBeProperSubset a => Data.Set.Class.CanBeProperSubset (Data.Set.Class.Union a) instance Data.Set.Class.HasUnion a => Data.Set.Class.HasUnion (Data.Set.Class.Intersection a) instance Data.Set.Class.HasDifference a => Data.Set.Class.HasDifference (Data.Set.Class.Intersection a) instance Data.Set.Class.HasIntersection a => Data.Set.Class.HasIntersection (Data.Set.Class.Intersection a) instance Data.Set.Class.HasComplement a => Data.Set.Class.HasComplement (Data.Set.Class.Intersection a) instance Data.Set.Class.HasSingleton x a => Data.Set.Class.HasSingleton x (Data.Set.Class.Intersection a) instance Data.Set.Class.HasSingletonWith k x a => Data.Set.Class.HasSingletonWith k x (Data.Set.Class.Intersection a) instance Data.Set.Class.HasEmpty a => Data.Set.Class.HasEmpty (Data.Set.Class.Intersection a) instance Data.Set.Class.HasEmptyWith k a => Data.Set.Class.HasEmptyWith k (Data.Set.Class.Intersection a) instance Data.Set.Class.HasTotal a => Data.Set.Class.HasTotal (Data.Set.Class.Intersection a) instance Data.Set.Class.HasTotalWith k a => Data.Set.Class.HasTotalWith k (Data.Set.Class.Intersection a) instance Data.Set.Class.HasSize a => Data.Set.Class.HasSize (Data.Set.Class.Intersection a) instance Data.Set.Class.CanBeSubset a => Data.Set.Class.CanBeSubset (Data.Set.Class.Intersection a) instance Data.Set.Class.CanBeProperSubset a => Data.Set.Class.CanBeProperSubset (Data.Set.Class.Intersection a) instance Data.Set.Class.HasUnion s => Data.Commutative.Commutative (Data.Set.Class.Union s) instance Data.Set.Class.HasIntersection s => Data.Commutative.Commutative (Data.Set.Class.Intersection s) instance (Data.Set.Class.HasUnion s, Data.Set.Class.HasIntersection s, Data.Set.Class.HasDifference s) => Data.Set.Class.HasXUnion s instance (Data.Commutative.Commutative (Data.Set.Class.Union s), Data.Set.Class.HasEmpty s) => Data.Commutative.CommutativeId (Data.Set.Class.Union s) instance (Data.Commutative.Commutative (Data.Set.Class.Intersection s), Data.Set.Class.HasTotal s) => Data.Commutative.CommutativeId (Data.Set.Class.Intersection s) instance GHC.Classes.Ord a => Data.Set.Class.HasUnion (Data.Set.Base.Set a) instance GHC.Classes.Ord a => Data.Set.Class.HasDifference (Data.Set.Base.Set a) instance GHC.Classes.Ord a => Data.Set.Class.HasIntersection (Data.Set.Base.Set a) instance Data.Set.Class.HasSingleton (Data.Set.Base.Set a) a instance Data.Set.Class.HasEmpty (Data.Set.Base.Set a) instance Data.Set.Class.HasSize (Data.Set.Base.Set a) instance GHC.Classes.Ord a => Data.Set.Class.CanBeSubset (Data.Set.Base.Set a) instance GHC.Classes.Ord a => Data.Set.Class.CanBeProperSubset (Data.Set.Base.Set a) instance GHC.Classes.Ord k => Data.Set.Class.HasUnion (Data.Map.Base.Map k a) instance GHC.Classes.Ord k => Data.Set.Class.HasDifference (Data.Map.Base.Map k a) instance GHC.Classes.Ord k => Data.Set.Class.HasIntersection (Data.Map.Base.Map k a) instance Data.Set.Class.HasSingletonWith (Data.Map.Base.Map k a) k a instance Data.Set.Class.HasEmpty (Data.Map.Base.Map k a) instance Data.Set.Class.HasSize (Data.Map.Base.Map k a) instance (GHC.Classes.Eq k, GHC.Classes.Ord k, GHC.Classes.Eq a) => Data.Set.Class.CanBeSubset (Data.Map.Base.Map k a) instance (GHC.Classes.Eq k, GHC.Classes.Ord k, GHC.Classes.Eq a) => Data.Set.Class.CanBeProperSubset (Data.Map.Base.Map k a) instance Data.Set.Class.HasSingleton [a] a instance Data.Set.Class.HasEmpty [a] instance Data.Set.Class.HasSize [a] instance Data.Set.Class.HasSingleton (Data.Sequence.Seq a) a instance Data.Set.Class.HasEmpty (Data.Sequence.Seq a) instance Data.Set.Class.HasSize (Data.Sequence.Seq a) instance Data.Set.Class.HasUnion Data.IntSet.Base.IntSet instance Data.Set.Class.HasDifference Data.IntSet.Base.IntSet instance Data.Set.Class.HasIntersection Data.IntSet.Base.IntSet instance Data.Set.Class.HasSingleton Data.IntSet.Base.IntSet Data.IntSet.Base.Key instance Data.Set.Class.HasEmpty Data.IntSet.Base.IntSet instance Data.Set.Class.HasSize Data.IntSet.Base.IntSet instance Data.Set.Class.CanBeSubset Data.IntSet.Base.IntSet instance Data.Set.Class.CanBeProperSubset Data.IntSet.Base.IntSet instance Data.Set.Class.HasUnion (Data.IntMap.Base.IntMap a) instance Data.Set.Class.HasDifference (Data.IntMap.Base.IntMap a) instance Data.Set.Class.HasIntersection (Data.IntMap.Base.IntMap a) instance Data.Set.Class.HasSingletonWith (Data.IntMap.Base.IntMap a) Data.IntSet.Base.Key a instance Data.Set.Class.HasEmpty (Data.IntMap.Base.IntMap a) instance Data.Set.Class.HasSize (Data.IntMap.Base.IntMap a) instance GHC.Classes.Eq a => Data.Set.Class.CanBeSubset (Data.IntMap.Base.IntMap a) instance GHC.Classes.Eq a => Data.Set.Class.CanBeProperSubset (Data.IntMap.Base.IntMap a) instance (Data.Hashable.Class.Hashable a, GHC.Classes.Eq a) => Data.Set.Class.HasUnion (Data.HashSet.HashSet a) instance (Data.Hashable.Class.Hashable a, GHC.Classes.Eq a) => Data.Set.Class.HasDifference (Data.HashSet.HashSet a) instance (Data.Hashable.Class.Hashable a, GHC.Classes.Eq a) => Data.Set.Class.HasIntersection (Data.HashSet.HashSet a) instance Data.Hashable.Class.Hashable a => Data.Set.Class.HasSingleton (Data.HashSet.HashSet a) a instance Data.Set.Class.HasEmpty (Data.HashSet.HashSet a) instance Data.Set.Class.HasSize (Data.HashSet.HashSet a) instance (Data.Hashable.Class.Hashable k, GHC.Classes.Eq k) => Data.Set.Class.HasUnion (Data.HashMap.Base.HashMap k a) instance (Data.Hashable.Class.Hashable k, GHC.Classes.Eq k) => Data.Set.Class.HasDifference (Data.HashMap.Base.HashMap k a) instance (Data.Hashable.Class.Hashable k, GHC.Classes.Eq k) => Data.Set.Class.HasIntersection (Data.HashMap.Base.HashMap k a) instance Data.Hashable.Class.Hashable k => Data.Set.Class.HasSingletonWith (Data.HashMap.Base.HashMap k a) k a instance Data.Set.Class.HasEmpty (Data.HashMap.Base.HashMap k a) instance Data.Set.Class.HasSize (Data.HashMap.Base.HashMap k a) instance GHC.Classes.Ord k => Data.Set.Class.HasUnion (Data.SetWith.SetWith k a) instance GHC.Classes.Ord k => Data.Set.Class.HasDifference (Data.SetWith.SetWith k a) instance GHC.Classes.Ord k => Data.Set.Class.HasIntersection (Data.SetWith.SetWith k a) instance GHC.Classes.Ord k => Data.Set.Class.HasSingletonWith (Data.SetWith.SetWith k a) (a -> k) a instance Data.Set.Class.HasEmptyWith (Data.SetWith.SetWith k a) (a -> k) instance Data.Set.Class.HasSize (Data.SetWith.SetWith k a) instance (GHC.Classes.Ord k, GHC.Classes.Eq a) => Data.Set.Class.CanBeSubset (Data.SetWith.SetWith k a) instance (GHC.Classes.Ord k, GHC.Classes.Eq a) => Data.Set.Class.CanBeProperSubset (Data.SetWith.SetWith k a) instance Data.Set.Class.HasUnion (Data.Functor.Contravariant.Predicate a) instance Data.Set.Class.HasDifference (Data.Functor.Contravariant.Predicate a) instance Data.Set.Class.HasIntersection (Data.Functor.Contravariant.Predicate a) instance Data.Set.Class.HasComplement (Data.Functor.Contravariant.Predicate a) instance GHC.Classes.Eq a => Data.Set.Class.HasSingleton (Data.Functor.Contravariant.Predicate a) a instance Data.Set.Class.HasEmpty (Data.Functor.Contravariant.Predicate a) instance Data.Set.Class.HasTotal (Data.Functor.Contravariant.Predicate a) instance Data.Discrimination.Sorting.Sorting a => Data.Set.Class.HasUnion (Data.Set.Ordered.Many.OMSet a) instance GHC.Classes.Eq a => Data.Set.Class.HasDifference (Data.Set.Ordered.Many.OMSet a) instance GHC.Classes.Ord a => Data.Set.Class.HasIntersection (Data.Set.Ordered.Many.OMSet a) instance Data.Set.Class.HasSingleton (Data.Set.Ordered.Many.OMSet a) a instance Data.Set.Class.HasEmpty (Data.Set.Ordered.Many.OMSet a) instance Data.Set.Class.HasSize (Data.Set.Ordered.Many.OMSet a) instance GHC.Classes.Eq a => Data.Set.Class.CanBeSubset (Data.Set.Ordered.Many.OMSet a) instance GHC.Classes.Eq a => Data.Set.Class.CanBeProperSubset (Data.Set.Ordered.Many.OMSet a) instance GHC.Classes.Eq a => Data.Set.Class.HasUnion (Data.Set.Unordered.Many.UMSet a) instance GHC.Classes.Eq a => Data.Set.Class.HasDifference (Data.Set.Unordered.Many.UMSet a) instance GHC.Classes.Eq a => Data.Set.Class.HasIntersection (Data.Set.Unordered.Many.UMSet a) instance Data.Set.Class.HasSingleton (Data.Set.Unordered.Many.UMSet a) a instance Data.Set.Class.HasEmpty (Data.Set.Unordered.Many.UMSet a) instance Data.Set.Class.HasSize (Data.Set.Unordered.Many.UMSet a) instance GHC.Classes.Eq a => Data.Set.Class.CanBeSubset (Data.Set.Unordered.Many.UMSet a) instance GHC.Classes.Eq a => Data.Set.Class.CanBeProperSubset (Data.Set.Unordered.Many.UMSet a) instance GHC.Classes.Eq a => Data.Set.Class.HasUnion (Data.Set.Unordered.Unique.UUSet a) instance GHC.Classes.Eq a => Data.Set.Class.HasDifference (Data.Set.Unordered.Unique.UUSet a) instance GHC.Classes.Eq a => Data.Set.Class.HasIntersection (Data.Set.Unordered.Unique.UUSet a) instance Data.Set.Class.HasSingleton (Data.Set.Unordered.Unique.UUSet a) a instance Data.Set.Class.HasEmpty (Data.Set.Unordered.Unique.UUSet a) instance Data.Set.Class.HasSize (Data.Set.Unordered.Unique.UUSet a) instance GHC.Classes.Eq a => Data.Set.Class.CanBeSubset (Data.Set.Unordered.Unique.UUSet a) instance GHC.Classes.Eq a => Data.Set.Class.CanBeProperSubset (Data.Set.Unordered.Unique.UUSet a) instance GHC.Classes.Ord a => Data.Set.Class.HasUnion (Data.Set.Ordered.Unique.Finite.FiniteSet a) instance GHC.Classes.Ord a => Data.Set.Class.HasDifference (Data.Set.Ordered.Unique.Finite.FiniteSet a) instance GHC.Classes.Ord a => Data.Set.Class.HasIntersection (Data.Set.Ordered.Unique.Finite.FiniteSet a) instance GHC.Classes.Ord a => Data.Set.Class.HasComplement (Data.Set.Ordered.Unique.Finite.FiniteSet a) instance Data.Set.Class.HasSingletonWith (Data.Set.Ordered.Unique.Finite.FiniteSet a) (Data.Set.Base.Set a) a instance Data.Set.Class.HasEmptyWith (Data.Set.Ordered.Unique.Finite.FiniteSet a) (Data.Set.Base.Set a) instance Data.Set.Class.HasTotalWith (Data.Set.Ordered.Unique.Finite.FiniteSet a) (Data.Set.Ordered.Unique.Finite.FiniteSet a) instance Data.Set.Class.HasSize (Data.Set.Ordered.Unique.Finite.FiniteSet a) instance GHC.Classes.Ord a => Data.Set.Class.CanBeSubset (Data.Set.Ordered.Unique.Finite.FiniteSet a) instance GHC.Classes.Ord a => Data.Set.Class.CanBeProperSubset (Data.Set.Ordered.Unique.Finite.FiniteSet a)