Prologue: how to avoid the reverse without cuts?

Question

So, I'm trying to write a predicate in a prolog that can take a list of L1 and a list of L2 and return a list of all the elements in L1 that are not in L2. This is what I still have:

% 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 because I use this predicate to sort the paths in the graph (L1 is the list of nodes that I could go to, and L2 are the nodes that I have already been to) to ensure that I will not visit the same same node more than once and get stuck in a loop. But this implementation makes me stuck in a loop because it returns after it tries with the first X, and it fails, to an unchanged X, falling into an infinite loop between the same two nodes that can reach each other. I know this is easy to fix by adding abbreviations for nocontains as follows:

 % 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 result without incisions? So when I use notin, do I get only one possible answer? (Its for school and part of the assignment is not to use any built-in predicates or control operators)

Edit:

To be more specific with regard to assignment restrictions: it must 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 - a-rejection). The semicolon is fine. Any utility predicates that we need must be determined by ourselves.

Thanks for all the answers, but I'm starting to think that this may be more of a problem with the method that I use to find the path between the two nodes in the graph, as the answers do not seem to have an easy way around this.

Answer 1

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

dif/2 used to express in a purely relational way two different terms.

For example, in your case, describing that an item 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 as follows:

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

Please note that this creates a unique M = 5 solution.

No cuts are required to express uneven timing.

Answer 2

Since you cannot use the built-in functions or control structures or abbreviations, perhaps the question is that there is no answer. (That is, perhaps the question is to emphasize the need for denial as failure or some equivalent.)

(By the way, your definition for myappendelem actually adds an element.)

Answer 3

A trivial, roundabout way to do this:

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

what 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 do not want to create 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 a more logical way of expressing "an item is not in the list" than \+ member(M, L2) .

There are also library predicates that would do the job. Another effective way to work with sets is to present 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, fewer conclusions mean less work done to prove the request. However, this is a little misleading when sort/2 involved, as it is always counted as one output. In SWI-Prolog, it uses the built-in C implementation, and it's hard to compare with pure Prolog code. Also keep in mind that setof/3 uses sort/2 internally.)

Answer 4

If you cannot use dif or findall or setof or \+ or -> or even ; then you can use the following where the control is built around \= . This is still denial as a failure (And so, for example, there is an internal invisible cut). However, using methods in other answers and built-in system predicates are the best way.

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

Inquiries

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