Prolog: how to avoid backtracking without cuts?

Question

So i am trying to write a predicate in prolog that can take a list L1 and a list L2 and return a list of all the elements in L1 that are not in L2. This is what i have so far:

% 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).

This works, however it gives more than one answer, for example:

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

This is a problem as i am using this predicate to sort out paths in a graph(L1 being the list of nodes i might go to, and L2 being the nodes i have already been to) to ensure that i wont visit the same node more than once and get stuck in a loop. But this implementation gets me stuck in a loop, because it backtracks after it tries with the first X and it fails, to the unaltered X, getting into an infinite loop between the same two nodes that can reach each other. I know this is easy to fix by adding cuts to nocontains like so:

% 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).

But is there a way to achieve the same without cuts? So when I use notin I get only one possible answer? (Its for school, and part of the assignment is to not use any built-in predicates or control operators)

Edit:

Just to be more specific on the limitations of the assignment: It should consist of pure facts and rules, we are not allowed to use any built-in predicates or control structures(including but not limited to arithmetic, cuts or negation-as-failure). Semicolon is okay. Any utility predicates needed we need to define ourselves.

Thanks for all the answers but I am starting to think that it might be more a problem with the method I use for finding a path between two nodes in a graph, as from the answers it doesn't look like there is an easy way around this.

Joaquinajoash

Even the semicolon is a control operator. Please state which ones are allowed then – Eimile

Tell your instructors to teach Prolog with a set of predicates that actually allow you to solve the tasks they give. To express that two terms are different in a purely relational way, use dif/2. In particular, using dif/2 lets you express what you need: An element that does not occur in a list. This does not require arithmetic, control structures (except (,)/2), cuts or negation-as-failure. – Lagos

Answer 1

Use a Prolog system that supports dif/2. There are many such systems, even free ones.

dif/2 is used to express, in a purely relational way, that two terms are different.

For example, in your case, describing that an element is not a member of a list:

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

Or shorter, using maplist(dif(L), Ls).

You can use this in your example like this:

?- 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.

Note that this produces the unique solution M=5.

No cuts are necessary to express term disequality.

Lagos

Answer 2

Since you cannot use builtins or control structures or cuts, maybe the point of the question is that there is no answer. (That is, perhaps the point of the question is to highlight the need for some way to express negation, e.g as negation as failure or disequality.)

(Incidentally, your definition for myappendelem actually prepends the element.)

Meli

Answer 3

The trivial, roundabout way to do it:

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

which is exactly:

Make a set of all M such that M is a member of L1 but not a member of 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].

If you don't want to make an ordered set, you can use bagof/3 instead of 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].

However, the answer by @mat shows an arguably more logically sound way of expressing "element not in list" than \+ member(M, L2).

There are also library predicates that would do the job. One more efficient way of dealing with sets is to represent them as sorted lists without duplicates, as in 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].

(In general, less inferences means less work done to prove the query. This is however a bit misleading when sort/2 is involved, as it always counts as one inference. In SWI-Prolog, it uses a native C implementation, and it is difficult to compare to pure Prolog code. Also, keep in mind that setof/3 uses a sort/2 internally.)

Anastasius

Cuts are bad if used incorrectly, and good if used correctly. Their subtlety takes a while to learn. Not all parts of a program are, or have to be, pure. I could have used cuts instead of swi-prolog.org/pldoc/man?predicate=-%3E/2 – Reams

Answer 4

If you cant use dif, or findall or setof or \+ or-> or even ; then you can use the following where the control is built around \=. This still is negation as failure (And so like dif there is an internal invisible cut). Using methods in others answers and built in system predicates is a better way though.

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).

Queries:

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

But it will give you repeated answers. (But at least they are the same).

  ?- 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.

Disinterest

This would probably work, there would be some redundant checks with the duplicate results but at least it wouldn't get stuck in a loop, but we are not allowed to use negation-as-failure either. Maybe my method of finding a path between two nodes in a graph is the problem.... :/ – Joaquinajoash

I think its impossible. At some point you need to check if an element is NOT a part of a list. This means you need negation, which in prolog means negations as failure. my_member2(Key, [Key| T], true). my_member2(_Key, [], false). my_member2(Key, [_|Tail], X) :- my_member(Key, Tail, X). This returns true then back tracks to false.. my_member(a,[a,b,c],TF). TF = true; TF= false; false. – Disinterest