Странные результаты для манипулирования списком

Question

Я пытаюсь реализовать некоторые предикаты для манипулирования списками в Прологе. Все работает как хотелось. Например

append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs). 

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

?- append([1,2,3],[4,5,6],X).
X = [1,2,3,4,5,6].                   % OK

Но у меня проблемы с предикатом delete. Вот как это реализовано:

delete(X,[Y|Ys],Zs) :- X == Y, delete(X,Ys,Zs).
delete(X,[_X|Ys],[_Z|Zs]) :- delete(X,Ys,Zs).
delete(_X,[],[]).

Пример запроса с плохим результатом:

?- delete(4,[1,2,3,4],X).
X = [_G8975, _G8978, _G8981].       % BAD

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

Спасибо заранее!

Answer 1

Одним из загадочных способов избавиться от загадочных имен переменных является использование numbervars/3, например,

?- length(X, 3).
X = [_G2019, _G2022, _G2025].

?- length(X, 3), numbervars(X, 0, _).
X = [A, B, C].

Теперь к вашему delete/3, Помимо других незначительных проблем, таких как необычный порядок аргументов, необычный порядок предложений и т. Д., У вас есть одна главная проблема: во втором предложении вы помещаете новую анонимную переменную, где должен был быть элемент исходного списка.

delete(X, [Y|Ys], [Y|Zs]) :- delete(X, Ys, Zs).

С этим во втором пункте, это вроде работает:

?- delete(4, [1,2,3,4], L).
L = [1, 2, 3] .

?- delete(2, [1,2,3,4,2,3,4], L).
L = [1, 3, 4, 3, 4] .

Есть дальнейшие проблемы с вашей реализацией. Вы можете посмотреть на реализацию того же предиката в library(lists) от SWI-Prolog: читайте и документацию тоже!

Answer 2

Этот ответ вдохновлен логически чистым кодом, который false представил в своем ответе.

Давайте использовать мета-предикат tfilter/3 и неопределенность неравенства dif/3 и просто напиши:

? - Vs0 = [1,2,3,4], tfilter (dif (4), Vs0, Vs).
Vs0 = [1,2,3,4],
Vs = [1,2,3]. % преуспевает детерминистически? - Vs0 = [1,2,3,4,2,3,4], tfilter (dif (2), Vs0, Vs).
Vs0 = [1, 2, 3,4, 2, 3,4],
Vs = [1, 3,4, 3,4]. % преуспевает детерминистически

Реализация delete/3 сводится к:

delete(E,Vs0,Vs) :-
   tfilter(dif(E),Vs0,Vs).

Как и код @ false, эта реализация является монотонной, что делает предикат универсальным и позволяет получать логически обоснованные ответы даже при работе с неосновными терминами.

Наконец, давайте выполним довольно общий запрос и посмотрим на все ответы:

? - Vs0 = [X, Y, Z], удалить (E, Vs0, Vs). Vs0 = [ X, Y, Z ], E = X, E = Y, E = Z, Vs = []; Vs0 = [ X, Y, Z ], E = X, E = Y, dif (E, Z), Vs = [ Z ]; Vs0 = [ X, Y, Z ], E = X, dif (E, Y), E = Z, Vs = [ Y ]; Vs0 = [ X, Y, Z ], E = X, dif (E, Y), dif (E, Z), Vs = [ Y, Z ]; Vs0 = [ X, Y, Z ], dif (E, X), E = Y, E = Z, Vs = [ X ]; Vs0 = [ X, Y, Z ], диф (E, X), E = Y, диф (E, Z), Vs = [ X, Z ]; Vs0 = [ X, Y, Z ], диф (E, X), диф (E, Y), E = Z, Vs = [ X, Y ]; Vs0 = [ X, Y, Z ], диф (E, X), диф (E, Y), диф (E, Z), Vs = [ X, Y, Z ]. 

Answer 3

В вашей программе есть несколько проблем. Но сначала, как новичок:

Придерживайтесь чистого монотонного подмножества Пролога

В вашей программе вы используете (==)/2 которого больше нет в этом чистом подмножестве. В вашем случае замените его на (=)/2,

Всегда смотрите на все ответы

Циклы верхнего уровня Пролога показывают только первый ответ. Вы должны требовать большего, нажав ; или ПРОСТРАНСТВО. Ваша программа с (=)/2 дает (с более читаемыми переменными):

?- delete(4,[1,2,3,4],X).
X = [_A,_B,_C] ;
X = [_A,_B,_C,_D] ;
false.

То есть: не только первый ответ является неожиданным, но есть и второй, со списком такой же длины, что и исходный. С другой стороны, первый ответ включал ожидаемое решение. Так что программа довольно общая.

Уменьшить размер ввода

?- delete(4,[4],L).
L = [] ;
L = [_A] ;
false.

Первый ответ кажется правильным, а второй совершенно неожиданным. То есть определение является слишком общим, о чем свидетельствует delete(4,[4],[any])

Специализируйте программу

Чтобы локализовать программу, специализируйте программу, вводя такие цели, как false, а также = настолько, насколько это возможно, и до тех пор, пока delete(4,[4],[any]) преуспевает. Я придумаю:

? - удалить (4,[4],[любой]).

удалить (X, [Y | Ys], Zs): - false, X = Y, удалить (X, Ys, Zs).
удалить (X, [_ X | Ys], [_ Z | Zs]): - X = 4, _X = 4, _Z = любой,
   удалить (X,Ys,Zs).
удалить (_X,[],[]):- _X = 4.

Теперь должно быть очевидно, что в этом правиле _X =4, _Z = any должно быть довольно то же самое, и X = 4, _X = 4 должно быть по-другому. Неравенство лучше всего выражается dif/2,

delete(_X, [], []).
delete(X, [Y|Ys], [Y|Zs]) :-
   dif(X, Y),
   delete(X, Ys, Zs).
delete(X, [X|Ys], Zs) :-
   delete(X, Ys, Zs).

Это определение теперь можно использовать по-разному. подобно

?- delete(X,Xs,[1,2,3]).
Xs = [1, 2, 3],
dif(X, 3),
dif(X, 2),
dif(X, 1) ;
Xs = [1, 2, 3, X],
dif(X, 3),
dif(X, 2),
dif(X, 1) ;
Xs = [1, 2, 3, X, X],
dif(X, 3),
dif(X, 2),
dif(X, 1) ...

Обратите внимание, что сейчас существует бесконечно много ответов!