Precursor.Data.Set

An efficient implementation of sets.

These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.

 import Data.Set (Set)
 import qualified Data.Set as Set

The implementation of Set is based on size balanced binary trees (or trees of bounded balance) as described by:

• Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/.
• J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973.

Bounds for union, intersection, and difference are as given by

• Guy Blelloch, Daniel Ferizovic, and Yihan Sun, "Just Join for Parallel Ordered Sets", https://arxiv.org/abs/1602.02120v3.

Note that the implementation is left-biased -- the elements of a first argument are always preferred to the second, for example in union or insert. Of course, left-biasing can only be observed when equality is an equivalence relation instead of structural equality.

Warning: The size of the set must not exceed maxBound::Int. Violation of this condition is not detected and if the size limit is exceeded, its behaviour is undefined.

Documentation

data Set a :: * -> *

A set of values a.

Instances

Foldable Set

Methods

fold :: Monoid m => Set m -> m

foldMap :: Monoid m => (a -> m) -> Set a -> m

foldr :: (a -> b -> b) -> b -> Set a -> b

foldr' :: (a -> b -> b) -> b -> Set a -> b

foldl :: (b -> a -> b) -> b -> Set a -> b

foldl' :: (b -> a -> b) -> b -> Set a -> b

foldr1 :: (a -> a -> a) -> Set a -> a

foldl1 :: (a -> a -> a) -> Set a -> a

toList :: Set a -> [a]

null :: Set a -> Bool

length :: Set a -> Int

elem :: Eq a => a -> Set a -> Bool

maximum :: Ord a => Set a -> a

minimum :: Ord a => Set a -> a

sum :: Num a => Set a -> a

product :: Num a => Set a -> a

Ord a => IsList (Set a)

Associated Types

type Item (Set a) :: *

Methods

fromList :: [Item (Set a)] -> Set a

fromListN :: Int -> [Item (Set a)] -> Set a

toList :: Set a -> [Item (Set a)]

Eq a => Eq (Set a)

Methods

(==) :: Set a -> Set a -> Bool

(/=) :: Set a -> Set a -> Bool

(Data a, Ord a) => Data (Set a)

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Set a -> c (Set a)

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

toConstr :: Set a -> Constr

dataTypeOf :: Set a -> DataType

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

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

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

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

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

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

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

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

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

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

Ord a => Ord (Set a)

Methods

compare :: Set a -> Set a -> Ordering

(<) :: Set a -> Set a -> Bool

(<=) :: Set a -> Set a -> Bool

(>) :: Set a -> Set a -> Bool

(>=) :: Set a -> Set a -> Bool

max :: Set a -> Set a -> Set a

min :: Set a -> Set a -> Set a

(Read a, Ord a) => Read (Set a)

Methods

readsPrec :: Int -> ReadS (Set a)

readList :: ReadS [Set a]

readPrec :: ReadPrec (Set a)

readListPrec :: ReadPrec [Set a]

Show a => Show (Set a)

Methods

showsPrec :: Int -> Set a -> ShowS

show :: Set a -> String

showList :: [Set a] -> ShowS

Ord a => Semigroup (Set a)

Methods

(<>) :: Set a -> Set a -> Set a

sconcat :: NonEmpty (Set a) -> Set a

stimes :: Integral b => b -> Set a -> Set a

Ord a => Monoid (Set a)

Methods

mempty :: Set a

mappend :: Set a -> Set a -> Set a

mconcat :: [Set a] -> Set a

NFData a => NFData (Set a)

Methods

rnf :: Set a -> ()

type Item (Set a)

type Item (Set a) = a

add :: Ord a => a -> Set a -> Set a

O(log n). Add an element to a set. If the set already contains an element equal to the given value, it is replaced with the new value.

remove :: Ord a => a -> Set a -> Set a

O(log n). Remove an element from a set.

member :: Ord a => a -> Set a -> Bool

O(log n). Is the element in the set?