Prolog Programming

はじめに

今回はちょっと便利な述語を問題形式で紹介します。元ネタは P-99: Ninety-Nine Prolog Problems です。P-99 と同じ問題もありますが、その場合は異なる解答を考えたいと思います。プログラムの動作は SWI-Prolog version 5.6.59 (Windows XP) で確認しました。

●問題１

リストの要素がただひとつか調べる述語 single(Ls) を定義してください。

?- single([a]).
true.

?- single([a, b]).
false.

?- single([]).
false.

解答

●問題２

リストの要素がひとつ以上あるか調べる述語 pair(Ls) を定義してください。

?- pair([a]).
true.

?- pair([a, b]).
true.

?- pair([]).
false.

解答

●問題３

リスト Xs はリスト Ys よりも長いことを表す述語 longer(Xs, Ys) を定義してください。

?- longer([a, b, c], [d, e]).
true.

?- longer([a, b], [c, d]).
false.

?- longer([a, b), [c]).
false.

解答

●問題４

リスト Xs の最後尾を求める述語 last(Xs, Ys) と、最後尾の要素を取り除く述語 butlast(Xs, Ys) を定義してください。

?- last([a, b, c, d, e], X).
X = [e] ;
false.

?- butlast([a, b, c, d, e], X).
X = [a, b, c, d] ;
false.

解答

●問題５

リスト Xs の先頭から N 個の要素を取り出す述語 take(Xs, N, Ys) を定義してください。

?- take([a, b, c, d, e], 3, X).
X = [a, b, c] ;
false.

?- take([a, b, c, d, e], 6, X).
X = [a, b, c, d, e].

解答

●問題６

リスト Xs の先頭から N 個の要素を取り除く述語 drop(Xs, N, Ys) を定義してください。

?- drop([a, b, c, d, e], 3, X).
X = [d, e] ;
fales.

?- drop([a, b, c, d, e], 6, X).
X = [].

解答

●問題７

リスト Xs の N 番目から M 番目の要素を部分リストとして取り出す述語 subseq(Xs, N, M, Ys) を定義してください。なお、リストの要素は 1 から数え始めるものとします。

?- subseq([a, b, c, d, e], 2, 4, X).
X = [b, c, d] ;
false.

?- subseq([a, b, c, d, e], 3, 2, X).
X = [] ;
false.

解答

●問題８

リスト Xs の末尾から N 個の要素を取り除く述語 butlast(Xs, N, Ys) を定義してください。

?- butlast([a, b, c, d, e], 3, X).
X = [a, b] ;
false.

?- butlast([a, b, c, d, e], 6, X).
false.

解答

●問題９

リスト Xs を長さ N の部分リストに分割する述語 group(Xs, N, Ys) を定義してください。

?- group([a, b, c, d, e, f], 2, X).
X = [[a, b], [c, d], [e, f]] ;
false.

?- group([a, b, c, d, e, f], 3, X).
X = [[a, b, c], [d, e, f]] ;
false.

?- group([a, b, c, d, e, f], 4, X).
X = [[a, b, c, d], [e, f]] ;
false.

解答

●問題10

リスト Ls の中から X と等しい要素の位置 N を求める述語 position(X, Ls, N) を定義してください。なお、リストの要素は 1 から数え始めるものとします。

?- position(c, [a, b, c, d, e, f], X).
X = 3 ;
false.

?- position(g, [a, b, c, d, e, f], X).
false.

解答

●問題11

リスト Ls から X と等しい要素の個数 N を求める述語 count(X, Ls, N) を定義してください。

?- count(b, [a, b, a, b, a], X).
X = 2 ;
false.

?- count(c, [a, b, a, b, a], X).
X = 0 ;
false.

解答

●問題12

リスト Ls の要素の合計値を求める述語 sum_list(Ls, Sum) を定義してください。

?- sum_list([1, 2, 3, 4, 5], N).
N = 15.

解答

●問題13

リスト Ls の中から最大値を求める述語 max_list(Ls, Max) と最小値を求める述語 min_list(Ls, Min) を定義してください。

?- max_list([5, 6, 4, 7, 3, 8, 2, 9, 1], N).
N = 9 ;
false.

?- min_list([5, 6, 4, 7, 3, 8, 2, 9, 1], N).
N = 1 ;
false.

解答

●問題14

要素 X の右隣に要素 Y があるかチェックする述語 adjacent(X, Y, Ls) を定義してください。

?- adjacent(a, b, [a, b, c, d, e]).
true ;
false.

?- adjacent(X, Y, [a, b, c, d, e]).
X = a,
Y = b ;
X = b,
Y = c ;
X = c,
Y = d ;
X = d,
Y = e ;
false.

解答

●問題15

要素 X が 要素 Y よりも前に出現しているか調べる述語 before(X, Y, Ls) を定義してください。

?- before(a, c, [a, b, c, d, e]).
true ;
false.

?- before(X, c, [a, b, c, d, e]).
X = a ;
X = b ;
false.

?- before(X, Y, [a, b, c, d, e]).
X = a,
Y = b ;
X = a,
Y = c ;
X = a,
Y = d ;
X = a,
Y = e
...

解答

●問題16

整数 N から M までを格納したリストを作る述語 iota(N, M, Xs) を定義してください。

?- iota(1, 5, X).
X = [1, 2, 3, 4, 5] ;
false.

解答

●問題17

リスト Xs から重複要素を取り除いて集合を生成する述語 set_of_list(Xs, Ys) を定義してください。

?- set_of_list([a, b, c, a, d], X).
X = [b, c, a, d].

解答

●問題18

2 つの集合の和を求める述語 union(Xs, Ys, Zs) を定義してください。

?- union([a, b, c, d], [c, d, e, f], X).
X = [a, b, c, d, e, f].

解答

●問題19

2 つの集合の積を求める述語 intersection(Xs, Ys, Zs) を定義してください。

?- intersection([a, b, c, d], [c, d, e, f], X).
X = [c, d].

解答

●問題20

2 つの集合の差を求める述語 difference(Xs, Ys, Zs) を定義してください。

?- difference([a, b, c, d], [c, d, e, f], X).
X = [a, b].

解答

●問題21

2 つのソート済みのリストをひとつのソート済みのリストにまとめる述語 merge_list(Xs, Ys, Zs) を定義してください。

?- merge_list([1, 3, 5, 7, 9], [2, 4, 6, 8], X).
X = [1, 2, 3, 4, 5, 6, 7, 8, 9] ;
false.

解答

●問題22

述語 merge_list を使ってリストをソートする merge_sort(Xs, Ys) を定義してください。

?- merge_sort([5, 6, 4, 7, 3, 1, 2, 9, 8], X).
X = [1, 2, 3, 4, 5, 6, 7, 8, 9] ;
false.

解答

●問題23

リスト Ps がリスト Ls の「接頭辞 (prefix) 」か判定する述語 prefix(Ls, Ps) を定義してください。接頭辞とは、列の先頭からある位置までの部分列のことです。たとえば、リスト [a, b, c, d] の接頭辞は [ ], [a], [a, b], [a, b, c], [a, b, c, d] の 5 つになります。

?- prefix([a, b, c, d], X).
X = [] ;
X = [a] ;
X = [a, b] ;
X = [a, b, c] ;
X = [a, b, c, d].

解答

●問題24

リスト Ss がリスト Ls の「接尾辞 (suffix) 」か判定する述語 suffix(Ls, Ss) を定義してください。接尾辞とは、列のある位置から末尾までの部分列のことです。たとえば、リスト [a, b, c, d] の接尾辞は [a, b, c, d], [b, c, d], [c, d], [d], [ ] の 5 つになります。

?- suffix([a, b, c, d], X).
X = [a, b, c, d] ;
X = [b, c, d] ;
X = [c, d] ;
X = [d] ;
X = [].

解答

●問題25

リスト Xs がリスト Ls の部分リストか判定する述語 sublist(Xs, Ls) を定義してください。

?- sublist([b, c, d], [a, b, c, d, e]).
true

?- sublist(X, [a, b, c]).
X = [] ;
X = [a] ;
X = [a, b] ;
X = [a, b, c] ;
X = [b] ;
X = [b, c] ;
X = [c] ;
false.

解答

●解答１

リスト：要素がただひとつか

single([_]).

Prolog の場合、引数のリストと [ _ ] がマッチングすれば、そのリストの要素は一つしかないことがわかります。length でリストの長さを求める必要はありません。

●解答２

リスト：要素がひとつ以上あるか

pari([_ | _]).

たとえば、リスト [a] と [X | Xs] を照合すると、X = a, Xs = [ ] になります。したがって、引数のリストと [_ | _] がマッチングすれば、そのリストの要素は一つ以上あることがわかります。length でリストの長さを求める必要はありません。

なお、述語 pair の名前は Scheme の関数 pair? から拝借しました。

●解答３

リスト：リスト Xs は Ys よりも長いか

longer([_ | Xs], [_ | Ys]) :- !, longer(Xs, Ys).
longer([_ | _], []).

リストの先頭から順番にたどり、途中で Ys が空リストになれば Xs の方が長いことがわかります。述語 longer は再試行する必要がないので、カットでバックトラックを禁止しています。length でリストの長さを求めて比較するよりも、このプログラムの方が効率的だと思います。

●解答４

リスト： リストの最後尾を求める

last(Xs, Xs) :- single(Xs).       % last([X], [X]). でもよい
last([_ | Xs], Ys) :- last(Xs, Ys).

% 別解
last(Xs, [Y]) :- append(_, [Y], Xs).

最初のプログラムは単純な再帰定義でリストの最後尾を求めています。別解は述語 append を使った定義です。最後尾を [Y] とすると、無名変数 _ で表したリストと [Y] を連結したものが Xs になる、という関係を表しています。

リスト：最後尾の要素を取り除く

butlast(Xs, []) :- single(Xs).    % butlast([_], []). でもよい
butlast([X | Xs], [X | Ys]) :- butlast(Xs, Ys).

% 別解
butlast(Xs, Ys) :- append(Ys, [_], Xs).

butlast の最初の規則は、要素がひとつしかないリストから最後尾の要素を取り除くと空リストになることを表しています。これが再帰の停止条件になります。あとは次の規則で butlast を再帰呼び出しして、Xs から最後尾の要素を取り除いたリスト Ys にリストの先頭要素 X を追加していくだけです。

別解は述語 append を使った定義です。最後尾を [ _ ] とすると、[Ys] と [ _ ] を連結したものが Xs になる、という関係を表しています。

●解答５

リスト：リストの先頭から N 個の要素を取り出す

take(_, 0, []).
take([], N, []) :- N > 0.
take([X | Xs], N, [X | Ys]) :-
    N > 0, N1 is N - 1, take(Xs, N1, Ys).

% 別解
take(Xs, N, Ys) :- append(Ys, _, Xs), length(Ys, N).
take(Xs, N, Xs) :- length(Xs, M), N > M.

最初の規則で、N が 0 の場合は空リストを返します。次の規則は途中でリストが空になった場合です。この場合も空リストを返します。最後の規則で、take を再帰呼び出ししてリスト Ys を求め、その先頭に要素 X を追加します。

別解は append を使った定義です。append でリスト Xs を Ys と _ に分解して、Ys の長さが N になればいいわけです。length で失敗すると再試行が行われるので正常に動作しますが、効率はあまりよくありません。ただし、最初の規則だけでは N が Xs の長さよりも大きいと失敗します。Xs をそのまま返したい場合は、2 番目の規則が必要になります。

●解答６

リスト：リストの先頭から N 個の要素を削除する

drop(Xs, 0, Xs).
drop([], N, []) :- N > 0.
drop([_ | Xs], N, Ys) :-
    N > 0, N1 is N - 1, drop(Xs, N1, Ys).

% 別解
drop(Xs, N, Ys) :- append(Zs, Ys, Xs), length(Zs, N).
drop(Xs, N, []) :- length(Xs, M), N > M.

最初の規則は、削除する要素数が 0 であればリスト Xs はそのままであることを表しています。次の規則は、空リストは空リストのままであることを表しています。最後の規則で、N 個の要素を取り除いたリスト Ys は、先頭要素を取り除いたリスト Xs から N - 1 個の要素を取り除いたリストであることを表しています。

別解は append を使った定義です。append でリスト Xs を Zs と Ys に分解して、Zs の長さが N になればいいわけです。take と同様に、length で失敗すると再試行が行われるので正常に動作しますが、効率はあまりよくありません。ただし、最初の規則だけでは N が Xs の長さよりも大きいと失敗します。空リストを返したい場合は、2 番目の規則が必要になります。

●解答７

リスト：部分リストを取り出す

subseq(_, N, M, []) :- N > M.
subseq(Xs, N, M, Ys) :-
    N > 0, M >= N, N1 is N - 1, K is M - N1, drop(Xs, N1, Zs), take(Zs, K, Ys).

subseq は drop と take を使うと簡単です。最初の規則で N <= M を満たしているかチェックします。そうでなければ空リストを返します。次の規則で、先頭から取り除く要素の個数を N1 に求め、取り出す要素の個数を K に求めます。あとは、N1 個の要素を drop で取り除いて、take で k 個の要素を取り出します。

●解答８

リスト：リストの末尾から N 個の要素を取り除く

butlast(Xs, N, Ys) :-
    length(Xs, M), K is M - N, take(Xs, K, Ys).

リスト Xs の長さを M とすると、リストの末尾から N 個の要素を取り除くことは、リストの先頭から M - N 個の要素を取り出すことと同じになります。取り出す要素の個数を K is M - N で求めて、take で K 個の要素を取り出します。

●解答９

リスト：リストの分割

group([], _, []).
group(Xs, N, [As | Ys]) :-
    Xs \= [], take(Xs, N, As), drop(Xs, N, Rs), group(Rs, N, Ys).

述語 group は take と drop を使うと簡単に定義できます。Xs が空リストの場合は分割できないので空リストを返します。これが再帰の停止条件になります。Xs が空リストでない場合、まず take で N 個の要素を格納したリスト As を求めます。次に、N 個の要素を取り除いたリスト Rs を drop で求めます。あとは、group を再帰呼び出ししてリスト Rs を分割し、分割したリスト Ys の先頭に As を追加すればいいわけです。

●解答10

リスト：要素の位置を求める

position(X, Ls, N) :- position(X, Ls, N, 1).
position(X, [X | _], N, N).
position(X, [_ | Ys], N, M) :-
    M1 is M + 1, position(X, Ys, N, M1).

% 別解
position(X, Ls, N) :-
    append(Ys, [X | _], Ls), length(Ys, M), N is M + 1.

実際の処理は position/4 で行います。最後の引数が要素の位置を表します。2 番目の規則で、X とリストの先頭要素がマッチングしたら、第 3 引数を第 4 引数と同じ N に指定します。そうでなければ、最後の規則で位置 M の値を +1 してから position を再帰呼び出しします。

別解は append を使った定義です。リスト Ls を Ys と [X | _] に分割すると、X の位置はリスト Ys の長さに 1 を加えたものになります。最初の定義では要素を指定する変数 X を自由変数にすることはできませんが、別解では要素 X と位置 N を自由変数にしても動作します。

●解答11

リスト：要素の個数を求める

count(_, [], 0).
count(X, [X | Xs], M) :- count(X, Xs, N), M is N + 1.
count(X, [Y  |Xs], N) :- X \= Y, count(X, Xs, N).

% 別解
count(X, Ls, N) :- count(X, Ls, 0, N).
count(_, [], N, N).
count(X, [X | Xs], A, N) :- A1 is A + 1, count(X, Xs, A1, N).
count(X, [Y | Xs], A, N) :- X \= Y, count(X, Xs, A, N).

最初の規則は、リスト Ls が空リストであれば個数は 0 という関係を表しています。これが再帰の停止条件になります。2 番目の規則で、X と等しい要素を見つけた場合は、残りのリストに対して count を再帰呼び出しして、求めた要素の個数 N に 1 を加えます。要素 Y が X と異なる場合は N を +1 しません。

別解は count を末尾再帰で書き直したものです。count/4 の第 3 引数 A が累積変数で、X と等しい要素をカウントします。

●解答12

リスト：要素の合計値を求める

sum_list([], 0).
sum_list([X | Xs], Sum) :-
    sum_list(Xs, Sum1), Sum is Sum1 + X.

% 別解
sum_list(Ls, Sum) :- sum_list(Ls, 0, Sum).
sum_list([], Sum, Sum).
sum_list([X | Xs], A, Sum) :- A1 is A + X, sum_list(Xs, A1, Sum).

最初の規則は空リストの合計値は 0 であることを表しています。これが再帰の停止条件になります。次の規則で、リストを X と Xs に分解し、sum_list を再帰呼び出しして Xs の合計値 Sum1 を求めます。そして、それに X の値を加えて Sum を求めます。

別解は累積変数 A を使って sum_list を末尾再帰に書き直したものです。

●解答13

リスト：リストから最大値と最小値を求める

max_list([X | Xs], M) :- max_list(Xs, X, M).
max_list([], M, M).
max_list([X | Xs], Y, M) :- X > Y, max_list(Xs, X, M).
max_list([X | Xs], Y, M) :- X =< Y, max_list(Xs, Y, M).

min_list([X | Xs], M) :- min_list(Xs, X, M).
min_list([], M, M).
min_list([X | Xs], Y, M) :- X < Y, min_list(Xs, X, M).
min_list([X | Xs], Y, M) :- X >= Y, min_list(Xs, Y, M).

max_list/3 と min_list/3 は第 2 引数を累積変数として使っていて、そこに最大値 (または最小値) を保持します。最初に呼び出すとき、リストの先頭要素をセットします。あとは残りの要素を順番に調べていき、リストの先頭要素 X が第 2 引数 Y よりも大きい (または小さい) 場合は、それを X に置き換えるだけです。

●解答14

リスト：X と Y は隣り合っているか

adjacent(X, Y, [X, Y | _]).
adjacent(X, Y, [_ | Zs]) :- adjacent(X, Y, Zs).

% 別解
adjacent(X, Y, Ls) :- append(_, [X, Y | _], Ls).

述語 adjacent の定義は簡単です。リストが [X, Y | _] とマッチングすれば、X と Y が隣り合っていることがわかります。そうでなければ、次の規則で先頭の要素を取り除き、adjacent を再帰呼び出しして残りのリスト Zs から探します。

別解は append を使ってリスト Ls を _ と [X, Y | _] に分割します。分割できなければ、X と Y は隣り合っていないことになります。

●解答15

リスト：X は Y よりも前に出現しているか

members(X, [X | Xs], Xs).
members(X, [_ | Xs], Ys) :- members(X, Xs, Ys).

before(X, Y, Ls) :- 
    members(X, Ls, Xs), member(Y, Xs).

述語 before は述語 members を定義すると簡単にプログラムすることができます。members(X, Ls, Zs) は述語 member とほぼ同じですが、X と等しい要素を見つけたとき、Zs は残りのリストになります。プログラムは簡単なので説明は省略いたします。

before は最初に members で X を探し、残りのリスト Xs に Y があるか member で探します。member のかわりに members(Y, Xs, _) としてもかまいません。

●解答16

リスト：数列の生成

iota(N, M, []) :- N > M.
iota(N, M, [N | Xs]) :-
    N =< M, N1 is N + 1, iota(N1, M, Xs).

述語 iota は簡単です。最初の規則が再帰定義の停止条件です。N が M より大きい場合は空リストになります。N が M 以下の場合、iota を再帰呼び出しして N1 から M までのリスト Xs を生成し、その先頭に N を追加するだけです。

●解答17

リスト：集合の生成

set_of_list([], []).
set_of_list([X | Xs], Ys) :- member(X, Xs), !, set_of_list(Xs, Ys).
set_of_list([X | Xs], [X | Ys]) :- set_of_list(Xs, Ys).

述語 set_of_list はリストから重複要素を取り除きます。空リストは重複要素がないので空リストのままです。次の規則で、リストの先頭要素 X が残りのリスト Xs にあるか member で調べ、同じ要素があれば X を集合 Ys に加えません。最後の要素で、同じ要素がない場合は X を Ys に加えます。

●解答18

リスト：集合の和

union1([], Xs, Xs).
union1([X | Xs], Ys, Zs) :- member(X, Ys), !, union1(Xs, Ys, Zs).
union1([X | Xs], Ys, [X | Zs]) :- union1(Xs, Ys, Zs).

述語 union は SWI-Prolog に定義されているので、名前は union1 としました。最初の規則は空集合 (空リスト) と集合 Xs の和は Xs であることを表しています。次の規則で、要素 X が集合 Ys に含まれていれば、X を新しい集合 Zs に加えません。最後の規則で、X が Ys に含まれていない場合は X を Zs に追加します。

●解答19

リスト：集合の積

intersection1([], _, []).
intersection1([X | Xs], Ys, [X | Zs]) :-
    member(X, Ys), !, intersection1(Xs, Ys, Zs).
intersection1([_ | Xs], Ys, Zs) :- intersection1(Xs, Ys, Zs).

述語 intersection は SWI-Prolog に定義されているので、名前は intersection1 としました。最初の規則は空集合 (空リスト) と集合 _ の積は空集合であることを表しています。次の規則で、要素 X が集合 Ys に含まれていれば、X を新しい集合 Zs に追加します。そうでなければ、最後の規則で X は Zs に追加しません。

●解答20

リスト：集合の差

difference([], _, []).
difference([X | Xs], Ys, Zs) :-
    member(X, Ys), !, difference(Xs, Ys, Zs).
difference([X | Xs], Ys, [X | Zs]) :- difference(Xs, Ys, Zs).

最初の規則は、空集合と集合 _ の差は空集合であることを表しています。次の規則で、要素 X が Ys に含まれいる場合は集合 Zs に X を追加しません。そうでなければ、最後の規則で X を Zs に追加します。

●解答21

リスト：リストのマージ

merge_list([], Ys, Ys).
merge_list(Xs, [], Xs).
merge_list([X | Xs], [Y | Ys], [X | Zs]) :- X < Y, merge_list(Xs, [Y | Ys], Zs).
merge_list([X | Xs], [Y | Ys], [Y | Zs]) :- X >= Y, merge_list([X | Xs], Ys, Zs).

最初の規則は、空リストとリスト Ys をマージすると Ys になることを表しています。次の規則は、リスト Xs と空リストをマージすると Xs になることを表しています。この 2 つの規則が、再帰呼び出しの停止条件になります。

3 番目の規則で、それぞれのリストの先頭要素 X と Y を比較し、X が小さい場合はマージしたリスト Zs の先頭に X を追加し、そうでなければ最後の規則で Y を Zs の先頭に追加します。merge_list を再帰呼び出しするときは X または Y を取り除いて呼び出すことに注意してください。

●解答22

マージソートは merge_list を使ってデータをソートします。次の図を見てください。

 9 5 3 7 6 4 2 8  最初の状態

|5 9|3 7|4 6|2 8| 長さ２の列に併合

|3 5 7 9|2 4 6 8| 長さ４の列に併合 

 2 3 4 5 6 7 8 9  ソート終了


        図 : マージソート

マージをソートに応用する場合、最初は各要素をソート済みのリストとして考えます。この状態で隣のリストとマージを行い、長さ 2 のリストを作ります。次に、このリストに対して再度マージを行い、長さ 4 のリストを作ります。このように順番にマージしていくと、最後にはひとつのリストにマージされソートが完了します。

実際にプログラムを作る場合、リストの長さを 1, 2, 4, 8, ... と増やしていくよりも、再帰的に考えた方が簡単です。まず、ソートするリストを 2 つに分割して、前半部分をソートします。次に、後半部分をソートして、その結果をマージすればいいわけです。

再帰呼び出しするたびにリストは 2 つに分割されるので、最後にリストの要素はひとつとなります。これはソート済みのリストなので、ここで再帰呼び出しを終了してマージ処理を行えばいいわけです。プログラムは次のようになります。

リスト：マージソート

merge_sort(Xs, Ys) :- length(Xs, N), merge_sort(N, Xs, Ys).
merge_sort(_, [], []).
merge_sort(1, [X | _], [X]).
merge_sort(N, Xs, Ys) :-
    N > 1,
    M1 is N // 2,
    merge_sort(M1, Xs, Zs1),
    M2 is N - M1,
    drop(Xs, M1, Xs1),
    merge_sort(M2, Xs1, Zs2),
    merge_list(Zs1, Zs2, Ys).

実際の処理は merge_sort/3 で行います。merge_sort/3 の引数 Xs がソートするリスト、引数 n がリストの長さを表します。merge_sort はリストを分割する処理で、新しいリストを作らないことに注意してください。次の図を見てください。

merge_sort はソートするリストの範囲を開始位置と長さで表しています。上図のリストを二分割する場合、前半部分は Xs と N / 2 で表し、後半部分を Xs1 と N / 2 で表します。Xs1 はリスト Xs の先頭から N / 2 個の要素を取り除けば求めることができます。この処理を述語 drop で行います。

あとは merge_sort を再帰呼び出しでリストを分割していき、リストの長さが 1 になったならば新しいリストを返します。そして、merge_sort でソートしたリスト Zs1 と Zs2 を merge でマージすればいいわけです。

●解答23

リスト：接頭辞の判定

prefix(_, []).
prefix([X | Xs], [X | Ys]) :- prefix(Xs, Ys).

% 別解
prefix(Xs, Ys) :- append(Ys, _, Xs).

接頭辞の判定は簡単です。最初の規則は、空リストは接頭辞であることを表しています。次の規則で、リストの先頭要素が等しい場合は、残りのリスト Ys が Xs の接頭辞であることを確かめます。別解は append を使う方法で、リスト Xs を接頭辞 Ys と接尾辞 _ に分割します。

●解答24

リスト：接尾辞の判定

suffix(Xs, Xs).
suffix([_ | Xs], Ys) :- suffix(Xs, Ys).

% 別解
suffix(Xs, Ys) :- append(_, Ys, Xs).

接尾辞の判定も簡単です。最初の規則は、リスト Xs は接尾辞であることを表しています。次の規則で、リストの先頭要素を取り除いたリスト Xs を求め、Ys が Xs の接尾辞であることを確かめます。別解は append を使う方法で、リスト Xs を接頭辞 _ と接尾辞 Ys に分割します。

●解答25

リスト：部分リストの判定

sublist([], _).
sublist(Sub, Ls) :- prefix(Ls, Ps), suffix(Ps, Sub), Sub \= [].

% 別解
sublist([], _).
sublist(Sub, Ls) :- suffix(Ls, Ss), prefix(Ss, Sub), Sub \= [].

sublist は prefix と suffix を使うと簡単です。最初の規則は、空リストは部分リストであることを表します。次の規則で、リスト Ls の接頭辞 Ps を求め、Ps の接尾辞が部分リスト Sub になります。別解のように、prefix と suffix の順番を入れ替えても動作します。