Пролог: как избежать обратного хода без порезов?

Question

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

% Append an element to a list. 
myappendelem(X,L,[X|L]). 

% True if input list contains X. 
mycontains([H | T], X) :- 
    H == X; 
    mycontains(T,X). 

% Does the work for notin(). 
nocontains([],_,A,A). 
nocontains([H|T],L,A,R):- 
    mycontains(L,H), 
    nocontains(T,L,A,R); 
    myappendelem(H,A,AR), 
    nocontains(T,L,AR,R). 

% Returns all elements in L1 not in L2. 
notin(L1,L2,R):- 
    nocontains(L1,L2,[],X). 

Это работает, однако она дает более одного ответа, например:

notin([5,1],[4,3,2,1],X). 
X = [5]; 
X = [5,1]. 

Это является проблемой, так как я использую этот предикат, чтобы разобраться в пути в графе (L1 - список узлов, к которым я мог бы перейти, а L2 - это узлы, к которым я уже был), чтобы гарантировать, что я не буду посещать один и тот же узел более одного раза и застревать в цикле. Но эта реализация заставляет меня застревать в цикле, потому что она возвращается после того, как она пытается с первым X, и она терпит неудачу, к неизмененному X, попадая в бесконечный цикл между теми же двумя узлами, которые могут достигать друг друга. Я знаю, что это легко исправить, добавив отрубов nocontains следующим образом:

% Does the work for notin(). 
nocontains([],_,A,A). 
nocontains([H|T],L,A,R):- 
    mycontains(L,H),!, 
    nocontains(T,L,A,R); 
    myappendelem(H,A,AR),!, 
    nocontains(T,L,AR,R). 

Но есть способ достичь того же без сокращений? Поэтому, когда я использую notin, я получаю только один возможный ответ? (его для школы, и часть задания, чтобы не использовать какие-либо встроенные предикаты или оператор управления)

Edit:

Просто чтобы быть более конкретными ограничения задания: Это должно состоят из чистых фактов и правил, нам не разрешено использовать какие-либо встроенные предикаты или структуры управления (включая, но не ограничиваясь, арифметику, порезы или отрицание как отказ). Точка с запятой в порядке. Любые предикаты полезности, необходимые нам, нужно определить сами.

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

Answer 1

Поскольку вы не можете использовать встроенные функции или структуры управления или разрезы, возможно, вопрос в том, что ответа нет. (То есть, возможно, точка вопроса, чтобы подчеркнуть необходимость отрицания-как-отказ или какой-либо эквивалент.)

(Кстати, ваше определение myappendelem фактически присоединяет этот элемент.)

Answer 2

Используйте Prolog система, которая поддерживает dif/2. Есть много таких систем, даже бесплатных.

dif/2 Используется для выражения чисто реляционным образом двух терминов: .

Например, в вашем случае, описывая, что элемент не членом списка:

not_in(_, []). 
not_in(L, [X|Xs]) :- 
     dif(L, X), 
     not_in(L, Xs). 

Или короче, используя maplist(dif(L), Ls).

Вы можете использовать это в вашем примере, как это:

?- Ls1 = [5,1], Ls2 = [4,3,2,1], member(M, Ls1), not_in(M, Ls2). 
Ls1 = [5, 1], 
Ls2 = [4, 3, 2, 1], 
M = 5 ; 
false. 

Обратите внимание, что это дает единственное решение M = 5.

Никаких порезов не требуется для выражения несоответствия сроков.

Answer 3

тривиальное, окольный способ сделать это:

?- setof(M, (member(M, L1), \+ member(M, L2)), Ms). 

который точно:

Сделать множество всех M таким образом, что M является членом L1, но не является членом L2.

?- L1 = [a,b,c,d,e,f,g], 
    L2 = [c,f,x,y], 
    setof(M, (member(M, L1), \+ member(M, L2)), Ms). 
Ms = [a, b, d, e, g]. 

Если вы не хотите, чтобы сделать упорядоченный набор, вы можете использовать bagof/3 вместо setof/3:

?- L1 = [c,b,a,c,b,a], 
    L2 = [c,y], 
    setof(M, (member(M, L1), \+ member(M, L2)), Ms). 
Ms = [a, b]. 

?- L1 = [c,b,a,c,b,a], 
    L2 = [c,y], 
    bagof(M, (member(M, L1), \+ member(M, L2)), Ms). 
Ms = [b, a, b, a]. 

Однако answer by @mat показывает, возможно, более логично звук способ выражения " элемент не в списке ", чем \+ member(M, L2).

Существуют также предикаты библиотеки, которые будут выполнять эту работу. Еще один эффективный способ борьбы с наборами, чтобы представить их в виде отсортированных списков без дублей, как в library(ordsets):.

?- L1 = [a,b,c,d,e,f,g,a,a,a], 
    L2 = [c,f,x,y], 
    time(setof(M, (member(M, L1), \+ member(M, L2)), Ms)). 
% 85 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 1841262 Lips) 
Ms = [a, b, d, e, g]. 

?- L1 = [a,b,c,d,e,f,g,a,a,a], 
    L2 = [c,f,x,y], 
    time((sort(L1, S1), 
      sort(L2, S2), 
      ord_subtract(S1, S2, S))). 
% 28 inferences, 0.000 CPU in 0.000 seconds (90% CPU, 1066545 Lips) 
S1 = [a, b, c, d, e, f, g], 
S = [a, b, d, e, g]. 

(В общем, меньше умозаключения означает меньше работу, чтобы доказать запрос Это однако бит, вводящий в заблуждение, когда участвует sort/2, поскольку он всегда учитывается как один вывод. В SWI-Prolog он использует встроенную реализацию C, и ее трудно сравнивать с чистым кодом Prolog. Также имейте в виду, что setof/3 использует внутреннюю часть sort/2.)

Answer 4

Если вы не можете использовать dif, или findall или setof или \+ или -> или даже ;, то вы можете использовать следующее, где элемент управления построен вокруг \=. Это по-прежнему отрицание как отказ (И так, например, существует внутренний невидимый разрез). Однако использование методов в других ответах и ​​встроенные системные предикаты - лучший способ.

my_member(I,[I|_]). 
my_member(I,[_|T]):- 
    my_member(I,T). 

notin(Test,List,Result):- 
    notin_(Test,List,[],[],Result). 

notin_([],_,_,Result,Result). 
notin_([H|T],List,AcIn,AcOut,Result):- 
    my_member(H,List), 
    notin_(T,List,[H|AcIn],AcOut,Result). 
    notin_([H|T],List,AcIn,AcOut,Result):- 
    not_member(H,List), 
    notin_(T,List,AcIn,[H|AcOut],Result). 

item_is_not_head(Item,[H|_]):- 
    H \= Item. 

not_member(_,[]). 
not_member(Item,List):- 
    List=[_|T], 
    item_is_not_head(Item,List), 
    not_member(Item,T). 

запросы:

?-notin([5,1],[4,3,2,1],X). 
X =[5], 
false. 

Но это даст вам ответы повторены. (Но, по крайней мере, они одинаковы).

?- notin([a,b,q,x,x,y],[a,b,q,d,a,a],R). 
    R = [y, x, x] ; 
    R = [y, x, x] ; 
    R = [y, x, x] ; 
    false.