Получение отсортированного, отдельного списка целых чисел в Прологе

Question

Я пытаюсь сделать что-то очень простое, изучая Пролог. Однако я запутался, почему это работает:

?- length( L, 3 ),
   maplist( member, L, [[1,2,3], [1,2,3], [1,2,3]] ),
   sort( L, L ).
L = [1, 2, 3] ;

Но это, казалось бы, эквивалентное изменение с использованием clpfd:

?- use_module(library(clpfd)).

?- length( L, 3 ), L ins 1..3, sort( L, L ).
L = [_G5891, _G5894, _G5897],
_G5891 in 1..3,
_G5894 in 1..3,
_G5897 in 1..3.

Это работает:

?- length( L, 3 ), L ins 1..3, chain( L, #< ).
L = [1, 2, 3].

Но это не так:

?- length( L, 3 ), L ins 1..3, chain( L, #=< ), all_different( L ).
L = [_G6519, _G6522, _G6525],
_G6519 in 1..3,
all_different([_G6519, _G6522, _G6525]),
_G6522#>=_G6519,
_G6522 in 1..3,
_G6525#>=_G6522,
_G6525 in 1..3.

Может кто-нибудь объяснить, почему нерабочие примеры не дают мне ожидаемого результата?

Как побочный вопрос, есть ли более краткий способ переписать мой maplist Выражение в первом примере выше?

Answer 1

CLP в Прологе

Используемая вами система (библиотека SWI-Prolog + (clpfd)) является одним из примеров встраивания целочисленного решателя ограниченных областей в систему Prolog (некоторые другие - это CHIP, ECLiPSe+fd/ic, B-Prolog, SICStus+clpfd). Такое встраивание очень естественно в том смысле, что многие концепции Пролога отображаются непосредственно на концепции в Программировании с ограничениями, что дает нам Программирование с логическим ограничением (CLP).

Тем не менее, есть ряд особенностей простого Пролога, которых следует избегать при использовании его для CLP. Среди них есть сокращения (включая скрытые в конструкции if-then-else и \+/2 отрицание), но и мета-логические операции, как в вашем случае. В наших целях мета-логический означает любой примитив, который обрабатывает переменные как объекты (а не просто как заменители значений). Примеры этого var/1, ==/2, @</2и действительно также sort/2,

Мета-логические примитивы уже могут вызывать уродливые эффекты в простом прологе, например

?-  X\==Y, X=3, Y=3, X==Y.
Yes

но программисты Пролога научились правильно их использовать и избегать таких проблем. Однако с CLP легче попасть в эти ловушки, поскольку поток управления выполнением гораздо менее очевиден.

Что касается ваших примеров, первый работает, потому что sort/2 сортирует списки целых чисел, проблем нет. Во втором случае sort/2 сортирует список переменных домена, в результате чего получается список переменных домена в произвольном, определенном системой порядке. Как только это будет сделано, sort/2 считает свою работу выполненной. Если позже вы назначите целочисленные значения этим якобы "отсортированным" переменным, сортировка списка больше не будет проверяться, и ваша программа теперь может возвращать несортированные целочисленные списки в качестве результатов.

Правильная альтернатива состоит в том, чтобы использовать проверку сортировки, которая включает только чисто логические примитивы Пролога и / или предикаты ограничения, определенные решателем CLP. Вы уже сделали это, используя chain/2 ограничение в вашем третьем примере.

Локальное распространение и поиск

В последнем примере вы можете наблюдать типичное поведение решателя ограничений, основанное на локальном распространении: полученный вами ответ правильный, но не очень удовлетворительный. Анализируя ограничения более глубоко, на самом деле можно сделать вывод, что единственное правильное решение [1,2,3], но решатель не делает этого, потому что это может быть вычислительно дорого. Но посмотрите, что произойдет, если вы добавите немного информации:

?- L=[_,Y,_], L ins 1..3, chain(L, #=<), all_different(L), Y=2.
L = [1, 2, 3],
Y = 2

Задница, как только решатель узнает, что Y равен 2, задача становится достаточно легкой для решения полностью.

Решение для общего случая состоит в том, чтобы систематически разбить проблему на более простые подзадачи, убедившись, что вы охватите все. Другими словами, вы добавляете поиск, а способ Пролога - это дизъюнкция. В примере это может быть простым member(Y,[1,2,3]), Как правило, вы хотите сделать то же самое для всех переменных домена в вашей проблеме, просто чтобы быть в безопасности. Решатель CLP даст вам удобный примитив для этого, например, в случае clpfd

?- L=[_,_,_], L ins 1..3, chain(L, #=<), all_different(L), label(L).
L = [1, 2, 3] ;
false.

Это общая структура для программ CLP: сначала настройка ограничений, а затем поиск.

Answer 2

Встроенный предикат sort/2 эффективно сортирует список на основе порядка терминов, определенных для всех терминов, включая переменные. По этой причине этот предикат не может рассматриваться для реализации конкретного отношения. Только в особых случаях, например, когда первый аргумент не содержит переменных (то есть ground(L) успешно) и термин ациклический (acyclic_term(L) успешно), встроенное соответствует очевидному соотношению.

Вот еще один такой странный случай sort([X,1],[1,1]) который преуспевает, объединяя X = 1,