Пролог обратный / 2 списка формата вывода

Question

Я новичок в Прологе и застрял в домашнем задании.Я должен построить предикат myReverse(XS,YS), где XS - обратный список YS.Я построил некоторую логику следующим образом:

myReverse([],[]).
myReverse([H],[H]).
myReverse([L|H],[H|T]) :- myReverse(L,T).

Это вроде работает, но вывод не совсем то, что я хочу.Некоторые примеры:

myReverse(L,[]).
L = []                  % ok, that's fine

myReverse(L,[a]).
L = [a]                 % still fine

myReverse(L,[a,b]).
L = [[b]|a]             % expected [b,a]

myReverse(L,[a,b,c]).
L = [[[c]|b]|a]         % expected [c,b,a]

...

Можно ли как-нибудь достичь ожидаемого результата без использования аккумулятора или сторонних реализаций, таких как append?

Редактировать : Этовопрос НЕ дубликат Сторнирование списка в прологе , потому что я НЕ хочу использовать аккумулятор.Кроме того, этот вопрос гораздо больше касается формата вывода моего решения, чем самого решения.

Answer 1

Вы неправильно поняли запись [H|T], трассировка по примеру reverse(L, [a, b]) покажет ее.

Первое объединение:

rule: myReverse([L|H],[H|T]) :- myReverse(L,T).
unified: myReverse([L|a], [a|[b]]) :- myReverse(L, [b]).

На данный момент a - это отдельный атом, а не список, T in [H|T] должен быть списком, чтобы список был полным. [a, b, c] является синтаксическим сахаром для .(a, .(b, .(c, []))).

Ваше второе и третье объединения:

second: myReverse([b], [b]).
going back: myReverse([[b]|a], [a|[b]]) :- myReverse([b], [b]).
which outputs as: myReverse([[b]|a], [a, b]).

Ваш вывод [[b]|a] не является полным списком, поскольку a был атомом, а не списком, поэтому он не выводится как [[b], a].

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

myReverse([], []). % base case
myReverse([Head|Tail], Reversed) :-
    myReverse(Tail, TailReversed), % recursive call
    add_to_tail(Head, TailReversed, Reversed). % Put Head onto the end

add_to_tail(X, [],[X]). % base case
add_to_tail(X, [H|T], [H|Out]) :- 
    add_to_tail(X, T, Out). % recursive call, work done on exit

Более эффективно использовать аккумулятор. Желаем удачи в изучении пролога.