Portability | portable |
---|---|

Stability | provisional |

Maintainer | fox@ucw.cz |

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

with elements of the same hash values.
`Data.Set.Set`

e

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.

- data HashSet a
- (\\) :: Ord a => HashSet a -> HashSet a -> HashSet a
- null :: HashSet a -> Bool
- size :: HashSet a -> Int
- member :: (Hashable a, Ord a) => a -> HashSet a -> Bool
- notMember :: (Hashable a, Ord a) => a -> HashSet a -> Bool
- isSubsetOf :: Ord a => HashSet a -> HashSet a -> Bool
- isProperSubsetOf :: Ord a => HashSet a -> HashSet a -> Bool
- empty :: HashSet a
- singleton :: Hashable a => a -> HashSet a
- insert :: (Hashable a, Ord a) => a -> HashSet a -> HashSet a
- delete :: (Hashable a, Ord a) => a -> HashSet a -> HashSet a
- union :: Ord a => HashSet a -> HashSet a -> HashSet a
- unions :: Ord a => [HashSet a] -> HashSet a
- difference :: Ord a => HashSet a -> HashSet a -> HashSet a
- intersection :: Ord a => HashSet a -> HashSet a -> HashSet a
- filter :: Ord a => (a -> Bool) -> HashSet a -> HashSet a
- partition :: Ord a => (a -> Bool) -> HashSet a -> (HashSet a, HashSet a)
- map :: (Hashable b, Ord b) => (a -> b) -> HashSet a -> HashSet b
- fold :: (a -> b -> b) -> b -> HashSet a -> b
- elems :: HashSet a -> [a]
- toList :: HashSet a -> [a]
- fromList :: (Hashable a, Ord a) => [a] -> HashSet a

# Documentation

The abstract type of a `HashSet`

. Its interface is a suitable
subset of `Data.IntSet.IntSet`

.

# Operators

# Query

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

Is the element not a member of the set?

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

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

# Construction

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

# 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

is the set obtained by applying `map`

f s`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.