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:

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

  1. Print the elements of two sets that are in neither, using difference on both sides.
  2. Use Set.toAscList and Set.toDescList on the same set and compare.
  3. Count the distinct words of a sentence with a set and then with a map.
  4. Explain why the duplicate in the input list disappeared and where it went.
  5. Add a room to the visited set and print the set before and after.
  6. 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.

  1. What does a Set a store?

    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.

  2. What does fromList [1, 1, 2] give?

    Answer

    A set with two elements

    A set keeps one copy of each element.

  3. What does Set.difference a b contain?

    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.

  4. 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.

  5. What is the cost of member in a set of n elements?

    Answer

    Logarithmic

    The balanced tree is walked from the root, so the cost follows its height.

  6. 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.

  7. Which operation gives the elements that both sets contain?

    Answer

    intersection

    The intersection keeps only the common elements, as the set program showed.

  8. What order does Set.toList produce?

    Answer

    Ascending order of the elements

    The tree is ordered, so the traversal gives the elements in ascending order.

  9. 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.

  10. What does fromList cost 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