Copyright | 2011 Bryan O'Sullivan |
---|---|

License | BSD-style |

Maintainer | johan.tibell@gmail.com |

Stability | provisional |

Portability | portable |

Safe Haskell | None |

Language | Haskell98 |

A set of *hashable* values. A set cannot contain duplicate items.
A `HashSet`

makes no guarantees as to the order of its elements.

The implementation is based on *hash array mapped trie*. A
`HashSet`

is often faster than other tree-based set types,
especially when value comparison is expensive, as in the case of
strings.

Many operations have a average-case complexity of *O(log n)*. The
implementation uses a large base (i.e. 16) so in practice these
operations are constant time.

- data HashSet a
- empty :: HashSet a
- singleton :: Hashable a => a -> HashSet a
- union :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
- unions :: (Eq a, Hashable a) => [HashSet a] -> HashSet a
- null :: HashSet a -> Bool
- size :: HashSet a -> Int
- member :: (Eq a, Hashable a) => a -> HashSet a -> Bool
- insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a
- delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a
- map :: (Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet b
- difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
- intersection :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
- foldl' :: (a -> b -> a) -> a -> HashSet b -> a
- foldr :: (b -> a -> a) -> a -> HashSet b -> a
- filter :: (a -> Bool) -> HashSet a -> HashSet a
- toList :: HashSet a -> [a]
- fromList :: (Eq a, Hashable a) => [a] -> HashSet a

# Documentation

A set of values. A set cannot contain duplicate values.

Foldable HashSet | |

(Eq a, Hashable a) => IsList (HashSet a) | |

(Hashable a, Eq a) => Eq (HashSet a) | |

(Data a, Eq a, Hashable a) => Data (HashSet a) | |

(Eq a, Hashable a, Read a) => Read (HashSet a) | |

Show a => Show (HashSet a) | |

(Hashable a, Eq a) => Monoid (HashSet a) | |

NFData a => NFData (HashSet a) | |

Typeable (* -> *) HashSet | |

type Item (HashSet a) = a |

# Construction

# Combine

union :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a Source

*O(n+m)* Construct a set containing all elements from both sets.

To obtain good performance, the smaller set must be presented as the first argument.

unions :: (Eq a, Hashable a) => [HashSet a] -> HashSet a Source

Construct a set containing all elements from a list of sets.

# Basic interface

insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a Source

*O(min(n,W))* Add the specified value to this set.

delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a Source

*O(min(n,W))* Remove the specified value from this set if
present.

# Transformations

map :: (Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet b Source

*O(n)* Transform this set by applying a function to every value.
The resulting set may be smaller than the source.

# Difference and intersection

difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a Source

*O(n)* Difference of two sets. Return elements of the first set
not existing in the second.

intersection :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a Source

*O(n)* Intersection of two sets. Return elements present in both
the first set and the second.

# Folds

foldl' :: (a -> b -> a) -> a -> HashSet b -> a Source

*O(n)* Reduce this set by applying a binary operator to all
elements, using the given starting value (typically the
left-identity of the operator). Each application of the operator
is evaluated before before using the result in the next
application. This function is strict in the starting value.

foldr :: (b -> a -> a) -> a -> HashSet b -> a Source

*O(n)* Reduce this set by applying a binary operator to all
elements, using the given starting value (typically the
right-identity of the operator).

# Filter

filter :: (a -> Bool) -> HashSet a -> HashSet a Source

*O(n)* Filter this set by retaining only elements satisfying a
predicate.