3

I have the following rule:

noRepetition([]).
noRepetition([Elem|Rest]):- not(member(Elem,Rest)), !, noRepetition(Rest).

This rule is made to decide if a list has no repeating elements in it and the member rule decides if a particular element belongs to a list. My question is relating to the cut operator in this rule as I am not sure what it does.

I have drawn up the following trace for ?-noRepetition([a,b,b,c,d]) and have run across a problem(probably relating to my lack of understanding of the cut operator):

?-noRepetition([a,b,b,c,d])
Unfies with the second noRepetion rule and instantiates variables to:
noRepetition([a|b,b,c,d] :- not(member(a,[b,b,c,d])), !, noRepetition([b,b,c,d]).

Now I am stuck as not member returns true in this case thus the cut is proven true, however I am not sure if this cut prevents the program from going to noRepetition(the 3rd goal) or if it does something else. If it indeed prevents the program from going to noRepetition then this rule would be evaluated to true, which is not the case as there is repetition in the list.

false
  • 10,264
  • 13
  • 101
  • 209
JmanxC
  • 377
  • 2
  • 16

2 Answers2

4

To your question. My opinion: the cut is unnecessary. You might want to refresh your memory on what the cut does; here is a short summary. A good rule of thumb is to look at the last goal before the cut and try to see if it it leaves choice points behind. If it does, then they are all thrown away (along with all choice points from earlier goals within this clause body) and you are left with the first solution only. So we look at:

\+ member(Elem, Rest) % just another way to say not...

When can this leave behind a choice point? \+ Goal is true if Goal is false, false otherwise. As far as I am aware, \+ Goal can never be true more than once, nor can it be false more than once. So why do you need the cut? It is in this situation superfluous and in fact does nothing at all.

(I'd still like to know why did you put the cut there in the first place. Was there a similar predicate that did not use the negation on member/2?)

Offering better solutions is frowned upon by askers, but there are at least two other ways to solve this problem. You can even mash them up together for the following definition:

all_dif_list(L) :-
    (   ground(L)
    ->  sort(L, S),
        length(L, N),
        length(S, N)
    ;   all_dif_list_nonground(L)
    ).

all_dif_list_nonground([]).
all_dif_list_nonground([X|Xs]) :-
    maplist(dif(X), Xs),
    all_dif_list_nonground(Xs).

If you know that the list is fully instantiated, you can just sort it, and compare lengths. sort/2 removes duplicates so if there were repetitions, the sorted list would be shorter.

If the list contains variables, the safe thing to do would be to just say that each pair of elements in the list are (and will always be) different.

And keep in mind that member/2 is more complicated than its simple name and straight-forward definition suggest. I could easily write a 1000 word essay on the behavior of member/2 if I thought I'd benefit from that.

Community
  • 1
  • 1
  • Thank You for the quick response. That rule actually comes from a set of rules my teacher posted for an assignment. His member was written as such:member(X, [X|_]). member(X, [_|Rest]) :- member(X, Rest). I tried to trace it but I did not understand what the cut did at all. If I were to use the rule given,however, it does the third goal first, then attempts the cut? Sorry for everything being on one line,not sure how to edit comments on here. – JmanxC May 20 '16 at 23:23
  • @JmanxC Did you try to remove the cut and see if there is _any_ difference to the result you are getting? –  May 20 '16 at 23:28
  • @JmanxC Both in your question and your comment you talk about "third goal" and I have no idea what you are referring to.... :( –  May 20 '16 at 23:30
  • Oh sorry, by "third goal" i meant the third argument in the rule. So the recursive call to noRepetition(after the cut). Interestingly enough,removing the cut seems to exhibit the same behavior as if it was there. That is sort of interesting... I do understand the operator cut when its found at the end of a rule. That is so it doesn't backtrack to any other predicate with the same name after the first is resolved to be true. When a cut is in the middle of the rule,however, as it is in this example, I find it confusing as I am not sure how the cut works here. – JmanxC May 20 '16 at 23:56
  • @JmanxC Did you actually read my answer? I am quite certain that the cut does nothing. Altogether, this code very much looks like it is written by someone who is not entirely up to date with Prolog programming. –  May 21 '16 at 05:45
  • Nice 'n' neat! Exchanging the two length goals will help (minimally). – false May 21 '16 at 08:21
  • However, there is still one issue - I admit it is out of scope of the standard. Yet, your implementation may incorrectly succeed, when it should actually fail. I have not constructed such a case, but I am quite sure it exists! – false May 21 '16 at 08:22
  • Yes I did read your answer. Regarding this particular problem I am aware that removing the cut does not change the rule itself. My question more relates to how cut works in situations where you have head:-goal1,!,goal2. I am not sure how the cut works when you put it in the middle of two goals like that.It does make sense when you put it at the end(ie: head:- goal1,goal2,!.) as it just means that if this rule is evaluated true, it does not check any other cases. – JmanxC May 21 '16 at 17:39
  • However, when it is in the middle like that, I am not sure which goal it evaluates to be true or false or what it is cutting out. Hope this question makes sense. – JmanxC May 21 '16 at 17:39
  • @JmanxC Hm, starting to understand what you are asking. The problem with your example as it stands is that the cut does nothing at all, so it is a useless example to discuss the cut. It seems to me that the first paragraph explains what the cut does, but if it really doesn't, I suggest you ask a new question that asks exactly what you want to know, and use a better example. –  May 21 '16 at 18:42
0
noRepetition([]).
noRepetition([Item|Rest]) :- member(Item,Rest), !, fail.
noRepetition([_|Rest]) :- noRepetition(Rest).

Note: result may be unexpected if Item is not a ground term. For example:

noRepetition([X,a,b]).

will fail...

zebollo
  • 1