Правильная работа с множествами в Прологе

В Прологе кажется, что множества представлены списками.

Например, вот реализация union/3 из SWI-Prolog:

union([], L, L) :- !.
union([H|T], L, R) :-
    memberchk(H, L), !,
    union(T, L, R).
union([H|T], L, [H|R]) :-
union(T, L, R).

Однако этот предикат не очень декларативен, например:

?- union([1,2,3],X,[1,2,3,4]).
X = [1, 2, 3, 4].

который должен оставить несколько точек выбора, или:

?- union(X,[1,2],[1,2,3,4]).
<infinite loop>

что даже не работает!

Помимо этого, мы также находим следующие проблемы:

?- union([1,2,3],[4,5],[1,2,3,5,4]).
false.

?- union([1,1,1],[4,5],[1,1,1,4,5]).
true.

что явно неверно, если мы действительно говорим о наборах.

Мы ясно видим, что использовать списки для обсуждения наборов непросто, потому что:

  • Наборы не упорядочены, тогда как списки;
  • Наборы не содержат повторяющихся значений, тогда как списки могут.

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

Как следует правильно реализовать в Prolog предикаты, работающие с наборами?

Это очень общий вопрос, не относящийся к используемому здесь примеру union/3.


list set prolog unification
person Fatalize    schedule 02.11.2016    source источник
comment
Лень сейчас отвечать, но стоит взглянуть хотя бы на библиотеку (ordsets). Вы также можете использовать справочную таблицу, реализованную в библиотеке (assoc), и dict SWI-Prolog в виде набора: используйте ключи, все значения могут быть атомом true или чем-то в этом роде. Они не дают готовых ответов на ваш вопрос, но, по крайней мере, они представляют собой лучшую реализацию, чем то, что вы показываете.   -  person    schedule 02.11.2016

Ответы (3)


arrow_upward
3
arrow_downward

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

Но на самом деле это скорее исследовательский проект, чем задача программирования. Что вы можете делать в чистом Prolog сегодня?

Вы можете аппроксимировать наборы списками по-прежнему чистым и декларативным способом, при условии, что вы принимаете во внимание функциональные зависимости. Дополнительную информацию см. В этом ответе!

person false    schedule 02.11.2016

arrow_upward
3
arrow_downward

Как должны быть правильно реализованы предикаты, работающие с множествами, в Прологе?

Прежде всего, предикат объединения в прологе должен учитывать основные математические свойства объединения множеств, а именно:

  • ассоциативность: A ∪ (B ∪ C) = (A ∪ B) ∪ C
  • коммутативный: A ∪ B = B ∪ A

(Эти свойства гарантируют, что объединение является однозначным, что, однако, не должно касаться реализации предиката Пролога с аргументами.)

Более того, реализация объединения (или других предикатов множества) также должна иметь следующие свойства в Прологе:

  • Handle duplicates.

Если в одном из списков есть хотя бы элемент более одного раза, то этот элемент должен быть засчитан только один раз.

  • Handle cases where at least one argument is not instantiated.

например, Union([X],Union_Set,[Y])., очевидно, должен возвращать Union_set=[X,Y]. Другой пример: Union([X],[X1,Y1],[Y])., очевидно, должен возвращать X1=X, Y1=Y. через объединение.

  • Be deterministic Объединение - это набор всех отдельных элементов в коллекции. Это определение четко определено (математически), что не оставляет возможности неединственности (результат должен быть уникальным для каждой четко определенной математической операции (не только для объединения)).
  • Еще одной желанной особенностью может быть логическая чистота, которая обеспечивается алгебраическими свойствами (коммутативность, ассоциативность).
  • Обработка бесконечных циклов.

Как и в вашем примере в предикате объединения: union (X, [1,2], [1,2,3,4]). должен вернуть некоторую ошибку создания экземпляра.

Это некоторые функции, которые мне следует включить, поскольку мы говорим об операциях Set, но, конечно, это не все свойства, которые мы могли бы рассмотреть. Это также связано с реализациями, которые мы делаем при определении предикатов.

Напоследок еще один комментарий к: Sets are not ordered whereas lists are;

Это неправда. Частичное или полное упорядочение применяется как в списках, так и в наборах, и оно должно выполняться, если мы можем сравнивать все элементы или только некоторые элементы, что означает, что мы можем расположить их по порядку. Любая структура данных, такая как списки, не обеспечивает порядок (порядок связан с семантикой), если мы не рассматриваем его, например, в куче, где это древовидная структура, но мы считаем, что это упорядочено.

person coder    schedule 02.11.2016
comment
Если вы занимаетесь алгебраическими свойствами, такими как ассоциативность и коммутативность, вы неизбежно уже приняли логическую чистоту. Ведь без него эти свойства не будут реализованы! - person false; 02.11.2016
comment
Действительно очень полезный комментарий @false, спасибо !!! Отредактирую ответ, где упомяну логическую чистоту. - person coder; 02.11.2016

arrow_upward
2
arrow_downward

Во-первых, чтобы добавить дополнительный пример того, с чем нам сейчас приходится справляться:

?- union(A, [], A).
A = [].

Что мы можем читать как:

Пустой набор - это единственный набор.

Кто бы мог подумать?

Очень хорошая библиотека для рассуждений о множествах доступна в ECLiPSe как библиотека (коньюнто) :

Conjunto - это система для решения установленных ограничений по конечному набору условий предметной области. Он был разработан с использованием ядра ECLiPSe на основе метатерм. Он содержит библиотеку конечных доменов ECLiPSe. Библиотека Consunto.pl реализует ограничения на набор терминов предметной области, которые содержат термины бренда, а также основные наборы.

Также обратите внимание:

Начиная с версии 5.1 ECLiPSe, библиотека, описанная в этой главе, постепенно прекращается и заменяется новой библиотекой решателя наборов lib(ic_sets).

Это отличные библиотеки, и я рекомендую вам использовать их в качестве отправной точки, если вас интересуют установленные ограничения.

Хороший пример того, что можно сделать с заданными ограничениями, можно найти здесь:

http://csplib.org/Problems/prob010/models/golf.ecl.html

person mat    schedule 02.11.2016
comment
Немного другая интерпретация вашего первого примера: только пустой набор объединяется с пустым набором. - person false; 02.11.2016
comment
С другой стороны, эта специализация успешна: ?- A = [a], union(A, [], A). - person mat; 03.11.2016
comment
В самом деле, мы не можем дать всему определению сколько-нибудь значимого толкования. Мы можем дать только конкретные ответы один. - person false; 03.11.2016