(SWI-PL) Я не могу понять, как создать правило пролога, чтобы соответствовать этому конкретному типу ввода

Question

Итак, у меня есть домашнее задание, в котором я дал следующий код:

numeral(0).
numeral(succ(X)) :- numeral(X).
numeral(X+Y) :- numeral(X), numeral(Y).

add(0,X,X).
add(succ(X),Y,succ(Z)) :- add(X,Y,Z).

И я должен определить предикат пролога add2 (X, Y, Z), который выдаст, например,следующие результаты

% Exercise 1 Test Cases (for copy-paste to the REPL
%% 1. add2(succ(0)+succ(succ(0)), succ(succ(0)), Z).
%%    >>>> Z = succ(succ(succ(succ(succ(0)))))
%%
%% 2. add2(0, succ(0)+succ(succ(0)), Z).
%%    >>>> Z = succ(succ(succ(0)))
%%
%% 3. add2(succ(succ(0)), succ(0)+succ(succ(0)), Z).
%%    >>>> Z = succ(succ(succ(succ(succ(0)))).
%%
%% 4. add2(succ(0)+succ(0), succ(0+succ(succ(0))), Z).
%%    >>>> Z = succ(succ(succ(succ(succ(0))))).

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

% Exercise 1 Solution
add2(X,Y,Z):- add(X,Y,Z).
add2(A+B,Y,Z):- add2(A,B,X), add2(X,Y,Z).
add2(X,A+B,Z):- add2(A,B,Y), add2(X,Y,Z).

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

Вот то, что я думал, может сработать.

add2(X, succ(A+B), Z):- add2(A,B,Y), add2(X, succ(Y), Z).

Чем я былМысль заключалась в том, что интерпретатор будет распознавать ввод, такой как succ (0 + succ (...)), как succ (A + B), и тогда вышеуказанные правила смогут разрешить 0 + succ (...)в succ (...). Вывод, который я получаю из SWI-PL REPL, просто:

Z = succ(succ(succ(0+succ(succ(0))))) 

Еще одна попытка, которую я предпринял, была следующей:

add2(X,succ(0+succ(Y), Z)):- add2(X,succ(Y),Z).

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

Я использую SWI-PL в качестве своего пролога.

Answer 1

Я думаю, что это может помочь решить проблему с помощью предиката-помощника. Вспомогательная функция преобразует число, представленное каскадом succ(…) и … + …, в единый стиль (поэтому только succ(…)).

Таким образом, мы можем реализовать такую ​​функцию как:

normsucc(0, 0).
normsucc(succ(X), succ(NX)) :-
    normsucc(X, NX).
normsucc(X+Y, NXY) :-
    normsucc(X, NX),
    normsucc(Y, NY),
    add(NX, NY, NXY).

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

add2(X, Y, Z) :-
    normsucc(X, NX),
    normsucc(Y, NY),
    add(NX, NY, Z).

или проще, например, @ false предлагает:

add2(X, Y, Z) :-
    normsucc(X+Y, Z).