Learn With Me: Elixir - Sets (#20)

Sets are unordered collections of data where a data element can only occur once. These are sets in the sense of sets from set theory.

I've found that sets can occasionally be useful. If I want to know whether I've already visited a node in a graph or already processed a particular piece of data, I can see if it is in the set of data I've already visited or processed. They're also really useful for intersection and difference operations.

Sets are common in other languages as well. Javascript has a Set data type as of ES2015 and C# has a HashSet<T> class with set functionality.

Elixir Sets

In Elixir, a set can contain elements of any type. Elixir stores sets internally using the %MapSet{} struct. Functions that manipulate a set are located in the MapSet module.

Let's try it out.

iex> salad_ingredients = MapSet.new()
#MapSet<[]>
iex> MapSet.put(salad_ingredients, "lettuce")
#MapSet<["lettuce"]>
iex> MapSet.put(salad_ingredients, "cucumbers")
#MapSet<["cucumbers"]>
iex> salad_ingredients = MapSet.put(salad_ingredients, "lettuce")
#MapSet<["lettuce"]>
iex> salad_ingredients = MapSet.put(salad_ingredients, "cucumbers")
#MapSet<["cucumbers", "lettuce"]>
iex> salad_ingredients = MapSet.put(salad_ingredients, "tomatoes")
#MapSet<["cucumbers", "lettuce", "tomatoes"]>
iex> salad_ingredients = MapSet.put(salad_ingredients, "cucumbers")
#MapSet<["cucumbers", "lettuce", "tomatoes"]>
iex> MapSet.member?(salad_ingredients, "cucumbers")
true
iex> MapSet.member?(salad_ingredients, "carrots")
false

As you can see, a set will only ever contain one instance of any piece of data, so attempting to add the data again does not modify the set. MapSet.put/2 will add an item to the set and MapSet.member?/2 will indicate if an element is already in the set or not.

I've found that sets are enumerable, although since they are unordered, the elements can be in any arbitrary order.

iex> Enum.to_list(salad_ingredients)
["cucumbers", "lettuce", "tomatoes"]

We can use MapSet.new/1 to create a set from an existing enumerable, so we can easily initialize it with a list.

iex> MapSet.new(["zim", "dib", "gaz"])
#MapSet<["dib", "gaz", "zim"]>

MapSet.union/2 will join two sets together. You can think of it as a set addition operation.

iex> first_set = MapSet.new([1, 2, 3, 4, 5])
#MapSet<[1, 2, 3, 4, 5]>
iex> second_set = MapSet.new([-3, -2, -1, 0, 1, 2])
#MapSet<[-3, -2, -1, 0, 1, 2]>
iex> MapSet.union(first_set, second_set)
#MapSet<[-3, -2, -1, 0, 1, 2, 3, 4, 5]>

MapSet.difference/2 finds elements in the first set that aren't in the other set. You can think of it as a set subtraction operation.

iex> first_set = MapSet.new([1, 2, 3, 4, 5])
#MapSet<[1, 2, 3, 4, 5]>
iex> second_set = MapSet.new([-3, -2, -1, 0, 1, 2])
#MapSet<[-3, -2, -1, 0, 1, 2]>
iex> MapSet.difference(first_set, second_set)
#MapSet<[3, 4, 5]>

MapSet.intersection/2 find elements that are in both the first and second sets.

iex> first_set = MapSet.new([1, 2, 3, 4, 5])
#MapSet<[1, 2, 3, 4, 5]>
iex> second_set = MapSet.new([-3, -2, -1, 0, 1, 2])
#MapSet<[-3, -2, -1, 0, 1, 2]>
iex> MapSet.intersection(first_set, second_set)
#MapSet<[1, 2]>