Реверсивный слияние

Question

Мы можем объединить два отсортированных списков следующим образом

merge_([A|T], [], [A|T]). 
merge_([], [A|T], [A|T]). 
merge_([A|T], [B|U], [A|V]) :- A @< B, merge_(T, [B|U], V). 
merge_([A|T], [B|U], [B|V]) :- A @>= B, merge_([A|T], U, V). 

, который отлично работает в одном направлении. То, что не работает для этого определения, - это такие запросы, как merge_(A, [a, b, c], [a, b, c, d])., хотя есть уникальное и вполне очевидное решение A = [d].. Даже итерация более merge_(A, B, [a, b, c]). должна приводить к довольно тривиальному набору результатов: A является подмножеством [a, b, c] и B = [a, b, c] \ A.

Как изменить определение merge_, чтобы заставить его работать во всех направлениях?

Answer 1

@ ответ мата спот-. При ограничении проблемы целыми числами вы пользуетесь операторами CLP (FD), так как они знают о домене (или «всевозможных возможных значений»).

К сожалению, A @< B не имеет возможности априори знать, что возможные значения для A и B являются и, следовательно, не может «предложить» никакого возможного решения. Если, например, у вас был предикат valid(X), который был прав для X в области возможных значений, вы можете написать valid(A), valid(B), A @< B, .... Вот надуманный пример, который показывает, как это может сработать, если вы знаете, какой конечный домен возможных атомов вам интересен.

valid(X) :- member(X, [a,b,c,d,e,f,g,h,i,j,k,l,m,n]). 

    merge_([A|T], [], [A|T]). 
    merge_([], [A|T], [A|T]). 
    merge_([A|T], [B|U], [A|V]) :- valid(A), valid(B), A @< B, merge_(T, [B|U], V). 
    merge_([A|T], [B|U], [B|V]) :- valid(A), valid(B), A @>= B, merge_([A|T], U, V). 

Теперь, когда мы ограничены A и B существовать в той или иной конечной области значений, ваш предикат может работать «в обратном направлении»:

| ?- merge_(A, [a, b, c], [a, b, c, d]). 

A = [d] ? a 

no 
| ?- merge_(A, B, [a, b, c]). 

A = [a,b,c] 
B = [] ? a 

A = [] 
B = [a,b,c] 

A = [a] 
B = [b,c] 

A = [a,c] 
B = [b] 

A = [a,b] 
B = [c] 

A = [b,c] 
B = [a] 

A = [b] 
B = [a,c] 

A = [c] 
B = [a,b] 

no 
| ?- 

Answer 2

Предикаты (@<)/2 и (@>=)/2 являются не монотонна, и как таковые не обладают свойствами, которые необходимы, чтобы правильно описать то, что «объединение» означает в целом. Программы, которые используют такие предикаты, могут работать в определенных случаях, но обычно приводят неверные результатов в целом.

Чтобы показать суть проблемы, следующее важное декларативный свойство нарушается этими предикатами:

Добавление цель может максимально уменьшить, никогда не распространяется, множество решений.

Это монотонности сломана этими свойствами, как показано, например, с:

 
?- Y @< X. 
false. 

решения не существует, да? В частности, обязательноX=1, Y=0 is не решение, не так ли? Хорошо посмотрим:

 
?- X=1, Y=0, Y @< X. 
X = 1, 
Y = 0. 

Whaaat? Нам сказали, что есть нет решения вообще!

Другими словами, мы просто не можем применять даже самые фундаментальные логические рассуждения при работе с этими предикатами. На мой взгляд, поэтому лучше избегать таких предикатов, если вы хотите максимально использовать преимущества логического программирования.

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

Вот программа, которая описывает такое слияние списков   целых, используя CLP (FD)   ограничения:

 
merge_([A|T], [], [A|T]). 
merge_([], [A|T], [A|T]). 
merge_([A|T], [B|U], [A|V]) :- A #< B, merge_(T, [B|U], V). 
merge_([A|T], [B|U], [B|V]) :- A #>= B, merge_([A|T], U, V). 

Целое число analogon в примере вы процитировать:

 
?- merge_(A, [1,2,3], [1,2,3,4]). 
A = [4]. 

Итак, это работает точно так, как ожидалось. Единственный недостаток: для этого требуется, чтобы мы определили объекты, которые мы хотим обосновать, до целых чисел. На практике очень много программ в любом случае делают разницу по целым, так что это часто бывает приемлемым.

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

Кстати, другой пример вы цитируете также работает полностью, как ожидается, если вы просто используете CLP (FD) ограничения:

 
?- merge_(A, B, [1,2,3]). 
A = [1, 2, 3], 
B = [] ; 
A = [], 
B = [1, 2, 3] ; 
A = [1], 
B = [2, 3] ; 
A = [1, 2], 
B = [3] ; 
etc.