Можно ли перевернуть список только с двумя аргументами?

Question

Можно ли перевернуть список в Прологе только с двумя аргументами?Например:

reverse_list(List, Reversed).

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

С тремя аргументами вы можете использовать аккумулятор (почти как вфункциональное программирование):

reverseList([], Accumulator, Accumulator).
reverseList([Head|Tail], Accumulator, Solution) :-
  reverseList(Tail, [Head|Accumulator], Solution).
reverseList(List, Solution) :-
  reverseList(List, [], Solution).

Разъяснение : я видел решение с добавлением, мне было интересно, если бы вы могли сделать это без других функций пролога

Answer 1

уверен:

reverseList([[], Accumulator, Accumulator]).
reverseList([[Head|Tail], Accumulator, Solution]) :-
  reverseList([Tail, [Head|Accumulator], Solution]).
reverseList([List, Solution]) :-
  reverseList([List, [], Solution]).

редактировать: на самом деле это только один: b

не обмануть подход:

reverse([],[]).
reverse([H|T],L):-
    reverse(T,R),
    append(R,[H],L).

проблема в том, что производительностьбудет довольно плохо: вы будете повторяться по списку и для каждого элемента вы будете делать одно добавление / 3.используя time / 1 и случайный список из 1 000 000 элементов:

accumulator:    % 2,000,003 inferences, 0.652 CPU in 0.652 seconds (100% CPU, 3066292 Lips)
arity-2         % 1,000,003 inferences, 0.178 CPU in 0.178 seconds (100% CPU, 5602426 Lips)

Answer 2

Вы можете написать rev_list функцию с двумя аргументами:

rev_list([], []).
rev_list([Head|Tail], Reversed) :- rev_list(Tail, TailReversed), 
                                       append(TailReversed, [Head], Reversed).

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

rev x::xs = rev xs @ [x]

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

Answer 3

Я знаю, что опаздываю на вечеринку, но есть способ сделать это без "обмана" или использования append:

rev([], []).
rev([Head], [Head]).
rev([Head|Tail], [RHead|RTail]) :-
  rev(Tail, [RHead|RMid]),
  rev(RMid, Mid),
  rev([Head|Mid], RTail).

Это не очень эффективно (O(3^n) время), но оно элегантно и даже может быть полезно для доказательства теорем.