Copyright | (c) Milan Straka 2011 |
---|---|

License | BSD-style |

Maintainer | fox@ucw.cz |

Stability | provisional |

Portability | portable |

Safe Haskell | Safe |

Language | Haskell98 |

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

with elements of the same hash values.`Set`

e

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.

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

# Documentation

The abstract type of a `Set`

. Its interface is a suitable
subset of `IntSet`

.

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

# Query

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

Is the element not a member of the set?

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

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

# Construction

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

# 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 #

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

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