/* 
		The effect of cuts in a Prolog program
	      -----------------------------------------
The cut is a pure control mechanism that is meant to prune the search
space when the programmer is sure that there are no solutions in the pruned
space.

Assume a clause of the form A :- B1, ...,Bk, !, Bk+1, ..., Bn

If ever the above clause becomes unified with a goal,

1. The cut prunes all clause below it. Hence no other clauses with head A
   that occur after this clause are ever considered. Hence any further 
   solutions that may be obtained from them are left out.

2. The cut prunes out all alternative solutions to the conjunction of goals
   that appear to its left in the clause (B1, ..., Bk). Hence a conjunctive
   goal followed by a cut will produce at most one solution.

3. The cut does not affect the solutions produced by goals to its right
   (Bk+1, ..., Bn). However, once this conjunction fails, the search proceeds
   from the last alternative prior to the clause that contained the cut. 

*/

max(X, Y, Y) :- X =< Y, !.
max(X, Y, X).

/* Declaratively speaking the cut has no logical meaning. But on the other
** it succeeds on the query max(2,5,2).
*/

/* A cut is most useful when it is used to express mutaully exclusive tests
   as the following merge program shows. Assume we want to merge 2 sorted lists
*/

merge(X.Xs, Y.Ys, X.Zs) :- X<Y, !, merge(Xs, Y.Ys, Zs).
merge(X.Xs, Y.Ys, X.Y.Zs) :- X=:=Y, !, merge(Xs, Ys, Zs).
merge(X.Xs, Y.Ys, Y.Zs) :- X>Y, !, merge(X.Xs, Ys, Zs).
merge(Xs, [], Xs).
merge([], Ys, Ys).

/* 
   Once it has been determined that X<Y holds it is no longer necessary
   to test whether X=:=Y or X>Y, and hence about two-thirds of the tree
   may be pruned out. However if X=:=Y then it si no longer necessary to 
   check whether X>Y hold sand hence about one-third of the tree gets pruned
   out. The search which failed the test X<Y however does not get pruned out.
*/