rio-0.1.24.0: A standard library for Haskell

Safe Haskell | Safe-Inferred
Language | Haskell2010

RIO.HashSet

Contents

- Construction
- Combine
- Basic interface
- Transformations
- Difference and intersection
- Folds
- Filter
- Conversions
  - Lists
- HashMaps

Description

`Set` with hashed members. Import as:

    import qualified RIO.HashSet as HS

Synopsis

- data HashSet a
- empty :: HashSet a
- singleton :: Hashable a => a -> HashSet a
- union :: Eq a => HashSet a -> HashSet a -> HashSet a
- unions :: Eq 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 => 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
- toMap :: HashSet a -> HashMap a ()
- fromMap :: HashMap a () -> HashSet a

# Documentation

data HashSet a Source #

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

#### Instances

Instances details

Eq1 HashSet |
Instance details Defined in Data.HashSet.Internal Methods liftEq :: (a -> b -> Bool) -> HashSet a -> HashSet b -> Bool Source #
Ord1 HashSet |
Instance details Defined in Data.HashSet.Internal Methods liftCompare :: (a -> b -> Ordering) -> HashSet a -> HashSet b -> Ordering Source #
Show1 HashSet |
Instance details Defined in Data.HashSet.Internal Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> HashSet a -> ShowS Source # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [HashSet a] -> ShowS Source #
NFData1 HashSet | Since: unordered-containers-0.2.14.0
Instance details Defined in Data.HashSet.Internal Methods liftRnf :: (a -> ()) -> HashSet a -> () Source #
Foldable HashSet |

Instance details

Defined in Data.HashSet.Internal

Methods

fold :: Monoid m => HashSet m -> m Source #

foldMap :: Monoid m => (a -> m) -> HashSet a -> m Source #

foldMap' :: Monoid m => (a -> m) -> HashSet a -> m Source #

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

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

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

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

foldr1 :: (a -> a -> a) -> HashSet a -> a Source #

foldl1 :: (a -> a -> a) -> HashSet a -> a Source #

toList :: HashSet a -> [a] Source #

null :: HashSet a -> Bool Source #

length :: HashSet a -> Int Source #

elem :: Eq a => a -> HashSet a -> Bool Source #

maximum :: Ord a => HashSet a -> a Source #

minimum :: Ord a => HashSet a -> a Source #

sum :: Num a => HashSet a -> a Source #

product :: Num a => HashSet a -> a Source #

Hashable1 HashSet |
Instance details Defined in Data.HashSet.Internal Methods liftHashWithSalt :: (Int -> a -> Int) -> Int -> HashSet a -> Int Source #
Lift a => Lift (HashSet a :: Type) | Since: unordered-containers-0.2.17.0
Instance details Defined in Data.HashSet.Internal Methods lift :: Quote m => HashSet a -> m Exp Source # liftTyped :: forall (m :: Type -> Type). Quote m => HashSet a -> Code m (HashSet a) Source #
NFData a => NFData (HashSet a) |
Instance details Defined in Data.HashSet.Internal Methods rnf :: HashSet a -> () Source #

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

`mempty` = `empty`

`mappend` = `union`

\(O(n+m)\)

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

#### Examples

Expand

    >>> mappend (fromList [1,2]) (fromList [2,3])
    fromList [1,2,3]

Instance details Defined in Data.HashSet.Internal Methods mempty :: HashSet a Source # mappend :: HashSet a -> HashSet a -> HashSet a Source # mconcat :: [HashSet a] -> HashSet a Source #

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

`<>` = `union`

\(O(n+m)\)

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

#### Examples

Expand

    >>> fromList [1,2] <> fromList [2,3]
    fromList [1,2,3]

Instance details Defined in Data.HashSet.Internal Methods (<>) :: HashSet a -> HashSet a -> HashSet a Source # sconcat :: NonEmpty (HashSet a) -> HashSet a Source # stimes :: Integral b => b -> HashSet a -> HashSet a Source #
(Data a, Eq a, Hashable a) => Data (HashSet a) |

Instance details

Defined in Data.HashSet.Internal

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> HashSet a -> c (HashSet a) Source #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (HashSet a) Source #

toConstr :: HashSet a -> Constr Source #

dataTypeOf :: HashSet a -> DataType Source #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (HashSet a)) Source #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (HashSet a)) Source #

gmapT :: (forall b. Data b => b -> b) -> HashSet a -> HashSet a Source #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> HashSet a -> r Source #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> HashSet a -> r Source #

gmapQ :: (forall d. Data d => d -> u) -> HashSet a -> [u] Source #

gmapQi :: Int -> (forall d. Data d => d -> u) -> HashSet a -> u Source #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a) Source #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a) Source #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> HashSet a -> m (HashSet a) Source #

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

Instance details

Defined in Data.HashSet.Internal

Associated Types

type Item (HashSet a) |
Instance details Defined in Data.HashSet.Internal type Item (HashSet a) = a

Methods

fromList :: [Item (HashSet a)] -> HashSet a Source #

fromListN :: Int -> [Item (HashSet a)] -> HashSet a Source #

toList :: HashSet a -> [Item (HashSet a)] Source #

(Eq a, Hashable a, Read a) => Read (HashSet a) |
Instance details Defined in Data.HashSet.Internal Methods readsPrec :: Int -> ReadS (HashSet a) Source # readList :: ReadS [HashSet a] Source # readPrec :: ReadPrec (HashSet a) Source # readListPrec :: ReadPrec [HashSet a] Source #
Show a => Show (HashSet a) |
Instance details Defined in Data.HashSet.Internal Methods showsPrec :: Int -> HashSet a -> ShowS Source # show :: HashSet a -> String Source # showList :: [HashSet a] -> ShowS Source #

Eq a => Eq (HashSet a)

Note that, in the presence of hash collisions, equal `HashSet`s may behave differently, i.e. extensionality may be violated:

    >>> data D = A | B deriving (Eq, Show)
    >>> instance Hashable D where hashWithSalt salt _d = salt

    >>> x = fromList [A, B]
    >>> y = fromList [B, A]

    >>> x == y
    True
    >>> toList x
    [A,B]
    >>> toList y
    [B,A]

In general, the lack of extensionality can be observed with any function that depends on the key ordering, such as folds and traversals.

Instance details Defined in Data.HashSet.Internal Methods (==) :: HashSet a -> HashSet a -> Bool Source # (/=) :: HashSet a -> HashSet a -> Bool Source #
Ord a => Ord (HashSet a) |

Instance details

Defined in Data.HashSet.Internal

Methods

compare :: HashSet a -> HashSet a -> Ordering Source #

(<) :: HashSet a -> HashSet a -> Bool Source #

(<=) :: HashSet a -> HashSet a -> Bool Source #

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

(>=) :: HashSet a -> HashSet a -> Bool Source #

max :: HashSet a -> HashSet a -> HashSet a Source #

min :: HashSet a -> HashSet a -> HashSet a Source #

Hashable a => Hashable (HashSet a) |
Instance details Defined in Data.HashSet.Internal Methods hashWithSalt :: Int -> HashSet a -> Int Source # hash :: HashSet a -> Int Source #
type Item (HashSet a) |
Instance details Defined in Data.HashSet.Internal type Item (HashSet a) = a

# Construction

empty :: HashSet a Source #

\(O(1)\) Construct an empty set.

    >>> HashSet.empty
    fromList []

singleton :: Hashable a => a -> HashSet a Source #

\(O(1)\) Construct a set with a single element.

    >>> HashSet.singleton 1
    fromList [1]

# Combine

union :: Eq 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.

    >>> union (fromList [1,2]) (fromList [2,3])
    fromList [1,2,3]

unions :: Eq a => [HashSet a] -> HashSet a Source #

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

# Basic interface

null :: HashSet a -> Bool Source #

\(O(1)\) Return `True` if this set is empty, `False` otherwise.

    >>> HashSet.null HashSet.empty
    True
    >>> HashSet.null (HashSet.singleton 1)
    False

size :: HashSet a -> Int Source #

\(O(n)\) Return the number of elements in this set.

    >>> HashSet.size HashSet.empty
    0
    >>> HashSet.size (HashSet.fromList [1,2,3])
    3

member :: (Eq a, Hashable a) => a -> HashSet a -> Bool Source #

\(O(\log n)\) Return `True` if the given value is present in this set, `False` otherwise.

    >>> HashSet.member 1 (Hashset.fromList [1,2,3])
    True
    >>> HashSet.member 1 (Hashset.fromList [4,5,6])
    False

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

\(O(\log n)\) Add the specified value to this set.

    >>> HashSet.insert 1 HashSet.empty
    fromList [1]

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

\(O(\log n)\) Remove the specified value from this set if present.

    >>> HashSet.delete 1 (HashSet.fromList [1,2,3])
    fromList [2,3]
    >>> HashSet.delete 1 (HashSet.fromList [4,5,6])
    fromList [4,5,6]

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

    >>> HashSet.map show (HashSet.fromList [1,2,3])
    HashSet.fromList ["1","2","3"]

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

    >>> HashSet.difference (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])
    fromList [1]

intersection :: Eq 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.

    >>> HashSet.intersection (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])
    fromList [2,3]

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

# Conversions

## Lists

toList :: HashSet a -> [a] Source #

\(O(n)\) Return a list of this set's elements. The list is produced lazily. The order of its elements is unspecified, and it may change from version to version of either this package or of `hashable`.

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

\(O(n \min(W, n))\) Construct a set from a list of elements.

# HashMaps

toMap :: HashSet a -> HashMap a () Source #

\(O(1)\) Convert to set to the equivalent `HashMap` with `()` values.

    >>> HashSet.toMap (HashSet.singleton 1)
    fromList [(1,())]

fromMap :: HashMap a () -> HashSet a Source #

\(O(1)\) Convert from the equivalent `HashMap` with `()` values.

    >>> HashSet.fromMap (HashMap.singleton 1 ())
    fromList [1]