Работа с наборами как функции

Question

С FP курса:

type Set = Int => Boolean // Predicate 

    /** 
    * Indicates whether a set contains a given element. 
    */ 
    def contains(s: Set, elem: Int): Boolean = s(elem) 

Почему это имеет смысл?

assert(contains(x => true, 100)) 

В основном то, что она делает, это обеспечивает значение 100 функции x => true. I.e., мы предоставляем 100, он возвращает true.

Но как это связано с множествами?

Что бы мы ни положили, оно возвращает true. Где смысл этого?

Я понимаю, что мы можем предоставить нашу собственную реализацию/функцию реализации в качестве параметра, который будет представлять тот факт, что предоставленное значение находится внутри набора (или нет) - тогда (только) эта реализация делает функцию contains заполненной некоторыми смысл/значение/логика/функциональные возможности.

Но пока это выглядит как бессмыслица. Он называется contains, но имя не представляет логики. Мы могли бы назвать это apply(), потому что это означает применить функцию (1-й аргумент) к значению (2-й аргумент). Имея только имя contains, он может рассказать читателю, что автор может сказать. Может быть, это не слишком абстрактно?

Answer 1

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

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

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

Пусть даны set 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) 

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

Answer 2

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

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

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

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