What is the difference in execution if the cut '!' is present?

prolog, prolog-cut

Solution

What is the effect of the "!"

The cut prunes the search space. That is, in an otherwise pure and monotonic program, the cut will remove some solutions or answers. As long as those are redundant that's fine. It sounds so innocent and useful, doesn't it? Let's have a look!

And lest I forget, using `[E,Nr]` to denote pairs is rather unusual, better use a pair `E-Nr`.

We will now compare `counter_cut/2` and `counter_sans/2`.

| ?- counter_cut([a,a],Xs).
     Xs = [[a,2]].

| ?- counter_sans([a,a],Xs).
     Xs = [[a, 2]]
  ;  Xs = [[a, 1], [a, 1]].     % <<< surprise !!!

So the cut-version has fewer solutions. Seems the solution `counter_cut/2` retained is the right one. In this very particular case. Will it always take the right one? I will try a minimally more general query:

| ?- counter_cut([a,B],Xs).
     B = a,
     Xs = [[a, 2]].

| ?- counter_sans([a,B],Xs).
     B = a,
     Xs = [[a, 2]]
  ;  Xs = [[a, 1], [B, 1]].

Again, `_sans` is chattier, and this time, it is even a bit right-er; for the last answer includes `B = b`. In other words,

| ?- counter_cut([a,B], Xs), B = b.
     fails.              % incomplete !

| ?- counter_sans([a,B], Xs), B = b.
     B = b,
     Xs = [[a,1],[b,1]].

So sometimes the `_cut` version is better, and sometimes `_sans`. Or to put more directly: Both are wrong somehow, but the `_sans`-version at least includes all solutions.

Here is a "purified" version, that simply rewrites the last rule into two different cases: One for the end of the list and the other for a further, different element.

counter_pure([],[]).
counter_pure([H|T],[[H,C1]|R]) :- counter_pure(T,[[H,C]|R]), C1 is C+1.
counter_pure([H],[[H,1]]).
counter_pure([H,D|T],[[H,1]|R]) :- dif(H,D), counter_pure([D|T],R).

From an efficiency viewpoint that is not too famous.

Here is a test case for efficiency for a system with rational tree unification:

?- Es = [e|Es], counter(Es, Dict).
resource_error(stack).

Instead, the implementation should loop smoothly, at least till the end of this universe. Strictly speaking, that query has to produce a resource error, but only after it has counted up to a number much larger than `10^100000000`.

Problem

Original source