Lists and Cuts

Consider another maximum procedure, for determining, this time, the maximal number in a list of numbers.

Sometimes, also useful to change declarative semantics - to eliminate redundant computations. Consider definition 1 without the cut.

max( 0, []).
max( X, [X]).
max( X, [ X| Tail]) :-
  max( M, Tail),
  M =< X.
max( M, [ X| Tail]) :-
  max( M, Tail),
  M > X.

Problem : Maximal element will probably be have to be calculated twice if maximal element not in head of list.

Can change order of second and third clause - more efficient

Why is this more efficient ? More likely for maximal element to be in tail - however, STILL performing redundant computations.

Alternate definition with cut :

max2( 0, []).
max2( X, [X]).
max2 M, [X| Tail]) :- 
 max2( M, Tail),
 M >= X, !.
max2( X, [X | _]).

• If cut removed, the procedure would provide incorrect solutions through backtracking
• Position of last clause is important
• Order of third and fourth clauses in the procedure may now no be changed
• the cut in this case cannot be removed without affecting the procedural correctness - and is called a red cut.
• In the member definition above, however, the cut could be removed without affecting correctness of procedure (though it would reduce efficiency - that's why we are using it in the first place!) - and is called a green cut

Q: max(M,[2,4,5,6,7,23,23,5,4]
A: M = 23
M = 23
no more solutions

Oops - what happens with multiple elements !!

Q: max2(M,[2,4,5,6,7,23,23,5,4]
A: M = 23
no more solutions