Why do we use '!' in prolog

Question

This is the code that i am trying to understand.

co(X) :- co(X,[],L).
co([],A,A):- write(A).
co([X|Xs], A, L) :- p(X-Z,A,R), !, Z1 is Z+1, co(Xs, [X-Z1|R], L). 
co([X|Xs], A, L) :- co(Xs, [X-1|A], L). 

p(X-Y,[X-Y|R],R):- !.
p(X,[H|Y], [H|Z]) :- p(X,Y,Z).

What is the use of '!' and predicate p(,,) in the above code. OR Can anybody just add comments in every step of the above code so that i can able to understand . Thanks.

Answer 1

Beginners tend to use !/0 because they are not aware of its negative consequences.

This is because most Prolog textbooks that are popular among beginners are quite bad and often contain wrong and misleading information about !/0.

There is an excellent answer by @false on when to use !/0. In summary: don't.

Instead, focus on a declarative description about what holds, and try to make the description elegant and general using pure and monotonic methods like constraints, clean representations, ...

Answer 2

There are many things to address in your program. Cuts are not even the major concern. Please, bring me the broom.

Clean up the interface

What is the precise interface you are after? The purpose of co(Xs) currently, is to produce a side effect. Otherwise it can succeed or fail for a given list. But not more than that. Yet, this side effect is not at all needed - and is for most situations not a helpful approach, since such a program is practically unreusable and defies any logical reasoning. You need to leave a hole to let some result lurk out of the relation. Add another argument and remove the goal write/1 in co/3.

co(Xs, D) :-
   co(Xs, [], D).

Now you can test the program with the top-level shell alone. You do not need any harness or sandbox to check for the "output". It is there, readily in a separate argument.

Clean up the program structure

Next is co/3 itself. Here, the best is to clarify the intention by separating a bit the concerns, and making these extra arguments a bit more intention-revealing. D stands for dictionary. Another good name would be KVs meaning list (the plural s) of key-value pairs. Note how the different states are numbered: They start with D0, D1, ... and at the end there is D. In this manner, if you start to write a rule, you can put D0,D already in the head without knowing how many states you will need in that rule.

co([], D,D).
co([X|Xs], D0,D) :-
   nn(X, D0,D1),
   co(Xs, D1,D).

nn(K, D0,D) :-
   p(K-V0,D0,D1), !,
   V is V0+1,
   D = [X-V|D1].
nn(K, D0,D) :-
   D = [K-1|D0].

p(X-Y,[X-Y|R],R):- !.
p(X,[H|Y], [H|Z]) :- p(X,Y,Z).

co/3 now more clearly reveals its intention. It somehow relates the elements of a list to some state that is "updated" for each element. There is a word for this: This is a left-fold. And there is even a predicate for it: foldl/4. So we could equally define co/3 as:

co(Xs, D0,D) :-
   foldl(nn, Xs, D0,D).

or better get rid of co/3 altogether:

co(Xs, D) :-
   foldl(nn, Xs, [], D).

foldl(_C_3, [], S,S).
foldl(C_3, [X|Xs], S0,S) :-
   call(C_3, X, S0,S1),
   foldl(C_3, Xs, S1,S).

Note, that so far, I have not even touched any cuts of yours, these are now their last moments...

Remover superfluous cuts

The cut in p/3 does not serve any purpose. There is a cut immediately after the goal p/3 anyway. Then, X-Y is not needed in p/3, you can safely replace it by another variable. In short, p/3 is now the predicate select/3 from the Prolog prologue.

select(E, [E|Xs], Xs).
select(E, [X|Xs], [X|Ys]) :-
   select(E, Xs, Ys).

nn(K, D0,D) :-
   select(K-V0, D0,D1), !,
   V is V0+1,
   D = [K-V|D1].
nn(K, D0,D) :-
   D = [K-1|D0].

This one remaining cut cannot be removed so easily: it protects the alternate clause from being used should K-V not occur in D. However, there are still better ways to express this.

Replace cuts with (\+)/1

nn(K, D0,D) :-
   select(K-V0, D0,D1),
   V is V0+1,
   D = [K-V|D1].
nn(K, D0,D) :-
   \+select(K-_, D0,_),
   D = [K-1|D0].

Now, each rule states what it wants for itself. This means, that we can now freely change the order of those rules. Call it superstition, but I prefer:

nn(K, D0,D) :-
   \+select(K-_, D0,_),
   D = [K-1|D0].
nn(K, D0,D) :-
   select(K-V0, D0,D1),
   V is V0+1,
   D = [K-V|D1].

Purify with dif/2

To make this into a true relation, we need to get rid of this negation. Instead of saying, that there is no solution, we can instead demand that all keys (key is the first argument in Key-Value) are different to K.

nokey(_K, []).
nokey(K, [Kx-|KVs]) :-
   dif(K, Kx),
   nokey(K, KVs).

nn(K, D,[K-1|D]) :-
   nokey(K, D).
nn(K, D0,[K-V|D]) :-
   select(K-V0, D0,D),
   V is V0+1.

With the help of lambdas, nokey(K, D) becomes maplist(K+\(Kx-_)^dif(Kx,K), D)

To summarize, we have now:

co(Xs, D) :-
   foldl(nn, Xs, [], D).

nn(K, D,[K-1|D]) :-
   maplist(K+\(Kx-_)^dif(Kx,K), D).
nn(K, D0,[K-V|D]) :-
   select(K-V0, D0,D),
   V is V0+1.

So what is this relation about: The first argument is a list, and the second argument a Key-Value list, with each element and the number of occurrences in the list.