Я хочу реализовать предикат noDupl / 2 в Prolog и у меня проблемы с одноэлементными переменными

Question

Моя путаница в основном заключается в понимании одноэлементных переменных.

Я хочу реализовать предикат noDupl/2 в Прологе. Этот предикат может использоваться для идентификации чисел в списке, которые появляются ровно один раз, т.е. номера, которые не являются дубликатами. Первый аргумент noDupl - это список для анализа. Второй аргумент - это список чисел, которые не являются дубликатами, как описано ниже. Например, для списка [2, 0, 3, 2, 1] вычисляется результат [0, 3, 1] (поскольку 2 является дубликатом). В моей реализации я использовал предопределенный предикат-член и использовал вспомогательный предикат под названием helper.

Я объясню мою логику в псевдокоде, чтобы вы могли помочь мне определить, где я ошибся.

1. Прежде всего, если первый элемент не является членом остальной части списка, добавьте первый элемент в новый список результатов (как его заголовок).
2. Если первый элемент является членом T, вызовите вспомогательный метод для остальной части списка, первого элемента H и нового списка.

3. Вспомогательный метод, если в хвосте найден H, вернуть список без H, т.е. е. Tail.

   noDupl([],[]).
   noDupl([H|T],L) :-
      \+ member(H,T),
       noDupl(T,[H|T]).
   noDupl([H|T],L) :-
      member(H,T),
      helper(T,H,L).
   
   helper([],N,[]).
   helper([H|T],H,T). %found place of duplicate & return list without it
   helper([H|T],N,L) :-
      helper(T,N,[H|T1]).%still couldn't locate the place, so add H to the new List as it's not a duplicate
   

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

Answer 1

Предупреждения об одноэлементных переменных не являются актуальной проблемой.

Одиночные переменные - это логические переменные, которые встречаются один раз в некотором предложении Prolog (факт или правило).Пролог предупреждает вас об этих переменных, если они названы как не-одиночные переменные, т. Е. Если их имя не начинается с _.

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

---

Давайте построимканоническое решение вашей проблемы.

Во-первых, забудьте о CamelCase и выберите правильное имя предиката, которое отражает реляционный характер рассматриваемой проблемы: как насчет list_uniques/2?

Затем документируйте случаи, в которых вы ожидаете, что предикат даст один ответ, несколько ответов или вообще никакого ответа.Как?Не просто текст, а запросы .

Начните с самого общего запроса:

?- list_uniques(Xs, Ys).

Добавьте несколько наземных запросов:

?- list_uniques([], []).
?- list_uniques([1,2,2,1,3,4], [3,4]).
?- list_uniques([a,b,b,a], []).

И добавьте запросы, содержащие переменные:

?- list_uniques([n,i,x,o,n], Xs).
?- list_uniques([i,s,p,y,i,s,p,y], Xs).

?- list_uniques([A,B], [X,Y]).
?- list_uniques([A,B,C], [D,E]).
?- list_uniques([A,B,C,D], [X]).

Теперь давайте напишем некоторый код!Основано на library(reif) запись:

:- use_module(library(reif)).

list_uniques(Xs, Ys) :-
   list_past_uniques(Xs, [], Ys).

list_past_uniques([], _, []).           % auxiliary predicate
list_past_uniques([X|Xs], Xs0, Ys) :-
   if_((memberd_t(X,Xs) ; memberd_t(X,Xs0)),
       Ys = Ys0,
       Ys = [X|Ys0]),
   list_past_uniques(Xs, [X|Xs0], Ys0).

Что происходит?

• list_uniques/2 построено на предикате помощника list_past_uniques/3

• В любой момент list_past_uniques/3 отслеживает:

  • все элементы впереди (Xs) и
  • все элементы "позади" (Xs0) некоторые элементы исходного списка X.

• Если X является членом , либо список, затем Ys пропускает X - это не уникально !

• В противном случае X является уникальным иэто происходит в Ys (в качестве заголовка списка).

Давайте выполним некоторые из вышеуказанных запросов, используя SWI-Prolog 8.0.0:

?- list_uniques(Xs, Ys).
   Xs = [], Ys = []
;  Xs = [_A], Ys = [_A]
;  Xs = [_A,_A], Ys = []
;  Xs = [_A,_A,_A], Ys = []
...

?- list_uniques([], []).
true.
?- list_uniques([1,2,2,1,3,4], [3,4]).
true.
?- list_uniques([a,b,b,a], []).
true.

?- list_uniques([1,2,2,1,3,4], Xs).
Xs = [3,4].
?- list_uniques([n,i,x,o,n], Xs).
Xs = [i,x,o].
?- list_uniques([i,s,p,y,i,s,p,y], Xs).
Xs = [].

?- list_uniques([A,B], [X,Y]).
A = X, B = Y, dif(Y,X).
?- list_uniques([A,B,C], [D,E]).
false.
?- list_uniques([A,B,C,D], [X]).
   A = B, B = C, D = X, dif(X,C)
;  A = B, B = D, C = X, dif(X,D)
;  A = C, C = D, B = X, dif(D,X)
;  A = X, B = C, C = D, dif(D,X)
;  false.

Answer 2

В этом решении слегка измененная версия tpartition используется для большего контроля над тем, что происходит, когда элемент проходит условие (или нет):

tpartition_p(P_2, OnTrue_5, OnFalse_5, OnEnd_4, InitialTrue, InitialFalse, Xs, RTrue, RFalse) :-
   i_tpartition_p(Xs, P_2, OnTrue_5, OnFalse_5, OnEnd_4, InitialTrue, InitialFalse, RTrue, RFalse).

i_tpartition_p([], _P_2, _OnTrue_5, _OnFalse_5, OnEnd_4, CurrentTrue, CurrentFalse, RTrue, RFalse):-
  call(OnEnd_4, CurrentTrue, CurrentFalse, RTrue, RFalse).
i_tpartition_p([X|Xs], P_2, OnTrue_5, OnFalse_5, OnEnd_4, CurrentTrue, CurrentFalse, RTrue, RFalse):-
   if_( call(P_2, X)
      , call(OnTrue_5, X, CurrentTrue, CurrentFalse, NCurrentTrue, NCurrentFalse)
      , call(OnFalse_5, X, CurrentTrue, CurrentFalse, NCurrentTrue, NCurrentFalse) ),
   i_tpartition_p(Xs, P_2, OnTrue_5, OnFalse_5, OnEnd_4, NCurrentTrue, NCurrentFalse, RTrue, RFalse).

InitialTrue / InitialFalse и RTrue / RFalse содержат желаемое начальное и конечное состояние, процедуры OnTrue_5 и OnFalse_5 управляют переходом состояния после проверки условия P_2 для каждого элемента и OnEnd_4 управляет последним переходом.

Со следующим кодом для list_uniques/2:

list_uniques([], []).
list_uniques([V|Vs], Xs) :-
   tpartition_p(=(V), on_true, on_false, on_end, false, Difs, Vs, HasDuplicates, []),
   if_(=(HasDuplicates), Xs=Xs0, Xs = [V|Xs0]),
   list_uniques(Difs, Xs0).


on_true(_, _, Difs, true, Difs).

on_false(X, HasDuplicates, [X|Xs], HasDuplicates, Xs).

on_end(HasDuplicates, Difs, HasDuplicates, Difs).

Когда элемент проходит фильтр (его дубликат), мы просто отмечаем, что в списке есть дубликаты, и пропускаем элемент, в противном случае элемент сохраняется для дальнейшей обработки.

Answer 3

Так же, как мой предыдущий ответ , следующий ответ основан на library(reif) - и использует его несколько идиоматическим образом.

:- use_module(library(reif)).

list_uniques([], []).
list_uniques([V|Vs], Xs) :-
   tpartition(=(V), Vs, Equals, Difs),
   if_(Equals = [], Xs = [V|Xs0], Xs = Xs0),
   list_uniques(Difs, Xs0).

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

Answer 4

Этот ответ похож на этот предыдущий ответ @ gusbro .

Однако он не предлагает несколько барочную версию tpartition/4, новместо этого расширенная, но, надеюсь, более компактная версия tfilter/3, называемая tfilter_t/4, которую можно определить следующим образом:

tfilter_t(C_2, Es, Fs, T) :-
   i_tfilter_t(Es, C_2, Fs, T).

i_tfilter_t([], _, [], true).
i_tfilter_t([E|Es], C_2, Fs0, T) :-
   if_(call(C_2,E), 
       ( Fs0 = [E|Fs], i_tfilter_t(Es,C_2,Fs,T) ),
       ( Fs0 = Fs, T = false, tfilter(C_2,Es,Fs) )).

Адаптация list_uniques/2 проста:

list_uniques([], []).
list_uniques([V|Vs], Xs) :-
   if_(tfilter_t(dif(V),Vs,Difs), Xs = [V|Xs0], Xs = Xs0),
   list_uniques(Difs, Xs0).

Сохранитьскроллбары.Оставайтесь стройными!Используйте filter_t/4.

Answer 5

У вас уже есть проблемы с первым предикатом, noDupl/2.

Первый пункт, noDupl([], []). выглядит хорошо. Второй пункт неверен.

noDupl([H|T],L):-
    \+member(H,T),
    noDupl(T,[H|T]).

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

noDupl([H|T], [H|L]) :-
    \+ member(H, T),
    noDupl(T, L).

Пожалуйста, внимательно посмотрите на это и попытайтесь понять. H добавляется к результату путем объединения результата (второй аргумент в заголовке) в список с H в качестве заголовка и переменной L в качестве хвоста. Синглтонная переменная L в вашем определении является синглтоном, потому что в вашем определении есть ошибка, а именно, вы вообще ничего не делаете с ней.

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

noDupl([H|T], L) :-
    member(H, T),
    helper(T, H, T0),
    noDupl(T0, L).

Ваш helper/3 очищает остальную часть исходного списка от дубликата, объединяя результат с T0, а затем использует этот чистый список для продолжения удаления дубликатов.

Теперь к вашему помощнику. Первый пункт выглядит хорошо, но имеет переменную-одиночка. Это допустимый случай, когда вы не хотите ничего делать с этим аргументом, поэтому вы «объявляете» его неиспользуемым, например, так:

helper([], _, []).

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

?- helper([1,2,3,2], 2, L).

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

helper([H|T], H, L) :-
    helper(T, H, L).
helper([H|T], X, [H|L]) :-
    dif(H, X),
    helper(T, X, L).

Это минимальные исправления, которые дадут вам ответ, когда первый аргумент noDupl/2 будет обоснован. Вы можете сделать это, переименовав noDupl/2 в noDupl_ground/2 и определив noDupl/2 как:

noDupl(L, R) :-
    must_be(ground, L),
    noDupl_ground(L, R).

Попробуйте посмотреть, что вы получите по разным запросам в текущей наивной реализации, и спросите, есть ли у вас дополнительные вопросы. Он по-прежнему полон проблем, но это действительно зависит от того, как вы будете его использовать и что вы хотите получить от ответа.