# Sets¶

Sets allow you to store *unique*, *ordered* elements, providing efficient
insertion, lookups, deletions, and set operations. There are two implementations
provided by the `containers`

package: Data.Set and
Data.IntSet. Use `IntSet`

if you are storing, well… `Int`

s.

```
data Set element = ...
data IntSet = ...
```

Important

`Set`

relies on the element type having instances of the `Eq`

and
`Ord`

typeclass for its internal representation. These are already defined
for builtin types, and if you are using your own data type you can use the
deriving
mechanism.

Sets are *immutable*. Any function on a set that changes values in the container
actually creates a new set. In order to keep the changes, you need to assign
the result of the operation to a new variable. For example:

```
let s1 = Set.fromList ["a", "b"]
let s2 = Set.delete "a" s1
print s1
> fromList ["a","b"]
print s2
> fromList ["b"]
```

## Short Example¶

The following GHCi session shows some of the basic set functionality:

```
import qualified Data.Set as Set
let dataStructures = Set.fromList ["Set", "Map", "Graph", "Sequence"]
-- Check if "Map" and "Trie" are in the set of data structures.
Set.member "Map" dataStructures
> True
Set.member "Trie" dataStructures
> False
-- Add "Trie" to our original set of data structures.
let moreDataStructures = Set.insert "Trie" dataStructures
Set.member "Trie" moreDataStructures
> True
-- Remove "Graph" from our original set of data structures.
let fewerDataStructures = Set.delete "Graph" dataStructures
Set.toAscList fewerDataStructures
> ["Map","Sequence","Set"]
-- Create a new set and combine it with our original set.
let unorderedDataStructures = Set.fromList ["HashSet", "HashMap"]
Set.union dataStructures unorderedDataStructures
> fromList ["Graph","HashMap","HashSet","Map","Sequence","Set"]
```

Tip

- You can use the `OverloadedLists
- <https://downloads.haskell.org/ghc/latest/docs/users_guide/exts/overloaded_lists.html>`_

extension so you don’t need to write `fromList [1, 2, 3]`

everywhere.
Instead you can just write `[1, 2, 3]`

and if the function is
expecting a set it will be converted automatically! The code here
will continue to use `fromList`

for clarity though.

## Importing Set and IntSet¶

When using `Set`

or `IntSet`

in a Haskell source file you should always use
a `qualified`

import because these modules export names that clash with the
standard Prelude. You can import the type constructor and additional functions
that you care about unqualified.

```
import Data.Set (Set, lookupMin, lookupMax)
import qualified Data.Set as Set
import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet
```

## Common API Functions¶

Tip

All of these functions that work for `Set`

will also work for `IntSet`

,
which has the element type `a`

specialized to `Int`

. Anywhere that you
see `Set Int`

you can replace it with `IntSet`

. This will speed up
most operations tremendously (see Performance) with the exception of
`size`

which is O(1) for `Set`

and O(n) for `IntSet`

.

Note

`fromList [some,list,elements]`

is how a `Set`

is printed.

### Construction and Conversion¶

#### Create an empty set¶

```
Set.empty :: Set a
Set.empty = ...
```

empty creates a set with zero elements.

```
Set.empty
> fromList []
```

#### Create a set with one element (singleton)¶

```
Set.singleton :: a -> Set a
Set.singleton x = ...
```

singleton creates a set with a single element `x`

in
it.

```
Set.singleton "containers"
> fromList ["containers"]
Set.singleton 1
> fromList [1]
```

#### Create a set from a list¶

```
Set.fromList :: Ord a => [a] -> Set a
Set.fromList xs = ...
```

fromList creates a set containing the elements of the
list `xs`

. Since sets don’t contain duplicates, if there are repeated elements
in the list they will only appear once.

```
Set.fromList ["base", "containers", "QuickCheck"]
> fromList ["QuickCheck","base","containers"]
Set.fromList [1, 1, 2, 3, 4, 4, 5, 1]
> fromList [1,2,3,4,5]
```

#### Create a list from a set¶

```
Set.toAscList, Set.toList, Set.elems :: Set a -> [a]
Set.toAscList s = ...
```

toAscList, toList, and
elems return a list containing the elements of the set
`s` in *ascending* order.

Note

These all do the same thing; use `toAscList`

because its name indicates the
ordering.

```
Set.toDescList :: Set a -> [a]
Set.toDescList s = ...
```

toDescList returns a list containing the elements of
the set `s`

in *descending* order.

```
Set.toAscList (Set.fromList [0, 2, 4, 6])
> [0,2,4,6]
Set.toDescList (Set.fromList [0, 2, 4, 6]
> [6,4,2,0]
```

### Querying¶

#### Check if an element is in a set (member)¶

```
Set.member :: Ord a => a -> Set a -> Bool
Set.member x s = ...
```

member returns `True`

if the element `x`

is in the
set `s`

, `False`

otherwise.

```
Set.member 0 Set.empty
> False
Set.member 0 (Set.fromList [0, 2, 4, 6])
> True
```

#### Check if a set is empty¶

```
Set.null :: Set a -> Bool
Set.null s = ...
```

null returns `True`

if the set `s`

is empty,
`False`

otherwise.

```
Set.null Set.empty
> True
Set.null (Set.fromList [0, 2, 4, 6])
> False
```

#### The number of elements in a set¶

```
Set.size :: Set a -> Int
Set.size s = ...
```

size returns the number of elements in the set `s`

.

```
Set.size Set.empty
> 0
Set.size (Set.fromList [0, 2, 4, 6])
> 4
```

#### Find the minimum/maximum element in a set¶

*Since version 0.5.9*

```
lookupMin, lookupMax :: Set a -> Maybe a
lookupMin s = ...
lookupMax s = ...
```

lookupMin returns the minimum, or maximum
respectively, element of the set `s`

, or `Nothing`

if the set is empty.

```
Set.lookupMin Set.empty
> Nothing
Set.lookupMin (Set.fromList [0, 2, 4, 6])
> Just 0
Set.lookupMax (Set.fromList [0, 2, 4, 6])
> Just 6
```

Warning

Unless you’re using an old version of `containers`

**DO NOT** use
`Set.findMin`

or `Set.findMax`

. They are partial and throw a runtime
error if the set is empty.

### Modification¶

#### Adding a new element to a set¶

```
Set.insert :: Ord a => a -> Set a -> Set a
Set.insert x s = ...
```

insert places the element `x`

into the set `s`

,
replacing an existing equal element if it already exists.

```
Set.insert 100 Set.empty
> fromList [100]
Set.insert 0 (Set.fromList [0, 2, 4, 6])
> fromList [0,2,4,6]
```

### Set Operations¶

#### Union¶

```
Set.union :: Ord a => Set a -> Set a -> Set a
Set.union l r = ...
```

union returns a set containing all elements that are
in either of the two sets `l`

or `r`

(set union).

```
Set.union Set.empty (Set.fromList [0, 2, 4, 6])
> fromList [0,2,4,6]
Set.union (Set.fromList [1, 3, 5, 7]) (Set.fromList [0, 2, 4, 6])
> fromList [0,1,2,3,4,5,6,7]
```

#### Intersection¶

```
Set.intersection :: Ord a => Set a -> Set a -> Set a
Set.intersection l r = ...
```

intersection returns a set the elements that are in
both sets `l`

and `r`

(set intersection).

```
Set.intersection Set.empty (Set.fromList [0, 2, 4, 6])
> fromList []
Set.intersection (Set.fromList [1, 3, 5, 7]) (Set.fromList [0, 2, 4, 6])
> fromList []
Set.intersection (Set.singleton 0) (Set.fromList [0, 2, 4, 6])
> fromList [0]
```

#### Difference¶

```
Set.difference :: Ord a => Set a -> Set a -> Set a
Set.difference l r = ...
```

difference returns a set containing the elements that
are in the first set `l`

but not the second set `r`

(set
difference/relative compliment).

```
Set.difference (Set.fromList [0, 2, 4, 6]) Set.empty
> fromList [0,2,4,6]
Set.difference (Set.fromList [0, 2, 4, 6]) (Set.fromList [1, 3, 5, 7])
> fromList [0,2,4,6]
Set.difference (Set.fromList [0, 2, 4, 6]) (Set.singleton 0)
> fromList [2,4,6]
```

#### Subset¶

```
Set.isSubsetOf :: Ord a => Set a -> Set a -> Bool
Set.isSubsetOf l r = ...
```

isSubsetOf returns `True`

if all elements in the
first set `l`

are also in the second set `r`

(subset).

Note

We use infix notation so that it reads nicer. These are back-ticks (`), not single quotes (‘).

```
Set.empty `Set.isSubsetOf` Set.empty
> True
Set.empty `Set.isSubsetOf` (Set.fromList [0, 2, 4, 6])
> True
(Set.singleton 0) `Set.isSubsetOf` (Set.fromList [0, 2, 4, 6])
> True
(Set.singleton 1) `Set.isSubsetOf` (Set.fromList [0, 2, 4, 6])
> False
```

## Serialization¶

The best way to serialize and deserialize sets is to use one of the many libraries which already support serializing sets. binary, cereal, and store are some common libraries that people use.

Tip

If you are writing custom serialization code use fromDistinctAscList (see #405 for more info).

## Performance¶

The API docs are annotated with the Big-*O* complexities of each of the set
operations. For benchmarks see the haskell-perf/sets page.