Множество

Множество — набор уникальных объектов (называемых элементами множества). То же: set.

Множество — одно из ключевых понятий современной математики.

В Эрланге нет специального типа данных для множества, однако есть модули для работы с множествами. Множество задаётся другими типами данных: списком, картой. В стандартной поставке Erlang/OTP есть следующие модули для работы с множествами:

sets,
ordsets,
gb_sets,
sofs.

В sets множество задаётся с помощью типа данных карта, в ordsets — с помощью списка (упорядоченного):

1> sets:from_list([7,7,7,3,5,1,9,1]).
#{1 => [],3 => [],5 => [],7 => [],9 => []}
2> ordsets:from_list([7,7,7,3,5,1,9,1]).
[1,3,5,7,9]

В карте все ключи являются уникальными, поэтому как видим в первом случае, это свойство карты можно использовать для задания множества. Во втором случае множество задаётся с помощью упорядоченного списка — упорядоченность нужна для операций со множествами (например, чтобы найти пересечение множеств).

Конечно, можно в качестве элементов множества задавать не только числа, но и любые другие термы.

3> sets:from_list([test, math:pi(), 10, test, "test"]).
#{10 => [],3.141592653589793 => [],test => [],"test" => []}
4> ordsets:from_list([test, math:pi(), 10, test, "test"]).
[3.141592653589793,10,test,"test"]

У sets и ordsets есть одно важное отличие, про которое не стоит забывать. В sets элементы различны, если они не удовлетворяют строгому равенству (=:=). В ordsets для этого используется просто равенство (==):

5> sets:from_list([7,7.0,3,5,1]).
#{1 => [],3 => [],5 => [],7 => [],7.0 => []}
6> ordsets:from_list([7,7.0,3,5,1]).
[1,3,5,7]
7> ordsets:from_list([7.0,7,3,5,1]).
[1,3,5,7.0]

Как видим, в sets 7 и 7.0 были признаны разными элементами. В ordsets — одинаковыми. При этом у ordsets результат зависит от порядка элементов в списке, который используется для создания множества. Если сначала встретится 7, то во множестве будет именно 7. Если встретится первым 7.0, то будет именно 7.0. Это не страшно, если в дальнейшем мы будем работать со множеством именно как со множеством, но если в дальнейшем мы будем работать со множеством как со списком, это способно дать неожиданный результат.

В разных случаях скорость sets и ordsets разная. sets лучше применять в тех случаях, когда часто надо проверять, является ли какой-то объект элементом множества или нет (is_element). Операции по нахождению третьего множества быстрее у ordsets.

Множества можно использовать везде, где есть намёк на формальную логику. Пример: проанализировать CSV-файл и отобразить всех пользователей, у которых есть такие-то права, но которые при этом не являются работниками нашей организации.

Базовые операции со множествами

У sets и ordsets одинаковый набор функций для работы со множествами. Например, для нахождения пересечения двух множеств есть функция intersection. В обоих случаях она найдёт элементы, встречающиеся в обоих множествах.

1> S1 = sets:from_list([a,b,c,d]).
#{c => [],a => [],b => [],d => []}
2> S2 = sets:from_list([c,d,e,f]).
#{c => [],f => [],e => [],d => []}
3> sets:intersection(S1,S2).
#{c => [],d => []}
4> S3 = ordsets:from_list([a,b,c,d]).
[a,b,c,d]
5> S4 = ordsets:from_list([c,d,e,f]).
[c,d,e,f]
6> ordsets:intersection(S3,S4).
[c,d]

Другие базовые операции:

is_equal(Set1, Set2) сравнивает два множества на равенство.
size(Set) — размер множества.
subtract(Set1, Set2) вычитает из множества Set1 множество Set2 — возвращает множество элементов Set1, которые не встречаются в Set2.
union(Set1, Set2) складывает два множества — возвращает множество элементов (конечно, уникальных), которые встречаются хотя бы в одном множестве.

Документация

h(sets).

h(ordsets).

h(gb_sets).

h(sofs).