Объединение двух упорядоченных списков ProLog

Question

Эй, это мой код. Я только начинающий в прологе, но мне это нужно для школы

firstElement([_|_], [Elem1|List1], [Elem2|List2]):- 
     Elem1 =< Elem2, merge([Elem1] , List1, [Elem2|List2]);
     merge([], [Elem2], List2).

merge([Head|Tail], [Elem1|List1], [Elem2|List2]):-
     Elem1 =< Elem2,!, add(Elem1,[Head|Tail],[Head|Tail1]),
     merge([Head|Tail1], List1, [Elem2|List2]);
     add(Elem2,[Head|Tail],[Head|Tail1]),
     merge([Head|Tail1], [Elem1|List1], List2).

merge([Head|Tail], [], [Elem2|List2]):- 
     add(Elem2,[Head|Tail],[Head|Tail1]).

merge([Head|Tail], [Elem1|List1], []):-
     add(Elem1,[Head|Tail],[Head|Tail1]).

merge([Head|Tail], [], []).

add(X,[],[X]).

add(X,[Y|Tail],[Y|Tail1]):-
    add(X,Tail,Tail1).

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

Answer 1

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

Сначала давайте обсудим два базовых случая, связанных с пустыми списками:

merge(X, [], X).
merge([], X, X).

У вас их совсем нет, но я вижу какое-то признание, что вам нужно обращаться с пустыми списками, особенно во втором и третьем пунктах, но я думаю, что вы запутались и слишком усложнили их. Есть действительно три сценария, охватываемые этими двумя пунктами. Случай, когда оба списка пусты, является халявой, покрываемой обоими, но поскольку этот случай сработает до merge([], [], []), он покрыт. Основная идея здесь заключается в том, что если вы исчерпали любой из этих списков, потому что они были отсортированы, то, что вы оставили в другом списке, будет вашим результатом. Подумай об этом.

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

merge([L|Ls], [R|Rs], [L|Merged]) :-
  L @< R,
  merge(Ls, [R|Rs], Merged).

Вот что вам следует отметить:

• «Результат» L добавляется к рекурсивно сконструированному остатку.
• Рекурсивный вызов merge перестраивает весь второй список, используя [R|Rs].

Должно быть возможно построить другое предложение, посмотрев на это.

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

merge([L|Ls], [R|Rs], [N|Ns]) :-
    (   L @< R -> 
        N = L, merge(Ls, [R|Rs], Ns)
    ;   —- other case goes here
    ).

Эксперт, вероятно, построит его, используя if_/3 вместо:

@<(X,Y,true) :- X @< Y.
@<(X,Y,false) :- X @>= Y.

merge([L|Ls], [R|Rs], [N|Ns]) :-
    if_(@<(L,R),
        (N = L, merge(Ls, [R|Rs], Ns)),
        ( -- other case here )).

В любом случае, я надеюсь, что это поможет проиллюстрировать ситуацию.