Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

Please see the documentation of containers for details.

- data IntSet :: *
- type Key = Int
- (\\) :: IntSet -> IntSet -> IntSet
- null :: IntSet -> Bool
- size :: IntSet -> Int
- member :: Key -> IntSet -> Bool
- notMember :: Key -> IntSet -> Bool
- isSubsetOf :: IntSet -> IntSet -> Bool
- isProperSubsetOf :: IntSet -> IntSet -> Bool
- disjoint :: IntSet -> IntSet -> Bool
- empty :: IntSet
- singleton :: Key -> IntSet
- insert :: Key -> IntSet -> IntSet
- delete :: Key -> IntSet -> IntSet
- union :: IntSet -> IntSet -> IntSet
- difference :: IntSet -> IntSet -> IntSet
- intersection :: IntSet -> IntSet -> IntSet
- filter :: (Key -> Bool) -> IntSet -> IntSet
- partition :: (Key -> Bool) -> IntSet -> (IntSet, IntSet)
- split :: Key -> IntSet -> (IntSet, IntSet)
- splitMember :: Key -> IntSet -> (IntSet, Bool, IntSet)
- foldr :: (Key -> b -> b) -> b -> IntSet -> b
- foldl :: (a -> Key -> a) -> a -> IntSet -> a
- foldr' :: (Key -> b -> b) -> b -> IntSet -> b
- foldl' :: (a -> Key -> a) -> a -> IntSet -> a
- fold :: (Key -> b -> b) -> b -> IntSet -> b
- elems :: IntSet -> [Key]
- toList :: IntSet -> [Key]
- fromList :: [Key] -> IntSet
- toAscList :: IntSet -> [Key]
- toDescList :: IntSet -> [Key]

# Set type

A set of integers.

# Operators

# Query

isSubsetOf :: IntSet -> IntSet -> Bool #

*O(n+m)*. Is this a subset?
`(s1 `isSubsetOf` s2)`

tells whether `s1`

is a subset of `s2`

.

isProperSubsetOf :: IntSet -> IntSet -> Bool #

*O(n+m)*. Is this a proper subset? (ie. a subset but not equal).

disjoint :: IntSet -> IntSet -> 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 :: Key -> IntSet -> IntSet #

*O(min(n,W))*. Add a value to the set. There is no left- or right bias for
IntSets.

delete :: Key -> IntSet -> IntSet #

*O(min(n,W))*. Delete a value in the set. Returns the
original set when the value was not present.

# Combine

difference :: IntSet -> IntSet -> IntSet #

*O(n+m)*. Difference between two sets.

intersection :: IntSet -> IntSet -> IntSet #

*O(n+m)*. The intersection of two sets.

# Filter

partition :: (Key -> Bool) -> IntSet -> (IntSet, IntSet) #

*O(n)*. partition the set according to some predicate.

split :: Key -> IntSet -> (IntSet, IntSet) #

*O(min(n,W))*. 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`

.

split 3 (fromList [1..5]) == (fromList [1,2], fromList [4,5])

splitMember :: Key -> IntSet -> (IntSet, Bool, IntSet) #

*O(min(n,W))*. Performs a `split`

but also returns whether the pivot
element was found in the original set.

# Map

# Folds

## Strict folds

foldr' :: (Key -> b -> b) -> b -> IntSet -> b #

*O(n)*. A strict version of `foldr`

. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.

foldl' :: (a -> Key -> a) -> a -> IntSet -> a #

*O(n)*. A strict version of `foldl`

. Each application of the operator is
evaluated before using the result in the next application. This
function is strict in the starting value.

## Legacy folds

fold :: (Key -> b -> b) -> b -> IntSet -> b #

*O(n)*. Fold the elements in the set using the given right-associative
binary operator. This function is an equivalent of `foldr`

and is present
for compatibility only.

*Please note that fold will be deprecated in the future and removed.*

# Conversion

## List

*O(n)*. An alias of `toAscList`

. The elements of a set in ascending order.
Subject to list fusion.

## Ordered list

toAscList :: IntSet -> [Key] #

*O(n)*. Convert the set to an ascending list of elements. Subject to list
fusion.

toDescList :: IntSet -> [Key] #

*O(n)*. Convert the set to a descending list of elements. Subject to list
fusion.