/*
COSC3308  PROLOG Example-3
          List Processing        12/7/2003
*/
domains
  list,state=integer*
  element = integer
predicates
  first (state,element)
  equal1(integer,integer)
  equal2(integer,integer)
  mem(element,list)
  notmem (element,list)
  append(list,list,list)
  sort(list,list)
  insert(element,list,list)
  reverse(list,list)
  reverse2(list,list,list)
  rev(list,list)
  max(list,element)
  delete (element,list,list)
  deleteone (element,list,list)
  run1()
  run2()
  run3
  removeAll (list,list)
  remove (list,list,list,list)
clauses  
  first([First|_],First).  %% A CUT would be redundant here.
  equal1(X,Y) :- X=10, X=Y.	%% Y(RHS) is yet to be bound.
  equal2(X,Y) :- X=10, Y=X.  
  mem (X, [X|_]) 	:- !.	%% Without this CUT,
  		%% mem(X,[1,2,3]) will produce 3 solutions.
  mem (X, [_|T]) :- mem(X,T).
  notmem (M,L)  if  mem(M,L),  !,  fail.
  notmem (_,_).
  append ([], L, L)  :- !.  %% A CUT will prevent multiple solutions for following:
  		%% append(X,Y,[1,2,3,4]) will produce 5 solutions
  append ([H|T], L, [H|Result]) :- 
  		append(T,L,Result).    
  sort ([],[])		:- !.
  sort ([H|T], R)	:- sort(T,R1), 
  			   insert(H,R1,R).
  insert (N, [], [N])	:- !.
  insert (N, [H|T], [N,H|T])	:- N=H,
  				   insert(N,T,R).
  reverse (L,R)		:- reverse2(L,[],R), !.
  reverse2([],R,R)	:- !.
  reverse2([H|T],L,R)	:- reverse2(T,[H|L],R).
  rev ([H|[]], [H]).	%% rev([],YY) will fail
  			%% while reverse([],YY) succeeds.
  rev ([H|T], R)	:- rev(T,R1),
  			   append(R1, [H], R).
  max ([H|[]], H).  	%% The list has only one element.
  max ([H|T], H)	:- max(T,M), H>M, !.	%% Redundant Cut here.	
  	%% This CUT prevents multiple solutions for max([6,5,4,3],R)
  max ([_|T], M)	:- max(T,M).    %% M>=_.
  delete (_,[],[]).
  delete (X, [X|Tail], Answer) :-
  		delete(X, Tail, Answer).
  delete (X, [Y|Tail], [Y|Answer]) :-
  	  X<>Y, delete(X, Tail, Answer).
  deleteone (_,[],[]).
  deleteone (X, [X|Tail], Tail)	:- !. %% Done
  deleteone (X, [Y|Tail], [Y|Answer])
   	:- deleteone(X, Tail, Answer).
  removeAll(L,R)	:- remove(L,[],_,R).
  remove ([],D,D,[])	:- !.
  remove ([H|T], [], D, R) 	:- 
  		remove(T,[H],D,R),!.
  remove ([H|T], D, DD, [H|R])	:- 
  		mem(H,D), remove(T,D,DD,R),!.
  remove ([H|T], D, DD, R)	:-
  		not(mem(H,D)), remove(T, [H|D],DD,R).
  run1		:- rev([1,2,3],R),
  		   write (R).
  run2		:- sort([100, 200, 4,5,3,2,1],R),
  		   write(R).
  run3		:- L = [10,20,30,40,50,60,70,20,30,20,80,90,40,20,100],
  		   removeAll (L,N),
  		   write(N).
 
 /* When trace is enabled, the Trace Window will show four actions taken.
      Call
      Redo (When a call made already needs to be  reattempted by other clauses
            of the same Predicate.)
      Fail (When the last Call (or Last Redo) does not succeed for good)
      Return (When the last call is found to be satisfied and hence done).
     
      
      Example: Suppose that the following goal is given for tracing:
      	       insert(3, [1,2], R)

	CALL:		insert (3, [1,2], _)
	REDO:		Same as above
			3<1
	FAIL:		Same as above
	REDO:		Same as above
			3>=1
	CALL:		insert (3, [2], _)
	REDO:		Same as above
			3<2
	FAIL:		Same as above
	REDO:		Same
			3>=2
	CALL:		insert (3, [], _)
	RETURN:		insert (3, [], [3])	// First return as 2nd argument
						// is finally []
	RETURN:		insert (3, [2], [2,3])
	RETURN:		insert (3, [1,2], [1,2,3])
	
	// End of tracing	//        		   
 */