why does it make sense to use a cut when a predicate backtracks into the same solution?

EDIT (since OP insisted 😉

I am answering this question:

What am I gaining and losing from a use of a cut in the above code?

I am not sure what you are gaining. You are losing the ability to ask more general questions that you get for free if you do not use cuts in your code.

In the general case, getting the same correct solution more than once is a strong indication that your code, with or without cuts, is either redundant or plain wrong. This is not universally true of course but from experience, it is true often enough.


You shouldn’t “avoid cuts like the plague”. You should use cuts when you need them, and not use them when you don’t need them.

This is too big of a topic to answer on SO. Every decent Prolog textbook explains cuts and discusses when you need them and why; and use your judgement, which will improve as you program.

However: if your program is incorrect without cuts, cuts will not fix it.


Consider those problems.

  1. Given two boolean vectors, what is their dot product?

  2. Implement a predicate with three arguments. The first two arguments are boolean vectors, and the third argument is the dot product.

In Prolog-land, the second problem assumes that you can ask questions like “given one vector and a dot product, what is the other vector?” Can either one of your current implementations do that? And are you going to ask such questions? And even if you didn’t think you are going to ask such question, given that you could do it, could you come up with uses for it? Do you see where this is going?


Now, your code. There are issues with it (see for example the comment that Isabelle Newbie just made).

This does not give wrong results:

:- module(boolean, [add/3, mult/3, dot_product/3]).

add(1,1,1).
add(1,0,1).
add(0,1,1).
add(0,0,0).

mult(1,1,1).
mult(1,0,0).
mult(0,1,0).
mult(0,0,0).

dot_product(V1, V2, P) :-
    same_length(V1, V2),
    maplist(mult, V1, V2, [H|T]),
    foldl(add, T, H, P).

Using it:

?- use_module(boolean).
true.

?- dot_product([1,0,1],[1,1,1],P).
P = 1 ;
false.

?- dot_product([1, 1], [1, 0], Product).
Product = 1 ;
false.

?- dot_product([1, 1], V2, 1).
V2 = [1, 1] ;
V2 = [1, 0] ;
V2 = [0, 1] ;
false.

?- dot_product(V1, V2, 1).
V1 = V2, V2 = [1] ;
V1 = V2, V2 = [1, 1] ;
V1 = [1, 1],
V2 = [1, 0] ;
V1 = [1, 0],
V2 = [1, 1] ;
V1 = V2, V2 = [1, 0] ;
V1 = [1, 1],
V2 = [0, 1] ;
V1 = [0, 1],
V2 = [1, 1] ;
V1 = V2, V2 = [0, 1] ;
V1 = V2, V2 = [1, 1, 1] ;
V1 = [1, 1, 1],
V2 = [1, 1, 0] .

?- dot_product(V1, V2, P).
V1 = V2, V2 = [1],
P = 1 ;
V1 = [1],
V2 = [0],
P = 0 ;
V1 = [0],
V2 = [1],
P = 0 ;
V1 = V2, V2 = [0],
P = 0 ;
V1 = V2, V2 = [1, 1],
P = 1 ;
V1 = [1, 1],
V2 = [1, 0],
P = 1 ;
V1 = [1, 0],
V2 = [1, 1],
P = 1 .

EDIT2: There is still a choice point left after the last correct answer. To get rid of it, you can use tabling (as available in SWI-Prolog, for example). Make both add/3 and mult/3 tables, like this (before defining them):

:- table add/3, mult/3.

No more “false”s:

?- dot_product([1,0,1],[1,1,1],P).
P = 1.

?- dot_product(V1, [1, 0], 0).
V1 = [0, 1] ;
V1 = [0, 0].

The “same length” seems important enough; since there are no cuts, you can use the predicate to “generate-and-test”. Anyway, dot product is only defined for vectors of the same length, isn’t that so?

I made no attempt at optimizing the code. As you observe in your question, you can short-cut if the arguments are ground. This would be a good use of a cut (or an if-then-else): if arguments are ground, look for any “1” in any of the vectors; otherwise, use generic algorithm.

To check for “1” in a ground list, you could use memberchk(1, List).

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top