Программа Пролог не корректно объединяет отсортированные списки

Question

У меня есть простая программа, которую я пытаюсь написать на Прологе. По сути, изучая упражнение, я пытаюсь написать программу, которая принимает два отсортированных списка в качестве входных данных и возвращает объединенный список, который также отсортирован. Я назвал предикат «merge2», чтобы не путать его с включенным предикатом «merge», который, кажется, уже делает это.

Я использую рекурсию. Моя реализация ниже

merge2([],[],[]).
merge2([X],[],[X]).
merge2([],[Y],[Y]).
merge2([X|List1],[Y|List2],[X|List]):- X =< Y,merge2(List1,[Y|List2],List).
merge2([X|List1],[Y|List2],[Y|List]):- merge2([X|List1],List2,List).

Когда я запускаю это, я получаю X = [1,2,4,5,3,6], что, очевидно, неверно. Я был в состоянии кодировать несколько раз и пытался вывести рекурсию. Насколько я знаю, это должно вернуть правильный результат. Я не уверен, почему фактический результат такой странный.

Спасибо.

Answer 1

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

Этот ответ требует это то, что вы прочитали мою Список различий вики .

Ваша основная идея c была обоснованной, и в качестве основы для этого ответа использовался список различий. Таким образом, очевидно, большое изменение состоит в том, чтобы просто перейти от закрытого списка к открытому списку.

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

Самый простой базовый случай -

merge2([],[],[]).

но предикат, использующий список различий, может использовать различные средства для представления списка различий с использованием L-H, которое встречается очень часто, но я его не выбрал. Вместо этого этот ответ будет следовать шаблону вики с использованием двух переменных: первой для открытого списка и второй для дыры в конце открытого списка.

Попробуйте создать простой базовый случай на вашем своя.

Далее необходимы два базовых случая, когда один из списков пуст.

Затем случаи, которые выбирают элемент из одного или другого списка.

Наконец, помощник Предикат необходим для того, чтобы можно было использовать запрос merge2(L1,L2,L3).

Если вы запустите код, указанный в списке, он даст многократный ответ из-за возврата. Несколько сокращений решат проблему.

merge2(L1,L2,L3) :-
    merge2_prime(L1,L2,Hole0,Hole),
    Hole = [],
    L3 = Hole0.
merge2_prime([],[],Hole,Hole) :- !.
merge2_prime([X],[],Hole0,Hole) :-
    !,
    Hole0 = [X|Hole].
merge2_prime([],[Y],Hole0,Hole) :-
    !,
    Hole0 = [Y|Hole].
merge2_prime([X|List1],[Y|List2],Hole0,Hole) :-
    X =< Y,
    !,
    Hole0 = [X|Hole1],
    merge2_prime(List1,[Y|List2],Hole1,Hole).
merge2_prime(List1,[Y|List2],Hole0,Hole) :-
    Hole0 = [Y|Hole1],
    merge2_prime(List1,List2,Hole1,Hole).

Пример выполнения:

?- merge2([1,3,4],[2,5,6],L).
L = [1, 2, 3, 4, 5, 6].

?- merge2([0],[0],L).
L = [0, 0].

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

Answer 2

QuickCheck - твой друг. В этом случае свойство, которое вы хотите проверить, может быть выражено с использованием следующего предиката:

sorted(L1, L2) :-
    sort(L1, S1),
    sort(L2, S2), 
    merge2(S1, S2, L),
    sort(L, S),
    L == S.

Обратите внимание, что sort/2 является стандартным встроенным предикатом Prolog. Используя реализацию QuickCheck, предоставляемую инструментом lgtunit Logtalk, который вы можете запустить на большинстве систем Prolog, мы получаем:

?- lgtunit::quick_check(sorted(+list(integer),+list(integer))).
*     quick check test failure (at test 2 after 0 shrinks):
*       sorted([0],[0])
false.

Т.е. ваш код не выполняется для L1 = [0] и L2 = [0]:

?- merge2([0], [0], L).
L = [0, 0] ;
L = [0, 0] ;
false.

Отслеживание этого указанного c запроса должно позволить вам быстро найти хотя бы одну из ошибок в определении merge2/4 предиката. В большинстве систем Prolog вы можете просто набрать:

?- trace, merge2([0], [0], L).

Если вы хотите сохранить дубликаты в объединенном списке, вы можете использовать стандартные предикаты де-факто msort/2 в определении свойства:

sorted(L1, L2) :-
    sort(L1, S1),
    sort(L2, S2), 
    merge2(S1, S2, L),
    msort(L, S),
    L == S.

В этом случае снова запустите QuickCheck:

?- lgtunit::quick_check(sorted(+list(integer),+list(integer))).
*     quick check test failure (at test 3 after 8 shrinks):
*       sorted([],[475,768,402])
false.

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