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
IntSet if you are storing, well…
data Set element = ... data IntSet = ...
Set relies on the element type having instances of the
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
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"]
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"]
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¶
IntSet in a Haskell source file you should always use
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¶
All of these functions that work for
Set will also work for
which has the element type
a specialized to
Int. Anywhere that you
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
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
Set.singleton "containers" > fromList ["containers"] Set.singleton 1 > fromList 
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
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 = ...
These all do the same thing; use
toAscList because its name indicates the
Set.toDescList :: Set a -> [a] Set.toDescList s = ...
toDescList returns a list containing the elements of
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]
Check if an element is in a set (member)¶
Set.member :: Ord a => a -> Set a -> Bool Set.member x s = ...
True if the element
x is in the
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 = ...
True if the set
s is empty,
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
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
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
Unless you’re using an old version of
containers DO NOT use
Set.findMax. They are partial and throw a runtime
error if the set is empty.
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
replacing an existing equal element if it already exists.
Set.insert 100 Set.empty > fromList  Set.insert 0 (Set.fromList [0, 2, 4, 6]) > fromList [0,2,4,6]
Removing an element from a set¶
Set.delete :: Ord a => a -> Set a -> Set a Set.delete x s = ...
delete the element
x from the set
s. If it’s
not a member it leaves the set unchanged.
Set.delete 0 (Set.fromList [0, 2, 4, 6]) > fromList [2,4,6]
Set.union :: Ord a => Set a -> Set a -> Set a Set.union l r = ...
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]
Set.intersection :: Ord a => Set a -> Set a -> Set a Set.intersection l r = ...
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 
Set.difference :: Ord a => Set a -> Set a -> Set a Set.difference l r = ...
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]
Set.isSubsetOf :: Ord a => Set a -> Set a -> Bool Set.isSubsetOf l r = ...
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
The API docs are annotated with the Big-O complexities of each of the set operations. For benchmarks see the haskell-perf/sets page.