Почему мой предикат Prolog инвертирует/2 не работает?

Question

Я новичок в Prolog и как упражнение хочу создать предикат инверсии списка. Он использует add_tail предиката, который я сделал ранее — некоторые части могут быть лишними, но я не забочусь:

add_tail(A, [], A) :- 
    !. 
add_tail([A|[]], H, [A,H]) :- 
    !. 
add_tail([A|B], H, [A|C]) :- 
    add_tail(B,H,C). 

Он работает так же, как встроен предикат append/3:

?- add_tail([a,b,c], d, A). 
A = [a, b, c, d]. 

?- append([a,b,c], [d], A). 
A = [a, b, c, d]. 

Когда я использую append в мой invert предикат, он отлично работает, но если я использую add_tail, он не:

invert([], []). 
invert([A|B], C) :- 
    invert(B, D), 
    append(D, [A], C). 

invert2([], []). 
invert2([A|B], C) :- 
    invert2(B, D), 
    add_tail(D, A, C). 

?- invert([a,b,c,d], A). 
A = [d, c, b, a]. 

?- invert2([a,b,c,d], A). 
false.       % expected answer A = [d,c,b,a], like above 

Что такое моя ошибка? Спасибо!

Answer 1

Реализация add_tail/3 делает не вполне ведет себя так, как вы ожидаете. Рассмотрим:

 
?- append([], [d], Xs). 
Xs = [d]. 

?- add_tail([], d, Xs). 
false. 

Это плохо ... Но это еще хуже! Есть еще больше вопросов, с кодом вы представили:

• Используя (!)/0 вы понапрасну ограничить гибкость Вашего предиката.

• Несмотря на то, что [A|[]], возможно, правильный, он запутывает ваш код. Используйте вместо этого [A]!

• add_tail - плохое имя для предиката, который работает в нескольких направлениях.

• Имена переменных также могут быть лучше! Почему бы не использовать более описательные имена, например, As?

  Посмотрите еще раз на переменные, которые вы использовали в последнем пункте add_tail/3!

   
  add_tail([A|B], H, [A|C]) :- 
      add_tail(B, H, C). 
  

  Рассмотрим улучшенные имена переменных:

   
  add_tail([A|As], E, [A|Xs]) :- 
      add_tail(As, E, Xs). 
  

---

Я предлагаю начать сначала, как так:

 
list_item_appended([], X, [X]). 
list_item_appended([E|Es], X, [E|Xs]) :- 
    list_item_appended(Es, X, Xs). 

Давайте соберем list_item_appended/3 использовать в list_reverted/2!

 
list_reverted([], []). 
list_reverted([E|Es], Xs) :- 
    list_reverted(Es, Fs), 
    list_item_appended(Fs, E, Xs). 

Пример запроса:

?- list_reverted([a,b,c,d], Xs). 
Xs = [d, c, b, a]. 

Answer 2

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

?- add_tail(X, Y, Z). 

, дающий один ответ:

X = Z, 
Y = [] 

Это, вероятно, не отношение вы намерены определить Вот.

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

Answer 3

Трудно определить ваше точное ошибку, но первые два пункта из add_tail/3, те, с разрезами, неверны (если я не недоразумение, что предикат должен делать). Уже имя немного вводит в заблуждение, и вам следует позаботиться о том, чтобы у вас был избыточный код.

list_back([], B, [B]). 
list_back([X|Xs], B, [X|Ys]) :- 
    list_back(Xs, B, Ys). 

Это капля в замене для add_tail/3 в вашем определении invert/2. Но, как вы, вероятно, знаете, это не очень умный способ обратить вспять список.Хрестоматийный пример того, как это сделать:

list_rev(L, R) :- 
    list_rev_1(L, [], R). 

list_rev_1([], R, R). 
list_rev_1([X|Xs], R0, R) :- 
    list_rev_1(Xs, [X|R0], R). 

Answer 4

на основе предыдущего ответа «@mat» проблема остаток в первых двух строках

ваш предикат add_tail не нравится, потому что append

с append я получаю эту

| ?- append(X,Y,Z). 
Z = Y, 
X = [] ? ; 
X = [_A], 
Z = [_A|Y] ? ; 
X = [_A,_B], 
Z = [_A,_B|Y] ? ; 
X = [_A,_B,_C], 
Z = [_A,_B,_C|Y] ? ; 
X = [_A,_B,_C,_D], 
Z = [_A,_B,_C,_D|Y] ? ; 
X = [_A,_B,_C,_D,_E], 
Z = [_A,_B,_C,_D,_E|Y] ? ;y 

и, к сожалению, с ур add_tail я получаю й является результатом

| ?- add_tail(X,Y,Z). 
Z = X, 
Y = [] ? ; 
X = [_A], 
Z = [_A|Y] ? ; 
X = [_A|_B], 
Y = [], 
Z = [_A|_B] ? ; 
X = [_A,_B], 
Z = [_A,_B|Y] ? ; 
X = [_A,_B|_C], 
Y = [], 
Z = [_A,_B|_C] ? 
X = [_A,_B,_C], 
Z = [_A,_B,_C|Y] ? y 
yes 

после простой модификации в вашем add_tail кода я получил свой ожидаемый результат

код

% add_tail(A,[],A):-! . comment 

add_tail([],H,H) :-!. 
add_tail([A|B],H,[A|C]) :- add_tail(B,H,C). 

тест add_tail

| ?- add_tail(X,Y,Z). 

    Z = Y, 
    X = [] ? ; 
    X = [_A], 
    Z = [_A|Y] ? ; 
    X = [_A,_B], 
    Z = [_A,_B|Y] ? ; 
    X = [_A,_B,_C], 
    Z = [_A,_B,_C|Y] ? ; 
    X = [_A,_B,_C,_D], 
    Z = [_A,_B,_C,_D|Y] ? ; 
    X = [_A,_B,_C,_D,_E], 
    Z = [_A,_B,_C,_D,_E|Y] ? y 
    yes 

, наконец

я проверить ур invert предикат без модификации

| ?- invert([_A,_B,_C],L). 
L = [_C,_B,_A] ? ; 
no 

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

наслаждаться

Answer 5

Первый пункт add_tail/3 имеет список как второй аргумент, поэтому он никогда не будет применяться к вашему тестовому примеру. Тогда мы остались с 2 пунктами (упрощенных)

add_tail([A],H,[A,H]):-!. 
add_tail([A|B],H,[A|C]) :- add_tail(B,H,C). 

Вы можете видеть, что мы пропускаем пункт согласования для пустого списка в качестве первого аргумента. Конечно, append/3 вместо имеет такой матч.