Data.Set.Ordered.Unique.Finite

Documentation

newtype FiniteSet a

Constructors

FiniteSet

Fields

unFiniteSet :: (Set a, Set a)

Instances

Ord a => CanBeProperSubset (FiniteSet a)

Ord a => CanBeSubset (FiniteSet a)

HasSize (FiniteSet a)

Ord a => HasComplement (FiniteSet a)

Ord a => HasIntersection (FiniteSet a)

Ord a => HasDifference (FiniteSet a)

Ord a => HasUnion (FiniteSet a)

HasTotalWith (FiniteSet a) (FiniteSet a)

HasEmptyWith (FiniteSet a) (Set a)

HasSingletonWith (FiniteSet a) (Set a) a

Operators

(\\) :: Ord a => FiniteSet a -> FiniteSet a -> FiniteSet a

O(n+m)

Query

null :: Eq a => FiniteSet a -> Bool

O(1)

size :: FiniteSet a -> Int

O(1)

member :: Ord a => a -> FiniteSet a -> Bool

O(log n)

notMember :: Ord a => a -> FiniteSet a -> Bool

O(log n)

isSubsetOf :: Ord a => FiniteSet a -> FiniteSet a -> Bool

O(n+m+t1+t2)

isProperSubsetOf :: Ord a => FiniteSet a -> FiniteSet a -> Bool

O(n+m+t1+t2)

Construction

empty :: Set a -> FiniteSet a

O(1)

total :: FiniteSet a -> Set a

singleton :: Set a -> a -> FiniteSet a

O(1)

insert :: Ord a => a -> FiniteSet a -> FiniteSet a

O(log n)

delete :: Ord a => a -> FiniteSet a -> FiniteSet a

O(log n)

Combine

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+m)

complement :: Ord a => FiniteSet a -> FiniteSet a

/O(n+t)

Filter

filter :: (a -> Bool) -> FiniteSet a -> FiniteSet a

O(n)

partition :: (a -> Bool) -> FiniteSet a -> (FiniteSet a, FiniteSet a)

O(n) - Guaranteed to be disjoint

Map

map :: Ord b => (a -> b) -> FiniteSet a -> FiniteSet b

O(n)