Data.Set
A set is a map with no values
Data.Set stores keys and nothing else: the element and the key are the same thing. The type is Set a, the elements must be Ord, and the operations mirror the map ones:
fromList :: Ord a => [a] -> Set a
member :: Ord a => a -> Set a -> Bool
union :: Ord a => Set a -> Set a -> Set a
intersection :: Ord a => Set a -> Set a -> Set a
difference :: Ord a => Set a -> Set a -> Set a
A list keeps the order you gave it and the duplicates; a set does neither. The order of a set is the ascending order of its elements, so toList sorts as a side effect. When the question is "have I seen this before", a set is the structure that answers it in logarithmic time.
fromList, member and the operations
module Main (main) where
import qualified Data.Set as Set
main :: IO ()
main = do
let a = Set.fromList [1, 2, 3, 3 :: Int]
b = Set.fromList [3, 4 :: Int]
print a
print (Set.member 2 a)
print (Set.member 9 a)
print (Set.union a b)
print (Set.intersection a b)
print (Set.difference a b)
print (Set.size a)
print (Set.toList a)
ghc -Wall -O1 -o sets sets.hs
./sets
fromList [1,2,3]
True
False
fromList [1,2,3,4]
fromList [3]
fromList [1,2]
3
[1,2,3]
The duplicate 3 in the input list is one element in the set, and the Show instance prints the elements in order. The three set operations are not the same: the union keeps everything, the intersection only what both have, and the difference only what the first has and the second does not. The result of each is a new set and the two inputs are untouched.
A visited set
The classic use is a walk over names that remembers what it has seen. The function returns whether the room was new and the updated set, and a fold carries the set along:
module Main (main) where
import qualified Data.Set as Set
type Visited = Set.Set String
visit :: String -> Visited -> (Bool, Visited)
visit room visited
| Set.member room visited = (False, visited)
| otherwise = (True, Set.insert room visited)
main :: IO ()
main = do
let route = ["hall", "kitchen", "hall", "garden"]
(firsts, final) = foldl step ([], Set.empty) route
step (seen, visited) room =
let (fresh, next) = visit room visited
in (seen ++ [(room, fresh)], next)
print firsts
print (Set.toList final)
ghc -Wall -O1 -o visited visited.hs
./visited
[("hall",True),("kitchen",True),("hall",False),("garden",True)]
["garden","hall","kitchen"]
The second visit to the hall is marked False and the set does not grow, so the final set has three rooms. The order of the pair list follows the route, while the set is in alphabetical order, which is the usual reason to keep both: the list for the report, the set for the membership test.
What a set costs
A set of n elements has the cost of the balanced tree behind it:
- member and insert are logarithmic.
- fromList is n log n, which is the same as sorting the list first.
- union, intersection and difference are linear in the smaller set, because the elements are already in order.
- Set.toList is linear and gives the sorted order, so a set is also the cheapest sort of a list with duplicates.
For a few dozen elements a list with elem is fine and simpler; the set starts to pay from a few hundred, and a HashSet would only be faster with a hashable key type, which this course does not need. The next lesson keeps the same shape but for a value that changes in place: an IORef.
Exercises
- Print the elements of two sets that are in neither, using difference on both sides.
- Use Set.toAscList and Set.toDescList on the same set and compare.
- Count the distinct words of a sentence with a set and then with a map.
- Explain why the duplicate in the input list disappeared and where it went.
- Add a room to the visited set and print the set before and after.
- Decide for a list of one hundred names whether a list or a set is the right structure and say why.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does a
Set astore?Answer
Unique elements in an order given by Ord
A set is a balanced tree of unique elements, and its order is the Ord order.
-
What does
fromList [1, 1, 2]give?Answer
A set with two elements
A set keeps one copy of each element.
-
What does
Set.difference a bcontain?Answer
The elements of a that are not in b
The difference is directed: it removes from the first set the elements of the second.
-
What does this program print?
module Main (main) where import qualified Data.Set as Set main :: IO () main = print (Set.toList (Set.fromList [3, 1, 2, 1 :: Int]))Answer
[1,2,3]
The set removes the duplicate and toList gives the ascending order.
-
What is the cost of
memberin a set of n elements?Answer
Logarithmic
The balanced tree is walked from the root, so the cost follows its height.
-
What does this program print?
module Main (main) where import qualified Data.Set as Set main :: IO () main = print (Set.size (Set.union (Set.fromList [1, 2 :: Int]) (Set.fromList [2, 3])))Answer
3
The union has the elements 1, 2 and 3, and the shared 2 counts once.
-
Which operation gives the elements that both sets contain?
Answer
intersectionThe intersection keeps only the common elements, as the set program showed.
-
What order does
Set.toListproduce?Answer
Ascending order of the elements
The tree is ordered, so the traversal gives the elements in ascending order.
-
Why keep both a list and a set in the visited program?
Answer
The list keeps the route order for the report and the set makes the membership test cheap
Each structure answers a different question: order against membership.
-
What does
fromListcost for a list of n elements?Answer
n log n
Each of the n inserts costs about log n.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev