Use cut in Prolog to define a once_member/2 function

Question

Disclaimer: This is informal and non-assessed coursework to do in my own time. I have tried it myself, failed and am now looking for some guidance.

I am trying to implement a version of the member/2 function which will only return members for a list once.

For example:

| ?- member(X, [1,2,3,1]).
X = 1 ? ;
X = 2 ? ;
X = 3 ? ;
X = 1 ? ;

I would like it to only print out each number a maximum of once.

| ?- once_member(X, [1,2,3,1]).
X = 1 ? ;
X = 2 ? ;
X = 3 ? ;
no

We have been told to do this with the cut '!' operator but I have looked over the notes for my course for cut and more online and yet still can't make it click in my head!

So far I have managed to get:

once_member(E, [E | L]) :- !.
once_member(E, [_, L]) :-
    once_member(E, L).

Which returns 1 and then nothing else, I feel like my cut is in the wrong place and preventing a backtrack for each possible match but I'm really not sure where to go with it next.

I have looked in my course notes and also at: http://www.cs.ubbcluj.ro/~csatol/log_funk/prolog/slides/5-cuts.pdf and Programming in Prolog (Google Books)

Guidance on how to logically apply the cut would be most useful, but the answer might help me figure that out myself.

We have also been told to do another method which uses '\+' negation by failure but hopefully this may be simpler once cut has twigged for me?

Housetop

Answer 1

Here's an approach that uses a cut in the definition of once_member/2 together with the classic member/2 predicate:

once_member(X,[H|T]) :-
    member(H,T),
    !,
    once_member(X,T).
once_member(H,[H|_]).
once_member(X,[_|T]) :-
    once_member(X,T).

Applied to the example above:

?- once_member(X,[1,2,3,1]).

X = 2 ;

X = 3 ;

X = 1 ;
no

Note: Despite the odd-appearing three clause definition, once_member/2 is last-call/tail-recursive optimization eligible due to the placement of the cut ahead of its first self-invocation.

Thorne

I'm marking this right as it seems to match most closely with what they were after (from reading the question). However the other answers also seemed really good especially thanosQR who provided loads of useful tips and info. Thanks all! – Housetop

In fact, one of my tests had this, just missing the old member/2 predicate hence why I was getting anomalies I think. – Housetop

Answer 2

Remove redundant answers and stay pure!

We define memberd/2 based on if_/3 and (=)/3:

memberd(X, [E|Es]) :-
   if_(X = E, true, memberd(X, Es)).

Particularly with meta-predicates, a different argument order may come in handy sometimes:

list_memberd(Es, X) :-
   memberd(X, Es).

Sample query:

?- memberd(X, [1,2,3,1]).
X = 1 ;
X = 2 ;
X = 3 ;
false.

Pilate

Now it only needs the efficiency to avoid the creation of unnecessary choice points! – Topsoil

That would be a CP within (=)/3. – Topsoil

It would be eliminated for all the relevant cases. And it would not be eliminated if there is no determinate way to produce a correct answer. That is =(X,Y,R) would succeed twice. – Topsoil

=(X,Y,R) succeds twice. Once with X = Y and once with dif(X, Y) – Topsoil

Answer 3

The solution with cut... at first it sounds quite troublesome.

Assuming that the first argument will be instantiated, a solution is trivial:

once_member(X,L):-
    member(X,L),!.

but this will not have the behavior you want if the first arg is not instantiated.
If we know the domain of the lists elements (for example numbers between 1 and 42) we could instantiate the first argument:

once_member(X,L):-
    between(1,42,X),
    member_(X,L).

member_(X,L):-
    member(X,L),!.

but this is veeery inefficient

at this point, I started to believe that it's not possible to do with just a cut (assuming that we dont use + or list_to_set/2
oh wait! < insert idea emoticon here >

If we could implement a predicate (like list_to_set/2 of swi-prolog) that would take a list and produce a list in which all the duplicate elements are removed we could simply use the normal member/2 and don't get duplicate results. Give it a try, I think that you will be able to write it yourself.

--------Spoilers------------

    one_member(X,L):-
        list_to_set(L,S),
        member(X,S).

    list_to_set([],[]).
    list_to_set([H|T],[H|S]):-
        remove_all(H,T,TT),
        list_to_set(TT,S).

%remove_all(X,L,S): S is L if we remove all instances of X
    remove_all(_,[],[]).
    remove_all(X,[X|T],TT):-
        remove_all(X,T,TT),!.
    remove_all(X,[H|T],[H|TT]):-
        remove_all(X,T,TT).

As you see we have to use a cut in remove_all/3 because otherwise the third clause can be matched by remove_all(X,[X|_],_) since we do not specify that H is different from X. I believe that the solution with not is trivial.

Btw, the solution with not could be characterized as more declarative than the solution with cut; the cut we used is typically called a red cut since it alters the behavior of the program. And there are other problems; note that, even with the cut, remove_all(1,[1,2],[1,2]) would succeed.

On the other hand it's not efficient to check twice for a condition. Therefore, the optimal would be to use the if-then-else structure (but I assume that you are not allowed to use it either; its implementation can be done with a cut).

On the other hand, there is another, easier implementation with not: you should not only check if X is member of the list but also if you have encountered it previously; so you will need an accumulator:

-------------Spoilers--------------------

once_member(X,L):-
    once_member(X,L,[]).
once_member(X,[X|_T],A):-
    \+once_member(X,A).
once_member(X,[H|T],A):-
    once_member(X,T,[H|A]).

Throw

Answer 4

once_member(X, Xs) :-
   sort(Xs, Ys),
   member(X, Ys).

Like almost all other solutions posted, this has some anomalies.

?- X = 1, once_member(X, [A,B]).
   X = A, A = 1
;  X = B, B = 1.

?- X = 1, once_member(X, [A,A]).
   X = A, A = 1.

Topsoil