Работа с множествами как функциями

Во фрагменте кода, показанном выше, любой набор S представлен так называемой его характеристической функцией, т. е. функцией, которая по некоторому целому числу i проверяет, содержится ли i в набор S или нет. Таким образом, вы можете думать о такой характеристической функции f как о наборе, а именно

{i | все целые числа i, для которых f i равно true}

Если вы считаете любую функцию с типом Int => Boolean набором (на что указывает синоним типа Set = Int => Boolean), то вы можете описать contains как

Учитывая набор f и целое число i, contains(f, i) проверяет, является ли i элементом f или нет.

Некоторые наборы примеров могут сделать идею более очевидной:

Set                                Characeristic Function
 empty set                          x => false
 universal set                      x => true
 set of odd numbers                 x => x % 2 == 1
 set of even numbers                x => x % 2 == 0
 set of numbeers smaller than 10    x => x < 10

Пример. Набор {1, 2, 3} может быть представлен

val S: Set = (x => 0 <= x && x <= 3)

Если вы хотите узнать, есть ли в этом наборе какое-то число n, вы можете сделать

contains(S, n)

но, конечно (как вы уже сами заметили), вы получите тот же результат, если сделаете это напрямую.

S(n)

Хотя это короче, первое, возможно, легче читать (поскольку намерение несколько очевидно).

Множества (как математически, так и в контексте компьютерного представления) могут быть представлены различными способами. Использование характеристических функций является одной из возможностей. Идея состоит в том, что подмножество S данного универсального множества U полностью определяется функцией f:U-->{true,false} (называемой характеристической функцией подмножества). просто потому, что вы можете рассматривать f(u) как ответ на вопрос «является ли u элементом в S?».

Любой конкретный выбор представления наборов имеет преимущества и недостатки по сравнению с другими методами. В частности, некоторые представления лучше подходят для моделирования на функциональном языке, чем на императивном. Если мы сравним управление множествами как характеристическими функциями и как (отсортированными или несортированными) списками (или массивами), то, например, создание объединений, пересечений и разностей множеств очень эффективно с характеристическими функциями, но не так эффективно со списками. Проверить существование элемента так же просто, как вычислить f(-) с характеристическими функциями, в отличие от поиска в списке. Тем не менее, распечатка элементов в наборе выполняется немедленно со списком, но может потребовать большого количества вычислений с характеристической функцией.

При этом принципиальное отличие состоит в том, что с помощью характеристических функций можно моделировать бесконечные множества, а с массивом это невозможно. Конечно, никакой набор на самом деле не будет бесконечным, но такой набор, как (x: BigInt) x => (x % 2) == 0, действительно представляет этот набор всех четных целых чисел, и с ним действительно можно выполнять вычисления (пока вы не пытайтесь напечатать все элементы).

Итак, у каждого представления есть плюсы и минусы (дух).