Prologの技芸 3.3節の練習問題

(1)

% substitute(X,Y,L1,L2) :-
%  L2はL1中に現れるすべてのXをYで置き換えた結果である．
substitute(X,Y,[],[]).
substitute(X,Y,[X|Xs],[Y|Ys]) :- substitute(X,Y,Xs,Ys).
substitute(X,Y,[Z|Xs],[Z|Ys]) :- X \= Z, substitute(X,Y,Xs,Ys).

(2)

% select(X,Xs,Ys) :-
%  Ysは，Xsの最先頭にあるXをXsから削除したリストである．
select(X,[X|Xs],Xs).
select(X,[Y|Ys],[Y|Zs]) :- X \= Y, select(X,Ys,Zs).

(3)

% no_doubles(L1,L2) :-
%  L2はL1から重複する要素をすべて取り除いた結果である．
no_doubles([],[]).
no_doubles([X|Xs],Ys) :- member(X,Xs), !, no_doubles(Xs,Ys).
no_doubles([X|Xs],[X|Ys]) :- no_doubles(Xs,Ys).

(4)

% even_permutation(Xs,Ys) :-
%  YsはリストXsの偶数順列である．
% odd_permutation(Xs,Ys) :-
%  YsはリストXsの奇数順列である．
even_permutation([],[]).
odd_permutation([],[]).
even_permutation([X|Xs],Ys) :- odd_permutation(Xs,Ys).
odd_permutation([X|Xs],[X|Ys]) :- even_permutation(Xs,Ys).

(5)

% margesort(Xs,Ys) :-
%  リストYsはリストXsの順序付けられた順列である．
margesort([],[]).
margesort([X],[X]).
margesort([X1,X2|Xs],Ys) :-
 partition([X1,X2|Xs],Lefts,Rights),
 margesort(Lefts,Ls),
 margesort(Rights,Rs),
 marge(Ls,Rs,Ys).

% partition(Xs,Lefts,Rights) :-
%  LeftsとRightsはXsを大体半分ずつに分けたものである．
partition(Xs,Lefts,Rights) :-
 length(Xs,Length),
 half(Length,L,R),
 prefix(Lefts,Xs),
 length(Lefts,L),
 append(Lefts,Rights,Xs),
 length(Rights,R).

half(X,L,R) :-
 X1 is X/2,
 integer(X1),
 L = X1,
 R = X1.
half(X,L,R) :-
 X1 is (X-1)/2,
 integer(X1),
 L = X1,
 R is X-X1.

% marge(Xs,Ys,Zs) :-
%  ZsはXsとYsを併合したものである．
marge([],Xs,Xs).
marge(Xs,[],Xs).
marge([X|Xs],[Y|Ys],[X|Zs]) :- X < Y, marge(Xs,[Y|Ys],Zs).
marge([X|Xs],[Y|Ys],[Y|Zs]) :- X >= Y, marge([X|Xs],Ys,Zs).