1.6.5. ПРИМЕР: СРАВНЕНИЕ МНОЖЕСТВ

Как известно из теории множеств, два множества считаются равными, если они состоят из одних и тех же элементов. Предположим, что мы хотим запрограммировать на Рефале операцию сравнения конечных множеств на равенство. Для этого прежде всего следует придумать какой-то способ изображения множеств в виде объектных выражений. Сначала рассмотрим множества, элементами которых могут быть только символы (в смысле Рефала). Тогда множество символов {Os1, Os2, ..., Osn} можно изобразить в виде объектного выражения

При этом оказывается, что одному и тому же множеству могут соответствовать несколько его изображений. Например, множество {John, Mary} можно изобразить как в виде выражения John Mary, так и в виде выражения Mary John , или даже в виде Mary John John Mary . Таким образом, неравные выражения могут изображать равные множества.

Как известно, элементы множеств сами могут быть множествами. Поэтому мы теперь несколько усложним нашу задачу. Предположим, что рассматриваемые нами множества могут содержать в качестве элементов как символы, так и множества (которые, в свою очередь снова могут содержать множества и т.д.). Теперь мы должны как-то изобразить те элементы множества которые сами являются множествами.

Мы поступим следующим образом. Если элемент множества - символ Os, мы будем его изображать в виде символа Os. Если же элемент множества - множество X, мы будем изображать его в виде терма вида (X'), где X' - изображение множества X. Таким образом, множество {A, {A,B}, {A}} можно изобразить, например, в виде выражения A (A B) (A) .

Теперь постараемся определить функцию-предикат Eqset? , которая будет определять, являются ли два ее аргумента представлениями одного и того же множества. Для этого мы постараемся разложить понятие равенства множеств на более простые понятия.

А именно, два множества A и B равны в том и только том случае, если A является подмножеством B и B является подмножеством A. Далее, множество A является подмножеством множества B в том и только том случае, если для любого элемента X множества A верно, что X принадлежит B.

Поэтому мы определим не одну, а четыре функции-предиката: Eqset? будет проверять, что ее аргументы представляют одно и то же множество, Subset? будет проверять, что множество, представляемое первым аргументом, является подмножеством множества, представляемого вторым аргументом, El? будет проверять, что ее первый аргумент представляет элемент, входящий в множество, представляемое вторым аргументом, а Eqel? будет проверять, что ее аргументы представляют один и тот же элемент множества.

Интересно отметить, что если два элемента множества сами являются множествами, то их сравнение приводит к необходимости сравнивать два множества, поэтому функция Eqel? вынуждена вызвать функцию Eqset? . Таким образом, оказывается, что функция Eqset? в конечном итоге рекурсивно определяется через себя.