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

Question

counter([],[]). counter([H|T],[[H,C1]|R]) :- counter(T,[[H,C]|R]),!, C1 is C+1. counter([H|T],[[H,1]|R]) :- counter(T,R). 

What is the effect of "!" how do I get the same output for input in both the above and below code?

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

I am new to Prolog.

Answer 1

What is the effect of "!"

Reducing reduces the search space. That is, in another, clean and monotonous program, the cut will delete some decisions or answers. While this is redundant, that’s good. It sounds so innocent and helpful, right? Let's get a look!

^{_{And so I don’t forget, using [E,Nr] to indicate pairs is pretty unusual, it's better to use an E-Nr pair.}}

Now we 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 !!! 

Thus, the cut version has fewer solutions. It seems that counter_cut/2 solution remains correct. In this very specific case. Will it always be right? 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 more frequent, and this time he is even a little right; 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 _cut better, and sometimes the _sans . Or put it more bluntly: both are wrong, but the _sans version at least includes all the solutions.

Here is a “cleaned” version that simply rewrites the last rule in two different cases: one for the end of the list, and the other for the other, another 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). 

In terms of efficiency, which is not too well known.

Here is a test case of efficiency for a system with efficient tree merging:

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

Instead, implementation should go smoothly, at least until the end of this universe. Strictly speaking, this query should cause a resource error, but only after it has counted a number much larger than 10^100000000 .

Answer 2

Here's my clean and hopefully effective solution:

 counter([X|L], C):- counter(L, X, 1, C). counter([],X, Cnt, [[X,Cnt]]). counter([Y|L], X, Cnt, [[X,Cnt]|C]):- dif(X, Y), counter(L, Y, 1, C). counter([X|L],X, Cnt, [[X,XCnt]|C]):- Cnt1 #= Cnt+1, Cnt1 #=< XCnt, counter(L, X, Cnt1, [[X,XCnt]|C]). 

---

Using if_3 , as suggested by @false:

 counter([X|L], C):- counter(L, X, 1, C). counter([],X, Cnt, [[X,Cnt]]). counter([Y|L], X, Cnt, [[X,XCnt]|C]):- if_(X=Y, ( Cnt1 #= Cnt+1, Cnt1 #=< XCnt, counter(L, X, Cnt1, [[X,XCnt]|C]) ), ( XCnt=Cnt, counter(L, Y, 1, C) ) ). 

Answer 3

Operator cut ! captures the current derivation path by trimming all selection points. Given some facts

 fact(a). fact(b). 

you can compare the answers without cutting:

 ?- fact(X). X = a ; X = b. ?- fact(X), !. X = a. 

As you can see, the general request now reports only its first success. However, the request

 ?- fact(b), !. true. 

succeeds. This means that the cut violates the interpretation as a logical conjunction:

 ?- X = b, fact(X), !. X = b. ?- fact(X), !, X=b. false. 

but from our understanding of the conjunction A ∧ B must be executed exactly when B ∧ A. holds. So why do this at all?

• Efficiency: cuts can be used so that they change only the properties of the execution, but not the answers of the predicate. These so-called "green cuts," for example, are described in Richard O'Keefe's book Craft of Prolog . As shown above, maintaining the correctness of a predicate with a cut is much more complicated than one without, but obviously, correctness must be achieved before efficiency.

  It looks like your problem was green, but I'm not 100% sure if there are no changes in the answers.

• Denial: logical negation in accordance with a closed world assumption is expressed by abbreviation. You can define neg (X) as:

   neg(X) :- call(X), !, false. neg(_) :- true. 

  So, if call(X) succeeds, we cut off the selection point for the second rule and print false. Otherwise, nothing is cut out, and we get the truth. Keep in mind that this is not a negation in classical logic and that it suffers from illogical cut effects. Assume that the predicate land/1 is one of the continents:

   land(africa). land(america). land(antarctica). land(asia). land(australia). land(europe). 

  and then define water as everything that is not on land:

   water(X) :- neg(land(X)). 

  then you can correctly get:

   ?- water(pacific). true. ?- water(africa). false. 

  But you can also get:

   ?- water(space). true. 

  which should not be executed. In particular, in classical logic:

   land(africa) ∧ land(america) ∧ land(antarctica) ∧ land(asia) ∧ land(australia) ∧ land(europe) → ¬ land(space). 

  not valid. Again, you should be well aware of what you are doing if you use negation in Prolog.

Answer 4

Here is my attempt using if_/3 :

 counter([], []). counter([H|T], [[H,C]|OutT] ):- if_( T=[], (C = 1,OutT=[]), ( [H|T] = [H,H1|T2], if_( H=H1, (counter([H1|T2], [[H1,C1]|OutT]), C is C1+1), (C = 1, counter([H1|T2], OutT)) ) ) ).