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 #

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

Instances

Instances details

Foldable HashSet

Instance details

Defined in Data.HashSet.Internal

Methods

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

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

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

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

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

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

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

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

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

toList :: HashSet a -> [a] #

null :: HashSet a -> Bool #

length :: HashSet a -> Int #

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

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

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

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

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

Eq1 HashSet

Instance details

Defined in Data.HashSet.Internal

Methods

liftEq :: (a -> b -> Bool) -> HashSet a -> HashSet b -> Bool #

Ord1 HashSet

Instance details

Defined in Data.HashSet.Internal

Methods

liftCompare :: (a -> b -> Ordering) -> HashSet a -> HashSet b -> Ordering #

Show1 HashSet

Instance details

Defined in Data.HashSet.Internal

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> HashSet a -> ShowS #

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [HashSet a] -> ShowS #

NFData1 HashSet

Since: unordered-containers-0.2.14.0

Instance details

Defined in Data.HashSet.Internal

Methods

liftRnf :: (a -> ()) -> HashSet a -> () #

Hashable1 HashSet

Instance details

Defined in Data.HashSet.Internal

Methods

liftHashWithSalt :: (Int -> a -> Int) -> Int -> HashSet a -> Int #

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 #

liftTyped :: forall (m :: Type -> Type). Quote m => HashSet a -> Code m (HashSet a) #

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

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

toConstr :: HashSet a -> Constr #

dataTypeOf :: HashSet a -> DataType #

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

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

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

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

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

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

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

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

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

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

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

mappend :: HashSet a -> HashSet a -> HashSet a #

mconcat :: [HashSet a] -> HashSet a #

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

sconcat :: NonEmpty (HashSet a) -> HashSet a #

stimes :: Integral b => b -> HashSet a -> HashSet a #

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

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

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

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

Instance details

Defined in Data.HashSet.Internal

Methods

readsPrec :: Int -> ReadS (HashSet a) #

readList :: ReadS [HashSet a] #

readPrec :: ReadPrec (HashSet a) #

readListPrec :: ReadPrec [HashSet a] #

Show a => Show (HashSet a)

Instance details

Defined in Data.HashSet.Internal

Methods

showsPrec :: Int -> HashSet a -> ShowS #

show :: HashSet a -> String #

showList :: [HashSet a] -> ShowS #

NFData a => NFData (HashSet a)

Instance details

Defined in Data.HashSet.Internal

Methods

rnf :: HashSet a -> () #

Eq a => Eq (HashSet a)

Note that, in the presence of hash collisions, equal HashSets 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 #

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

Ord a => Ord (HashSet a)

Instance details

Defined in Data.HashSet.Internal

Methods

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

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

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

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

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

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

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

Hashable a => Hashable (HashSet a)

Instance details

Defined in Data.HashSet.Internal

Methods

hashWithSalt :: Int -> HashSet a -> Int #

hash :: HashSet a -> Int #

type Item (HashSet a)

Instance details

Defined in Data.HashSet.Internal

type Item (HashSet a) = a

Construction

empty :: HashSet a #

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

>>> HashSet.empty
fromList []

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

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

>>> HashSet.singleton 1
fromList [1]

Combine

union :: Eq a => HashSet a -> HashSet a -> HashSet a #

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

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

Basic interface

null :: HashSet a -> Bool #

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

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

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

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

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

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

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

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

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

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

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

Conversions

Lists

toList :: HashSet a -> [a] #

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

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

HashMaps

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

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

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

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

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

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