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.
All of these implementations are immutable which means that any update functions do not modify the set that you passed in, they creates a new set. In order to keep the changes you need to assign it 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 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 addional 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.