/* 
   %%%%%%%%%%%%% PROLOG UTILITY PARTS  %%%%%%%%%%%%%%%%%%%%%%%
   プロログの部品 (コメントになっている同名の述語は非効率の見本です)
*/

%% 実行遅延

:- public wait/1.
wait(0):- !.
wait(A):- 
	A>0,
	B is A-1,
	wait(B).

%% 総和

:- public sigma/2.
sigma(N,A):- 
	sigma(N,0,A).
sigma(0,A,A).
sigma(N,R,A):- 
	RR is N+R,
	NN is N-1,
	sigma(NN,RR,A).

%% sigma(0,0).
%% sigma(N,A):- 
%%	NN is N-1,
%%	sigma(NN,AA),
%%	A is AA+N.


%% リストの先頭

:- public car/2.
car(A,[A|_]).

%% car(A,L):- 
%%	[A|_]=L.

%% リストの先頭以外

:- public cdr/2.
cdr(A,[_|A]).

%% cdr(A,L):- 
%%	[_|A]=L.

%% リストの先頭に追加

:- public cons/3.
cons(A,B,[A|B]).

%% リストの二番目

:- public second/2.
second(A,[_,A|_]).

%% second(A,L):- 
%%	cdr(C,L),
%%	car(A,C).
%% second1(A,L):- 
%%	car(A,C),
%%	cdr(C,L).

%% リストの内容を出力

:- public write_list/1.
write_list([]).
write_list([A|L]):-
	write(A),
	write_list(L).

%% リストの要素を取り出す/リストの要素か調べる

:- public my_member/2.
my_member(A,[A|_]).
my_member(A,[_|L]):- 
	my_member(A,L).

%% リストの最後の要素を取り出す

:- public last/2.
last([A],A).
last([_|L],A):- 
	last(L,A).

%% リストの内容を加算する

:- public add_all/2.
add_all(A,N):- 
	add_all(A,0,N).
add_all([],N,N).
add_all([A|L],M,N):- 
	MM is M+A,
	add_all(L,MM,N).

%% add_all([],0).
%% add_all([A|L],N):- 
%%	add_all(L,M),
%%	N is M+A.

%% リストの指定の位置の要素を取り出す

:- public nth/3.
nth(1,A,[A|_]).
nth(N,A,[_|L]):-
	M is N-1,
	nth(M,A,L).

%% リストから1要素とそれ以外を取り出す

:- public select/3.
select([A|L],A,L).
select([B|L],A,[B|R]):- 
	select(L,A,R).

%% 連想ペアリストの検索

:- public assoc/3.
assoc(A,B,[[A|B]|_]).
assoc(A,B,[_|L]):- 
	assoc(A,B,L).

%% リストの同一要素の削除

:- public pack/2.
pack([],[]).
pack([A|L],R):-
	member(A,L),
	pack(L,R).
pack([A|L],[A|R]):-
	pack(L,R).

%% リストを指定位置で分割

:- public divide/4.
divide(0,L,[],L).
divide(N,[A|L],[A|R],T):- 
	N>0,
	M is N-1,
	divide(M,L,R,T).

%% リストを指定の要素位置で分割

:- public divide_at/4.
divide_at(A,[A|L],[],[A|L]).
divide_at(A,[B|L],[B|R],T):- 
	divide_at(A,L,R,T).

%% 指定の要素を削除

:- public delete/3.
delete(_,[],[]).
delete(A,[A|L],R):- 
	delete(A,L,R).
delete(A,[B|L],[B|R]):- 
	delete(A,L,R).

%% 指定の位置の要素を削除

:- public delete_nth/3.
delete_nth(1,[_|L],L).
delete_nth(N,[A|L],[A|R]):- 
	M is N-1,
	delete_nth(M,L,R).

%% リストの指定の位置に挿入

:- public insert/4.
insert(1,A,L,[A|L]).
insert(N,A,[B|L],[B|R]):- 
	N>0,
	M is N-1,
	insert(M,A,L,R).

%% リストのAの後ろにＢを挿入

:- public insert_after/4.
insert_after(A,B,[A|L],[A,B|L]).
insert_after(A,B,[C|L],[C|R]):- 
	insert_after(A,B,L,R).

%% リストの長さ

:- public list_length/2.
list_length(L,N):- 
	list_length(L,0,N).
list_length([],N,N).
list_length([_|L],N,M):- 
	NN is N+1,
	list_length(L,NN,M).

%% list_length([],0).
%% list_length([_|L],N):- 
%%	list_length(L,M),
%%	N is M+1.

%% リストの結合

:- public my_append/3.
my_append([],L,L).
my_append([A|L],R,[A|LR]):- 
	my_append(L,R,LR).

%% リストの反転

:- public reverse/2.
reverse(L,R):-
	rev(L,[],R).
rev([],L,L).
rev([A|L],R,ANS):- 
	rev(L,[A|R],ANS).

%% reverse([],[]).
%% reverse([A|L],R):- 
%%	reverse(L,K),
%%	append(K,[A],R).

%% リストの中のリストの結合

:- public appends/2.
appends([],[]):- !.
appends([[]|L],R):- 
	!,
	appends(L,R).
appends([[X|L]|LL],[X|LR]):-
	appends([L|LL],LR).

%% appends([],[]).
%% appends([X|L],X1):-
%%	append(X,Y,X1),
%%	appends(L,Y).

%% appends([],[]).
%% appends([X|L],X1):-
%%	appends(L,Y),
%%	append(X,Y,X1).


%% リストの中のリストの反転

:- public reverses/2.
reverses(L,R):-reverses(L,[],R).
reverses([],_,[]).
reverses([[]|L],R,[R|X]):-
	reverses(L,[],X).
reverses([[A|S]|L],R,X):-
	reverses([S|L],[A|R],X).


%% reverses([],[]).
%% reverses([A|L],[B|R]):- 
%%	reverse(A,B),
%%	reverses(L,R).

%%  3リストの結合
:- public append3/4.
append3(A,B,C,ABC):-
	append(A,BC,ABC),
	append(B,C,BC).

%% append3(A,B,C,ABC):-
%%	append(B,C,BC),
%%	append(A,BC,ABC).

%%%  リストの平坦化

:- public flat/2.
flat(A,B):-flat(A,[],B),!.
flat([],X,X).
flat([A|L],R,ANS):-
	flat(A,X,ANS),
	flat(L,R,X).
flat(A,X,[A|X]).

%% flat([],[]).
%% flat([A|L],ANS):-
%% 	flat(A,AF),
%%	flat(L,LF),
%%	append(AF,LF,ANS).
%% flat(A,[A]).

%%　クィックソ−ト

/* quick sort */
:- public qsort/2.

qsort(L,R):-qsort(L,[],R).

:- mode qsort(+,+,-).

qsort([],L,L).
qsort([A|L],R,ANS):-
	partition(L,A,L1,L2),
	qsort(L1,[A|X],ANS),
	qsort(L2,R,X).

:- mode partition(+,+,-,-).

partition([],_,[],[]).
partition([X|L],A,[X|L1],L2):- 
	X=<A,
	!,
	partition(L,A,L1,L2).
partition([X|L],A,L1,[X|L2]):- 
	partition(L,A,L1,L2).
