/*
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 //
*/