Copyright	(c) Milan Straka 2011
License	BSD-style
Maintainer	fox@ucw.cz
Stability	provisional
Portability	portable
Safe Haskell	Safe
Language	Haskell98

Data.HashSet

Contents

Operators
Query
Construction
Combine
Filter
Map
Fold
Conversion

Description

Persistent Set based on hashing, which is defined as

  data Set e = IntMap (Some e)

is an IntMap indexed by hash values of elements, containing a value of Some e. That contains either one e or a Set e with elements of the same hash values.

The interface of a Set is a suitable subset of IntSet and can be used as a drop-in replacement of Set.

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

Synopsis

Documentation

data Set a Source

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

Instances

Eq a => Eq (Set a) Source
(Hashable a, Ord a, Data a) => Data (Set a) Source
Ord a => Ord (Set a) Source
(Hashable a, Ord a, Read a) => Read (Set a) Source
Show a => Show (Set a) Source
Ord a => Monoid (Set a) Source
NFData a => NFData (Set a) Source

type HashSet a = Set a Source

Deprecated: HashSet is deprecated. Please use Set instead.

The HashSet is a type synonym for Set for backward compatibility. It is deprecated and will be removed in furture releases.

Operators

(\\) :: Ord a => Set a -> Set a -> Set a Source

Same as difference.

Query

null :: Set a -> Bool Source

Is the set empty?

size :: Set a -> Int Source

Number of elements in the set.

member :: (Hashable a, Ord a) => a -> Set a -> Bool Source

Is the element a member of the set?

notMember :: (Hashable a, Ord a) => a -> Set a -> Bool Source

Is the element not a member of the set?

isSubsetOf :: Ord a => Set a -> Set a -> Bool Source

Is this a subset?

isProperSubsetOf :: Ord a => Set a -> Set a -> Bool Source

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

Construction

empty :: Set a Source

The empty set.

singleton :: Hashable a => a -> Set a Source

A set of one element.

insert :: (Hashable a, Ord a) => a -> Set a -> Set a Source

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 -> Set a -> Set a Source

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

Combine

union :: Ord a => Set a -> Set a -> Set a Source

The union of two sets.

unions :: Ord a => [Set a] -> Set a Source

The union of a list of sets.

difference :: Ord a => Set a -> Set a -> Set a Source

Difference between two sets.

intersection :: Ord a => Set a -> Set a -> Set a Source

The intersection of two sets.

Filter

filter :: Ord a => (a -> Bool) -> Set a -> Set a Source

Filter all elements that satisfy some predicate.

partition :: Ord a => (a -> Bool) -> Set a -> (Set a, Set 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) -> Set a -> Set b Source

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 -> Set a -> b Source

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

Conversion

elems :: Set a -> [a] Source

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

toList :: Set a -> [a] Source

Convert the set to a list of elements.

fromList :: (Hashable a, Ord a) => [a] -> Set a Source

Create a set from a list of elements.