Prolog - understandig the use of cut

Question

I can't understand clearly the use of cut. For example in this case: flatten, is it really needed? It works for me even without both cut predicates (I tried removing). What are the cases that can cause the backtracking going to the cut? Removing the cuts you have the same implementation of the book "The art of prolog" (Shapiro E.,Sterling L.) that is:

flatten([X|Xs],Ys) :-
    flatten(X,Ysl), 
    flatten(Xs,Ys2), 
    append(Ys1,Ys2,Ys).
flatten(X,[X]) :- 
    constant(X), 
    X\=[].
flatten([],[]).

which leads me to another question: is it necessary in the second clause to check if it's not a list? If it's a single term won't unify with the first clause...isn't it?

Answer 1

The program linked in your question uses cut ! operator to prevent the code in the answer from unifying with other clauses. Without these cuts flatten2/2 from the answer would unify an empty list in the first argument with clauses one and three, i.e.

flatten2([], []) :- !.
flatten2(L, [L]).

Similarly, without a cut in the second clause flatten2/2 would unify a non-empty list in clauses two and three, leading to incorrect behavior.

Your code, on the other hand, has explicit checks to ensure that each clause of flatten/2 deals with one specific situation:

• First clause recursively flattens non-empty lists
• Second clause makes a single-item list from constants other than empty lists
• Third clause "flattens" empty lists.

Since each clause applies exclusively to a single type of item on the left, the cut is not necessary. You could have rewritten your code with a cut by switching the second and the third clause, and adding a cut after matching an empty list, but I would strongly recommend against doing this (demo).

is it necessary in the second clause to check if it's not a list?

This check is necessary because an empty list [] is considered a constant, so your program would have incorrect behavior when empty lists are present in the list being flattened (demo).