Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
Please see the documentation of containers for details.
- data Set a :: * -> *
- null :: Set a -> Bool
- size :: Set a -> Int
- member :: Ord a => a -> Set a -> Bool
- notMember :: Ord a => a -> Set a -> Bool
- isSubsetOf :: Ord a => Set a -> Set a -> Bool
- disjoint :: Ord a => Set a -> Set a -> Bool
- empty :: Set a
- singleton :: a -> Set a
- insert :: Ord a => a -> Set a -> Set a
- delete :: Ord a => a -> Set a -> Set a
- union :: Ord a => Set a -> Set a -> Set a
- unions :: (Foldable f, Ord a) => f (Set a) -> Set a
- difference :: Ord a => Set a -> Set a -> Set a
- intersection :: Ord a => Set a -> Set a -> Set a
- filter :: (a -> Bool) -> Set a -> Set a
- partition :: (a -> Bool) -> Set a -> (Set a, Set a)
- split :: Ord a => a -> Set a -> (Set a, Set a)
- splitMember :: Ord a => a -> Set a -> (Set a, Bool, Set a)
- take :: Int -> Set a -> Set a
- drop :: Int -> Set a -> Set a
- splitAt :: Int -> Set a -> (Set a, Set a)
- map :: Ord b => (a -> b) -> Set a -> Set b
- mapMonotonic :: (a -> b) -> Set a -> Set b
- foldr :: (a -> b -> b) -> b -> Set a -> b
- foldl :: (a -> b -> a) -> a -> Set b -> a
- lookupMin :: Set a -> Maybe a
- lookupMax :: Set a -> Maybe a
- maxView :: Set a -> Maybe (a, Set a)
- minView :: Set a -> Maybe (a, Set a)
- elems :: Set a -> [a]
- toList :: Set a -> [a]
- fromList :: Ord a => [a] -> Set a
- toAscList :: Set a -> [a]
- toDescList :: Set a -> [a]
- fromAscList :: Eq a => [a] -> Set a
- fromDescList :: Eq a => [a] -> Set a
- fromDistinctAscList :: [a] -> Set a
- fromDistinctDescList :: [a] -> Set a
Set type
A set of values a
.
Foldable Set | |
Eq1 Set | Since: 0.5.9 |
Ord1 Set | Since: 0.5.9 |
Show1 Set | Since: 0.5.9 |
Ord a => IsList (Set a) | Since: 0.5.6.2 |
Eq a => Eq (Set a) | |
(Data a, Ord a) => Data (Set a) | |
Ord a => Ord (Set a) | |
(Read a, Ord a) => Read (Set a) | |
Show a => Show (Set a) | |
Ord a => Semigroup (Set a) | Since: 0.5.7 |
Ord a => Monoid (Set a) | |
NFData a => NFData (Set a) | |
type Item (Set a) | |
Operators
Query
isSubsetOf :: Ord a => Set a -> Set a -> Bool #
O(n+m). Is this a subset?
(s1 `isSubsetOf` s2)
tells whether s1
is a subset of s2
.
disjoint :: Ord a => Set a -> Set a -> Bool #
O(n+m). Check whether two sets are disjoint (i.e. their intersection is empty).
disjoint (fromList [2,4,6]) (fromList [1,3]) == True disjoint (fromList [2,4,6,8]) (fromList [2,3,5,7]) == False disjoint (fromList [1,2]) (fromList [1,2,3,4]) == False disjoint (fromList []) (fromList []) == True
Since: 0.5.11
Construction
insert :: Ord a => a -> Set a -> Set a #
O(log n). Insert an element in a set. If the set already contains an element equal to the given value, it is replaced with the new value.
Combine
union :: Ord a => Set a -> Set a -> Set a #
O(m*log(n/m + 1)), m <= n. The union of two sets, preferring the first set when equal elements are encountered.
intersection :: Ord a => Set a -> Set a -> Set a #
O(m*log(n/m + 1)), m <= n. The intersection of two sets. Elements of the result come from the first set, so for example
import qualified Data.Set as S data AB = A | B deriving Show instance Ord AB where compare _ _ = EQ instance Eq AB where _ == _ = True main = print (S.singleton A `S.intersection` S.singleton B, S.singleton B `S.intersection` S.singleton A)
prints (fromList [A],fromList [B])
.
Filter
partition :: (a -> Bool) -> Set a -> (Set a, Set a) #
O(n). Partition the set into two sets, one with all elements that satisfy
the predicate and one with all elements that don't satisfy the predicate.
See also split
.
split :: Ord a => a -> Set a -> (Set a, Set a) #
O(log n). The expression (
) is a pair split
x set(set1,set2)
where set1
comprises the elements of set
less than x
and set2
comprises the elements of set
greater than x
.
splitMember :: Ord a => a -> Set a -> (Set a, Bool, Set a) #
O(log n). Performs a split
but also returns whether the pivot
element was found in the original set.
take :: Int -> Set a -> Set a #
Take a given number of elements in order, beginning with the smallest ones.
take n =fromDistinctAscList
.take
n .toAscList
Since: 0.5.8
drop :: Int -> Set a -> Set a #
Drop a given number of elements in order, beginning with the smallest ones.
drop n =fromDistinctAscList
.drop
n .toAscList
Since: 0.5.8
map :: Ord b => (a -> b) -> Set a -> Set b #
O(n*log n).
is the set obtained by applying map
f sf
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
mapMonotonic :: (a -> b) -> Set a -> Set b #
O(n). The
, but works only when mapMonotonic
f s == map
f sf
is strictly increasing.
The precondition is not checked.
Semi-formally, we have:
and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapMonotonic f s == map f s where ls = toList s
Folds
maxView :: Set a -> Maybe (a, Set a) #
O(log n). Retrieves the maximal key of the set, and the set
stripped of that element, or Nothing
if passed an empty set.
minView :: Set a -> Maybe (a, Set a) #
O(log n). Retrieves the minimal key of the set, and the set
stripped of that element, or Nothing
if passed an empty set.
O(n). An alias of toAscList
. The elements of a set in ascending order.
Subject to list fusion.
fromList :: Ord a => [a] -> Set a #
O(n*log n). Create a set from a list of elements.
If the elements are ordered, a linear-time implementation is used,
with the performance equal to fromDistinctAscList
.
O(n). Convert the set to an ascending list of elements. Subject to list fusion.
toDescList :: Set a -> [a] #
O(n). Convert the set to a descending list of elements. Subject to list fusion.
fromAscList :: Eq a => [a] -> Set a #
O(n). Build a set from an ascending list in linear time. The precondition (input list is ascending) is not checked.
fromDescList :: Eq a => [a] -> Set a #
O(n). Build a set from a descending list in linear time. The precondition (input list is descending) is not checked.
Since: 0.5.8
fromDistinctAscList :: [a] -> Set a #
O(n). Build a set from an ascending list of distinct elements in linear time. The precondition (input list is strictly ascending) is not checked.
fromDistinctDescList :: [a] -> Set a #
O(n). Build a set from a descending list of distinct elements in linear time. The precondition (input list is strictly descending) is not checked.