% CPSC 312 March 2021
% Copyright D Poole 2021. Released on liscence: https://creativecommons.org/licenses/by-nc-sa/4.0/
% diff(E,X,DE) is true if DE is the derivative of E with respect to X
diff(X,X,1).
diff(C,X,0) :- atomic(C), dif(C,X).
diff(A+B,X,DA+DB) :-
diff(A,X,DA),
diff(B,X,DB).
diff(A*B,X,A*DB+B*DA) :-
diff(A,X,DA),
diff(B,X,DB).
% an so on for other arithmetic operators
diff(sin(E),X,cos(E)*DE) :-
diff(E,X,DE).
diff(cos(E),X,-sin(E)*DE) :-
diff(E,X,DE).
diff(exp(E),X,exp(E)*DE) :-
diff(E,X,DE).
% Try:
%?- diff(x+3*x+6*x*y, x, D).
%?- diff(7+3*x+6*x*y, x, D).
%?- diff(x+3*x+6*x*y+ 11*x*x, x, D).
%simplify(Exp, Exp2) is true if expression Exp2 is a simplified for Exp
simplify(X,X) :-
atomic(X).
simplify((A+B),V) :-
simplify(A, VA),
simplify(B, VB),
simp_vals(VA+VB, V).
simplify((A*B),V) :-
simplify(A, VA),
simplify(B, VB),
simp_vals(VA*VB, V).
%simplify_vals(Exp, Exp2) is true if expression Exp simplifies to Exp2,
% where the arguments to Exp have already been simplified
simp_vals(0+V,V).
simp_vals(V+0,V).
simp_vals(A+B,AB) :-
number(A),number(B),
AB is A+B.
simp_vals(A+B,A+B).
simp_vals(0*_,0).
simp_vals(_*0,0).
simp_vals(V*1,V).
simp_vals(1*V,V).
simp_vals(A*B,AB) :-
number(A),number(B),
AB is A*B.
simp_vals(A*B,A*B).
% try:
%?- simplify(y*1+(0*x + x*0),E).
%?- simplify(y*(2*10+3),E).
%?- simplify(1+ (3*1+x*0)+ (6*x*0+y* (6*1+x*0))+ (11*x*1+x* (11*1+x*0)), E).
%?- diff(x+3*x+6*x*y+ 11*x*x, x, D), simplfy(D,E).
%%%%%% Dutch Flag %%%%%%%%%
% for testing, here is a definition of the colour of numbers
red(E) :- E < 10.
white(10).
blue(E) :- E>10.
% dutch_flag(L,D) is true if D conatins the elements of L where,
% the red elements are before the white elements, which are before the blue elements.
dutch_flag(L,D):-
partn(L,R,W,B),
append(R,W,RW),
append(RW,B,D).
% partn(L,R,W,B) is true when
% R contains the elements of L that are red
% W contains the elements of L that are white
% B contains the elements of L that are blue
partn([],[],[],[]).
partn([H|T],[H|R],W,B) :- red(H), partn(T,R,W,B).
partn([H|T],R,[H|W],B) :- white(H), partn(T,R,W,B).
partn([H|T],R,W,[H|B]) :- blue(H), partn(T,R,W,B).
%:- dutch_flag([4,9,17,3,88,10,33,0],D).
% dutch flag with difference lists
dutch_flag_dl(L,R):-
partn_dl(L,R,W,W,B,B,[]).
%partn_dl(L,R1,R2,W1,W2,B1,B2) is true when
% R1-R2 contains elements of L that are red
% W1-W2 contains elements of L that are white
% B1-B2 contains elements of L that are blue
partn_dl([],R,R,W,W,B,B).
partn_dl([H|T],[H|R1],R2,W1,W2,B1,B2) :- red(H), partn_dl(T,R1,R2,W1,W2,B1,B2).
partn_dl([H|T],R1,R2,[H|W1],W2,B1,B2) :- white(H), partn_dl(T,R1,R2,W1,W2,B1,B2).
partn_dl([H|T],R1,R2,W1,W2,[H|B1],B2) :- blue(H), partn_dl(T,R1,R2,W1,W2,B1,B2).
% Try:
%:- dutch_flag_dl([4,9,17,3,88,10,33,0],D).
% Note: this can be made simpler by noticing that B2 is always [] and so can be removed.
% This is equivaent to treating B as a regular (not difference) list.
% The advantage of the origical format is that it is easy to reorder the colours.
% reversing dutch flag with difference lists
% rev_dutch_flag(L,D) is true if D conatins the elements of L where,
% the red elements are before the white elements, which are before the blue elements.
% the elements in each colour group are in reverse order than they are in L
rev_dutch_flag_dl(L,R):-
rev_partn_dl(L,R,W,W,B,B,[]).
%rev_partn_dl(L,R1,R2,W1,W2,B1,B2) is true when
% R1-R2 contains elements of L that are red in reverse order
% W1-W2 contains elements of L that are white in reverse order
% B1-B2 contains elements of L that are blue in reverse order
rev_partn_dl([],R,R,W,W,B,B).
rev_partn_dl([H|T],R1,R2,W1,W2,B1,B2) :- red(H), rev_partn_dl(T,R1,[H|R2],W1,W2,B1,B2).
rev_partn_dl([H|T],R1,R2,W1,W2,B1,B2) :- white(H), rev_partn_dl(T,R1,R2,W1,[H|W2],B1,B2).
rev_partn_dl([H|T],R1,R2,W1,W2,B1,B2) :- blue(H), rev_partn_dl(T,R1,R2,W1,W2,B1,[H|B2]).
% Try:
%:- rev_dutch_flag_dl([4,9,17,3,88,10,33,0],D).