Data.Set.Unordered.Many

Documentation

newtype UMSet a

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"

Constructors

UMSet

Fields

unUMSet :: [a]

Instances

Functor UMSet

Mergeable UMSet

Eq a => CanBeProperSubset (UMSet a)

Eq a => CanBeSubset (UMSet a)

HasSize (UMSet a)

HasEmpty (UMSet a)

Eq a => HasIntersection (UMSet a)

Eq a => HasDifference (UMSet a)

Eq a => HasUnion (UMSet a)

HasSingleton (UMSet a) a

Operators

(\\) :: Eq a => UMSet a -> UMSet a -> UMSet a

Query

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

O(1)

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)

isSubsetOf :: Eq a => UMSet a -> UMSet a -> Bool

O(n*m)

isProperSubsetOf :: Eq a => UMSet a -> UMSet a -> Bool

O(n*(m^3))

Construction

empty :: UMSet a

O(1)

singleton :: a -> UMSet a

O(1)

insert :: a -> UMSet a -> UMSet a

O(1)

delete :: Eq a => a -> UMSet a -> UMSet a

O(n)

Combine

union :: Eq a => UMSet a -> UMSet a -> UMSet a

O(n)

difference :: Eq a => UMSet a -> UMSet a -> UMSet a

O(n*m)

intersection :: Eq a => UMSet a -> UMSet a -> UMSet a

O(n*(m^4)) - Combines all elements of both

Filter

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

O(n)

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

O(n)

Map

map :: (a -> b) -> UMSet a -> UMSet b

O(n)

mapMaybe :: (a -> Maybe b) -> UMSet a -> UMSet b

O(?)