/* -*-prolog-*- */

/* このプログラムでは
   「単項式」とは3*xやy*zやx*(y*3)*zのような、
   数とアトム(xやyなど)と*と括弧だけからなる式をいい、
   「多項式」とは3*x+y*zのような、単項式と+だけからなる式をいう */

/* このプログラムは、数とアトムと+と*と括弧からなる式を与えて
   それを展開した多項式を得るためのもの。
   例えば ?-tenkai_and_seiri((x+y)*(x+y),X). とすると
   X = x*x+2*x*y+y*y を得る
   引き算はないので、-1との積で代用する
   例えば ?-tenkai_and_seiri((x+y)*(x+(-1)*y),X). とすると
   X = x*x+ -1*y*y を得る */
/* SWISHで動かす場合は、タブを開いてこのプログラムをカット&ペーストし、
   画面右下queryのところに tenkai_and_seiri((x+y)*(x+y),X). と入力して
   Runをクリック */

/* このような「記号をデータとして扱うプログラム」(記号処理)は、Prologが
   得意とする分野の1つです */

/* 単項式の定義。引数が単項式ならtrue */
tankou(X) :- atom(X).
tankou(X) :- number(X).
tankou(X*Y) :- tankou(X), tankou(Y).

/* 多項式の定義。引数が多項式ならtrue */
takou(X) :- tankou(X).
takou(X+Y) :- takou(X), takou(Y).

/* 第1引数に+と*と括弧からなる式を与え、
   それを分配法則によって展開して得た多項式を第2引数に代入する
   分配法則を適用するだけで、同類項のまとめなどはしない
   例えば第1引数がx*(y+z)の場合、第2引数にはx*y+x*zを得る
   第1引数が(x+y)*(x+y)の場合、第2引数にはx*x+x*y+(y*x+y*y)を得る */
tenkai(X,X) :- tankou(X).
tenkai(X1+X2,Y1+Y2) :-
	tenkai(X1,Y1), tenkai(X2,Y2).
tenkai(X1*X2,Y) :-
	tankou(X1), \+tankou(X2),
	/* X1とX2の両方が単項式の場合は最初の節が適用されるので、ここでは
	   その場合は排除 */
	tenkai(X2,Z1+Z2),
	tenkai(X1*Z1+X1*Z2,Y).
tenkai(X1*X2,Y) :-
	\+tankou(X1),
	tenkai(X1,Z1+Z2),
	tenkai(Z1*X2+Z2*X2,Y).

/* 第1引数にa*3*c*b*2のような単項式を与え、それを分解して、
   [[a,c,b],6]のように、第1要素にアトムからなるリスト、第2要素に数の全部の積を
   持つようなリストを生成して、第2引数に代入する。
   a*bのように数がない単項式の場合は、[[a,b],1]のように第2要素が1であるような
   リストを第2引数とする */
tankou_to_list(X,[[X],1]):-
	atom(X).
tankou_to_list(X,[[],X]):-
	number(X).
tankou_to_list(X,[L,N]):-
	X=X1*X2,
	tankou_to_list(X1,[L1,N1]),
	tankou_to_list(X2,[L2,N2]),
	append(L1,L2,L),
	is(N,N1*N2).

/* tankou_to_listと同様だが、第2引数に入るリストの第1リストをソートする。
   例えば第1引数がa*3*c*b*2のとき、第2引数には[[a,b,c],6]が入る */
tankou_to_sorted_list(X,[L,N]):-
	tankou_to_list(X,[L1,N]),
	msort(L1,L). /* sortだと重複した要素を排除してしまうのでmsortを使う */

/* tankou_to_listの逆。第1引数に[[a,b,c],6]のようなリストを与え、
   6*a*b*cのような単項式を生成して第2引数に代入する。
   ただし第1引数が[[a,b,c],1]のように、第2要素が1である場合、1を省いて
   a*b*cという単項式を第2引数に代入する。
   しかし例外として、第1引数が[[],1]のときは、第2引数に1を代入する。*/
list_to_tankou([[],1],1).
list_to_tankou([L,1],X):-
	L \= [],
	list_to_tankou_sub(L,X).
list_to_tankou([L,N],X):-
	N \= 1,
	list_to_tankou_sub([N|L],X).
/* tankou_to_listの下請けに使う。第1引数に[6,a,b,c]のようなリストを与え、
   それを6*a*b*cのような単項式に変換して第2引数に代入 */
list_to_tankou_sub([X],X).
list_to_tankou_sub(L,X1*X):-
	append(L1,[X],L),
	list_to_tankou_sub(L1,X1).

/* tankou_to_sorted_listをリストの各要素に適用する。
   第1引数に[2*b*c,a*3*c*b*2]のような単項式のリストを与え、その各要素を
   tankou_to_sorted_listでリストにして、[[[b,c],2],[[a,b,c],6]]のような
   リストを生成し、第2引数に代入する */
tankoulist_to_listlist([],[]).
tankoulist_to_listlist([X|L],[X1|L1]):-
	tankou_to_sorted_list(X,X1),
	tankoulist_to_listlist(L,L1).

 /* tankoulist_to_listlistと同様だが、得られたリストをソートする。
    例えば第1引数が[2*b*c,a*3*c*b*2,]のとき、第2引数はソートされて
    [[[a,b,c],6],[[b,c],2]]になる */
tankoulist_to_listlist_sorted(X,L):-
	tankoulist_to_listlist(X,L1),
	msort(L1,L). /* sortだと重複した要素を排除してしまうのでmsortを使う */

/* tankoulist_to_listlistの逆。
   第1引数に[[[a,b,c],6],[[a,b],2]]のようなリストを与え、
   [6*a*b*c,2*a*b]のような単項式のリストを生成して第2引数に代入する */
listlist_to_tankoulist([],[]).
listlist_to_tankoulist([X|L],[X1|L1]):-
	list_to_tankou(X,X1),
	listlist_to_tankoulist(L,L1).

/* 第1引数にa*b+a*cのような単項式を与え、それを
   [a*b,a*c]のようなリストに変形して第2引数に代入する */
takou_to_list(X,L):-
	tankou(X), L=[X].
takou_to_list(X,L):-
	X=X1+X2,
	takou_to_list(X1,L1),
	takou_to_list(X2,L2),
	append(L1,L2,L).

/* 第1引数に[a*b,a*c]のような単項式のリストを与え、それを
   a*b+a*cのような多項式に変形して第2引数に代入する */
list_to_takou([X],X).
list_to_takou(L,X1+X):-
	append(L1,[X],L),
	list_to_takou(L1,X1).

/* 第1引数に[[[a,b],3],[[a,b],4],[[c],5]]のような
   tankoulist_to_listlist_sortedで得られる形のリストが入っているとする。
   それを3*a*b+4*a*b+5*cのような多項式を表すものと考え、
   隣り合う同類項をまとめて、その結果
   [[[a,b],7],[[c],5]]のようなリストを得て、それを第2引数とする */
douruikou_matome([X],[X]).
douruikou_matome([X|L],L1):-
	douruikou_matome(L,[Y|L0]),
	X=[X1,N],Y=[Y1,M],
	(X1=Y1 ->
		is(N1,N+M),Z1=[X1,N1],L1=[Z1|L0];
		L1=[X,Y|L0]).

/* 第1引数に[[[a,b],7],[[b,c],0],[[c],5]]のような
   douruikou_matomeで得られる形のリストが入っているとする。
   その要素のうち、第2要素が0であるものを省いて
   [[[a,b],7],[[c],5]]のようなリストを得て、第2引数に代入。
   ただし、第2要素が0であるものを省くと空になる場合は
   [[],0]を唯一の要素とするリスト、すなわち[[[],0]]を第2引数に代入する */
remove_zero(L,L1):-
	remove_zero_sub(L,L0),
	(L0=[]->
		L1=[[[],0]];
		L1=L0).
/* remove_zeroの下請け。第1引数の要素のうち、第2要素が0であるものを省いて
   第2引数に入れるが、その結果、第2引数が空のリストになることがある */
remove_zero_sub([],[]).
remove_zero_sub([X|L],L1):-
	X=[_,0],
	remove_zero_sub(L,L1).
remove_zero_sub([X|L],[X|L1]):-
	X\=[_,0],
	remove_zero_sub(L,L1).

/* tenkai述語で得た多項式を第1引数に与えると、
   それの同類項をまとめるなどして整理した多項式を第2引数に代入する
   例えば第1引数にx*x+x*y+(y*x+y*y)を与えると、第2引数にx*x+2*x*y+y*yを得る */
takou_seiri(X,Y):-
	takou_to_list(X,L),
	tankoulist_to_listlist_sorted(L,L0),
	douruikou_matome(L0,L1),
	remove_zero(L1,L2),
	listlist_to_tankoulist(L2,L3),
	list_to_takou(L3,Y).

/* 最終的に出来上がる展開述語
   第1引数に式を与えると、第2引数にそれを展開して整理した多項式が入る
   例えば第1引数が(x+y)*(x+y)の場合、第2引数はx*x+2*x*y+y*y
   第1引数が(x+y)*(x+(-1)*y)の場合、第2引数はx*x+ -1*y*yになる */   
tenkai_and_seiri(X,Y):-
	tenkai(X,Z),
	takou_seiri(Z,Y).