hashmap-1.0.0.2: Persistent containers HashMap and HashSet.

Portabilityportable
Stabilityprovisional
Maintainerfox@ucw.cz

Data.HashSet

Contents

Description

Persistent HashSet, which is defined as

   data HashSet e = Data.IntMap.IntMap (Data.Set.Set e)

is an Data.IntMap.IntMap indexed by hash values of elements, containing a set Data.Set.Set e with elements of the same hash values.

The interface of a HashSet is a suitable subset of Data.IntSet.IntSet.

The complexity of operations is determined by the complexities of Data.IntMap.IntMap and Data.Set.Set operations. See the sources of HashSet to see which operations from containers package are used.

Synopsis

Documentation

data HashSet a Source

The abstract type of a HashSet. Its interface is a suitable subset of Data.IntSet.IntSet.

Instances

Typeable1 HashSet 
Eq a => Eq (HashSet a) 
(Hashable a, Ord a, Data a) => Data (HashSet a) 
Ord a => Ord (HashSet a) 
(Hashable a, Ord a, Read a) => Read (HashSet a) 
Show a => Show (HashSet a) 
Ord a => Monoid (HashSet a) 

Operators

(\\) :: Ord a => HashSet a -> HashSet a -> HashSet aSource

Same as difference.

Query

null :: HashSet a -> BoolSource

Is the set empty?

size :: HashSet a -> IntSource

Number of elements in the set.

member :: (Hashable a, Ord a) => a -> HashSet a -> BoolSource

Is the element a member of the set?

notMember :: (Hashable a, Ord a) => a -> HashSet a -> BoolSource

Is the element not a member of the set?

isSubsetOf :: Ord a => HashSet a -> HashSet a -> BoolSource

Is this a subset?

isProperSubsetOf :: Ord a => HashSet a -> HashSet a -> BoolSource

Is this a proper subset? (ie. a subset but not equal).

Construction

empty :: HashSet aSource

The empty set.

singleton :: Hashable a => a -> HashSet aSource

A set of one element.

insert :: (Hashable a, Ord a) => a -> HashSet a -> HashSet aSource

Add a value to the set. When the value is already an element of the set, it is replaced by the new one, ie. insert is left-biased.

delete :: (Hashable a, Ord a) => a -> HashSet a -> HashSet aSource

Delete a value in the set. Returns the original set when the value was not present.

Combine

union :: Ord a => HashSet a -> HashSet a -> HashSet aSource

The union of two sets.

unions :: Ord a => [HashSet a] -> HashSet aSource

The union of a list of sets.

difference :: Ord a => HashSet a -> HashSet a -> HashSet aSource

Difference between two sets.

intersection :: Ord a => HashSet a -> HashSet a -> HashSet aSource

The intersection of two sets.

Filter

filter :: Ord a => (a -> Bool) -> HashSet a -> HashSet aSource

Filter all elements that satisfy some predicate.

partition :: Ord a => (a -> Bool) -> HashSet a -> (HashSet a, HashSet a)Source

Partition the set according to some predicate. The first set contains all elements that satisfy the predicate, the second all elements that fail the predicate.

Map

map :: (Hashable b, Ord b) => (a -> b) -> HashSet a -> HashSet bSource

map f s is the set obtained by applying f to each element of s.

It's worth noting that the size of the result may be smaller if, for some (x,y), x /= y && f x == f y

Fold

fold :: (a -> b -> b) -> b -> HashSet a -> bSource

Fold over the elements of a set in an unspecified order.

Conversion

elems :: HashSet a -> [a]Source

The elements of a set. (For sets, this is equivalent to toList).

toList :: HashSet a -> [a]Source

Convert the set to a list of elements.

fromList :: (Hashable a, Ord a) => [a] -> HashSet aSource

Create a set from a list of elements.