今回はちょっと便利な関数を問題形式で紹介します。元ネタは P-99: Ninety-Nine Prolog Problems です。拙作のページ Prolog Programming Yet Another Prolog Problems と同じ問題ですが、あしからずご了承くださいませ。
リストの要素がただひとつか調べる述語 single(Xs) を定義してください。
> yaep:single([a]). true > yaep:single([a, b]). false > yaep:single([]). false
リストの要素がひとつ以上あるか調べる述語 pair(Xs) を定義してください。
> yaep:pair([a, b]). true > yaep:pair([a]). true > yaep:pair([]). false
リスト Xs はリスト Ys よりも長いか調べる述語 longer(Xs, Ys) を定義してください。
> yaep:longer([a, b, c], [d, e]). true > yaep:longer([a, b], [d, e]). false > yaep:longer([a], [d, e]). false
リストの最後尾の要素を求める関数 last(Xs) と、最後尾の要素を取り除く関数 butlast(Xs) を定義してください。
> yaep:last([a, b, c]). c > yaep:last([a]). a > yaep:last([]). ** exception error: no function clause matching yaep:last([]) > yaep:butlast([a, b, c]). [a,b] > yaep:butlast([a]). [] > yaep:butlast([]). ** exception error: no function clause matching yaep:butlast([])
リスト Xs の先頭から N 個の要素を取り出す関数 take(N, Xs) を定義してください。
> yaep:take(3, [a, b, c, d, e]). [a,b,c] > yaep:take(0, [a, b, c, d, e]). [] > yaep:take(5, [a, b, c, d, e]). [a,b,c,d,e] > yaep:take(6, [a, b, c, d, e]). [a,b,c,d,e]
リスト Xs の先頭から N 個の要素を取り除く関数 drop(N, Xs) を定義してください。
> yaep:drop(3, [a, b, c, d, e]). [d,e] > yaep:drop(0, [a, b, c, d, e]). [a,b,c,d,e] > yaep:drop(5, [a, b, c, d, e]). [] > yaep:drop(6, [a, b, c, d, e]). []
リスト Xs の N 番目から M - 1 番目の要素を部分リストとして取り出す関数 subseq(N, M, Xs) を定義してください。なお、リストの要素は 1 から数え始めるものとします。
> yaep:subseq(1, 3, [a, b, c, d, e]). [a,b] > yaep:subseq(1, 6, [a, b, c, d, e]). [a,b,c,d,e] > yaep:subseq(3, 6, [a, b, c, d, e]). [c,d,e] > yaep:subseq(3, 3, [a, b, c, d, e]). []
リスト Xs の末尾から N 個の要素を取り除く関数 butlastn(N, Xs) を定義してください。
> yaep:butlastn(1, [a, b, c, d, e]). [a,b,c,d] > yaep:butlastn(2, [a, b, c, d, e]). [a,b,c] > yaep:butlastn(5, [a, b, c, d, e]). []
リスト Xs を長さ N の部分リストに分割する述語 group(N, Xs) を定義してください。
> yaep:group(3, [1, 2, 3, 4, 5, 6]). [[1,2,3],[4,5,6]] > yaep:group(2, [1, 2, 3, 4, 5, 6]). [[1,2],[3,4],[5,6]] > yaep:group(1, [1, 2, 3, 4, 5, 6]). [[1],[2],[3],[4],[5],[6]] > yaep:group(4, [1, 2, 3, 4, 5, 6]). [[1,2,3,4],[5,6]]
リスト Xs の中から述語 Pred が真を返す最初の要素の位置を求める関数 position_if(Pred, Xs) を定義してください。なお、リストの要素は 1 から数え始めるものとします。
> yaep:position_if(fun(X) -> X =:= 2 end, [6, 5, 4, 3, 2, 1]). 5 > yaep:position_if(fun(X) -> X =:= 6 end, [6, 5, 4, 3, 2, 1]). 1 > yaep:position_if(fun(X) -> X =:= 1 end, [6, 5, 4, 3, 2, 1]). 6 > yaep:position_if(fun(X) -> X =:= 0 end, [6, 5, 4, 3, 2, 1]). false
リスト Xs から述語 Pred が真を返す要素の個数を求める関数 count_if(Pred, Xs) を定義してください。
> yaep:count_if(fun(X) -> X =:= 1 end, [1, 1, 2, 1, 2, 3, 1, 2, 3, 4]). 4 > yaep:count_if(fun(X) -> X =:= 2 end, [1, 1, 2, 1, 2, 3, 1, 2, 3, 4]). 3 > yaep:count_if(fun(X) -> X =:= 3 end, [1, 1, 2, 1, 2, 3, 1, 2, 3, 4]). 2 > yaep:count_if(fun(X) -> X =:= 4 end, [1, 1, 2, 1, 2, 3, 1, 2, 3, 4]). 1 > yaep:count_if(fun(X) -> X =:= 5 end, [1, 1, 2, 1, 2, 3, 1, 2, 3, 4]). 0
リスト Xs の要素の合計値を求める述語 sum_list(Xs) を定義してください。
> yaep:sum_list([1, 2, 3, 4, 5, 6, 7, 8]). 36 > yaep:sum_list([1, -2, 3, -4, 5, -6, 7, -8]). -4 > yaep:sum_list([]). 0
リスト Xs の中から最大値を求める関数 max_list(Xs) と最小値を求める関数 min_list(Xs) を定義してください。
> yaep:max_list([5, 6, 4, 7, 3, 8, 2, 9, 1]). 9 > yaep:min_list([5, 6, 4, 7, 3, 8, 2, 9, 1]). 1
要素 X の右隣に要素 Y があるかチェックする関数 adjacent(X, Y, Xs) を定義してください。
> yaep:adjacent(a, b, [a, b, c, d, e]). true > yaep:adjacent(d, e, [a, b, c, d, e]). true > yaep:adjacent(a, c, [a, b, c, d, e]). false > yaep:adjacent(e, d, [a, b, c, d, e]). false
要素 X が 要素 Y よりも前に出現しているか調べる関数 before(X, Y, Xs) を定義してください。
> yaep:before(a, b, [a, b, c, d, e]). true > yaep:before(a, e, [a, b, c, d, e]). true > yaep:before(c, b, [a, b, c, d, e]). false > yaep:before(e, a, [a, b, c, d, e]). false
整数 N から M までを格納したリストを作る関数 iota(N, M) を定義してください。
> yaep:iota(1, 8). [1,2,3,4,5,6,7,8] > yaep:iota(1, 1). [1] > yaep:iota(1, 0). []
リスト Xs から重複要素を取り除いて集合を生成する関数 set_of_list(Xs) を定義してください。
> yaep:set_of_list([a, b, c, a, d, e, b, f, g]). [c,a,d,e,b,f,g]
2 つの集合 Xs, Ys の和を求める関数 union(Xs, Ys) を定義してください。
> yaep:union([a, b, c, d], [c, d, e, f]). [a,b,c,d,e,f] > yaep:union([a, b, c, d], [e, f, g, h]). [a,b,c,d,e,f,g,h] > yaep:union([a, b, c, d], [a, b, c, d]). [a,b,c,d]
2 つの集合 Xs, Ys の積を求める関数 intersection(Xs, Ys) を定義してください。
> yaep:intersection([a, b, c, d], [c, d, e, f]). [c,d] > yaep:intersection([a, b, c, d], [e, f, g, h]). [] > yaep:intersection([a, b, c, d], [a, b, c, d]). [a,b,c,d]
2 つの集合 Xs, Ys の差を求める関数 difference(Xs, Ys) を定義してください。
> yaep:difference([a, b, c, d], [c, d, e, f]). [a,b] > yaep:difference([a, b, c, d], [e, f, g, h]). [a,b,c,d] > yaep:difference([a, b, c, d], [a, b, c, d]). []
2 つのソート済みのリスト Xs, Ys をひとつのソート済みのリストにまとめる関数 merge_list(Xs, Ys) を定義してください。
> yaep:merge_list(fun(X,Y)-> X < Y end, [1, 3, 5, 7], [2, 4, 6, 8]). [1,2,3,4,5,6,7,8] > yaep:merge_list(fun(X,Y)-> X < Y end, [1, 3, 5, 7], [1, 3, 5, 7, 9]). [1,1,3,3,5,5,7,7,9] > yaep:merge_list(fun(X,Y)-> X < Y end, [2, 4, 6], [2, 4, 6, 8]). [2,2,4,4,6,6,8]
関数 merge_list を使ってリスト Xs をソートする merge_sort(Pred, N, Xs) を定義してください。引数 N はリストの長さです。
> yaep:merge_sort(fun(X,Y)-> X < Y end, 9, [5, 6, 4, 7, 3, 8, 2, 9, 1]). [1,2,3,4,5,6,7,8,9] > yaep:merge_sort(fun(X,Y)-> X < Y end, 9, [9, 8, 7, 6, 5, 4, 3, 2, 1]). [1,2,3,4,5,6,7,8,9] > yaep:merge_sort(fun(X,Y)-> X < Y end, 10, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]). [1,2,3,4,5,6,7,8,9,10]
リスト Ps がリスト Xs の「接頭辞 (prefix) 」か判定する述語 prefix(Xs, Ps) を定義してください。接頭辞とは、列の先頭からある位置までの部分列のことです。たとえば、リスト [a, b, c, d] の接頭辞は [ ], [a], [a, b], [a, b, c], [a, b, c, d] の 5 つになります。
> yaep:prefix([a, b, c, d, e], [a, b]). true > yaep:prefix([a, b, c, d, e], [a, b, c]). true > yaep:prefix([a, b, c, d, e], [b, c]). false > yaep:prefix([a, b, c, d, e], []). true
リスト Ss がリスト Xs の「接尾辞 (suffix) 」か判定する述語 suffix(Xs, Ss) を定義してください。接尾辞とは、列のある位置から末尾までの部分列のことです。たとえば、リスト [a, b, c, d] の接尾辞は [a, b, c, d], [b, c, d], [c, d], [d], [ ] の 5 つになります。
> yaep:suffix([a, b, c, d, e], []). true > yaep:suffix([a, b, c, d, e], [e]). true > yaep:suffix([a, b, c, d, e], [d, e]). true > yaep:suffix([a, b, c, d, e], [b, d, e]). false
リスト Xs がリスト Ys の部分リストか判定する述語 sublist(Xs, Ys) を定義してください。
> yaep:sublist([b, c, d], [a, b, c, d, e]). true > yaep:sublist([c, d], [a ,b, c, d, e]). true > yaep:sublist([c], [a, b, c, d, e]). true > yaep:sublist([], [a, b, c, d, e]). true > yaep:sublist([a, c], [a, b, c, d, e]). false
リスト : 要素がただひとつか single([_]) -> true; single(_) -> false.
Erlang の場合、引数のリストとパターン [ _ ] がマッチングすれば、そのリストの要素は一つしかないことがわかります。length でリストの長さを求める必要はありません。
リスト : 要素がひとつ以上あるか pair([_ | _]) -> true; pair(_) -> false.
たとえば、リスト [1] と [X | Xs] を照合すると、X = 1, Xs = [ ] になります。したがって、引数のリストと [_ | _] がマッチングすれば、そのリストの要素は一つ以上あることがわかります。length でリストの長さを求める必要はありません。
なお、述語 pair の名前は Scheme の関数 pair? から拝借しました。
リスト : リスト Xs は Ys よりも長いか longer([], _) -> false; longer(_, []) -> true; longer([_ | Xs], [_ | Ys]) -> longer(Xs, Ys).
リストの先頭から順番にたどり、途中で Ys が空リストになれば xs の方が長いことがわかります。length でリストの長さを求めて比較するよりも、このプログラムの方が効率的だと思います。
リスト : リストの最後尾の要素を求める last([X]) -> X; last([_ | Xs]) -> last(Xs).
リスト : 最後尾の要素を取り除く butlast([_]) -> []; butlast([X | Xs]) -> [X | butlast(Xs)].
どちらの関数も引数が空リストの場合はエラーになります。last は単純な再帰定義でリストの最後尾を求めています。butlast の 1 番目の節は、要素がひとつしかないリストから最後尾の要素を取り除くと空リストになることを表しています。これが再帰の停止条件になります。あとは次の節で butlast を再帰呼び出しして、Xs から最後尾の要素を取り除いたリストに、引数のリストの先頭要素 X を追加していくだけです。
リスト : リストの先頭から N 個の要素を取り出す take(0, _) -> []; take(_, []) -> []; take(N, [X | Xs]) when N > 0 -> [X | take(N - 1, Xs)].
N が 0 の場合は空リストを返します。途中でリスト Xs が空になった場合も空リストを返します。最後の節で take を再帰呼び出しして、その先頭に要素 X を追加します。
リスト : リストの先頭から N 個の要素を削除する drop(0, Xs) -> Xs; drop(_, []) -> []; drop(N, [_ | Xs]) when N > 0 -> drop(N - 1, Xs).
最初の節で、削除する要素数が 0 であればリスト Xs をそのまま返します。次の節で、Xs が空リストの場合は空リストを返します。最後の節で drop を再帰呼び出しして、Xs から N - 1 個の要素を取り除いたリストを求めます。
リスト : 部分リストを取り出す subseq(N, M, Xs) when N > 0, M >= N -> take(M - N, drop(N - 1, Xs)).
subseq は drop と take を使うと簡単です。ガードで N と M の値をチェックします。drop で Xs から N - 1 個の要素を取り除き、そのリストから M - N 個の要素を take で取り出します。
リスト : リストの末尾から N 個の要素を取り除く butlastn(N, Xs) -> take(length(Xs) - N, Xs).
リスト Xs の長さを M とすると、リストの末尾から N 個の要素を取り除くことは、リストの先頭から M - N 個の要素を取り出すことと同じになります。butlastn は取り出す要素の個数を計算して take で取り出すだけです。
リスト : リストの分割 group(_, []) -> []; group(N, Xs) -> [take(N, Xs) | group(N, drop(N, Xs)) ].
関数 group は take と drop を使うと簡単に定義できます。Xs が空リストの場合は分割できないので空リストを返します。これが再帰の停止条件になります。Xs が空リストでない場合、まず take で N 個の要素を格納したリストを求めます。次に、N 個の要素を取り除いたリストを drop で求め、group を再帰呼び出ししてそのリストを分割します。あとはその返り値に take で取り出したリストを追加するだけです。
リスト : 要素の位置を求める
position_if(_, _, []) -> false;
position_if(P, N, [X | Xs]) ->
case P(X) of
true -> N;
false -> position_if(P, N + 1, Xs)
end.
position_if(P, Xs) -> position_if(P, 1, Xs).
positon_if/3 で要素の位置 N を求めます。リストの先頭から順番に調べていき、Pred の返り値が真であれば N を返します。Pred が真となる要素が見つからない場合は false を返します。
リスト : 要素の個数を求める
count_if(_, C, []) -> C;
count_if(P, C, [X | Xs]) ->
case P(X) of
true -> count_if(P, C + 1, Xs);
false -> count_if(P, C, Xs)
end.
count_if(P, Xs) -> count_if(P, 0, Xs).
count_if/3 で要素の個数をカウントします。引数 C を累積変数として使います。Pred(X) が真の場合、C を +1 して count_if/3 を再帰呼び出しします。そうでなければ C の値をそのままにして count_if/3 を再帰呼び出しします。リストが空リストの場合は C を返します。
リスト : 要素の合計値を求める sum_list([], A) -> A; sum_list([X | Xs], A) -> sum_list(Xs, A + X). sum_list(Xs) -> sum_list(Xs, 0).
sum_list/2 で要素の合計値を求めます。引数 A を累積変数として使っていて、sum_list/2 を再帰呼び出しするとき、A に X を加算します。リストが空リストの場合は A を返します。
リスト : リストから最大値と最小値を求める max_list([], Max) -> Max; max_list([X | Xs], Max) when X > Max -> max_list(Xs, X); max_list([_ | Xs], Max) -> max_list(Xs, Max). max_list([X | Xs]) -> max_list(Xs, X). min_list([], Min) -> Min; min_list([X | Xs], Min) when X < Min -> min_list(Xs, X); min_list([_ | Xs], Min) -> min_list(Xs, Min). min_list([X | Xs]) -> min_list(Xs, X).
max_list/2 (min_list/2) で最大値 (最小値) を求めます。引数 Max (Min) を累積変数として使っていて、そこに最大値 (または最小値) を保持します。最初に呼び出すとき、リストの先頭要素をセットします。あとは残りの要素を順番に調べていき、リストの先頭要素 X が Max (Min) よりも大きい (または小さい) 場合は、それを Max (Min) に置き換えるだけです。
リスト : X と Y は隣り合っているか adjacent(_, _, [_]) -> false; adjacent(X, Y, [X, Y | _]) -> true; adjacent(X, Y, [_ | Xs]) -> adjacent(X, Y, Xs).
関数 adjacent の定義は簡単です。リスト Xs が [X, Y | _] とマッチングすれば、X と Y は隣り合っていることがわかります。そうでなければ、adjacent を再帰呼び出しして先頭要素を取り除いたリストから探します。
リスト : X は Y よりも前に出現しているか before(_, _, []) -> false; before(X, Y, [X | Xs]) -> lists:member(Y, Xs); before(X, Y, [_ | Xs]) -> before(X, Y, Xs).
関数 before は関数 lists:member を使うと簡単にプログラムすることができます。最初の節と最後の節で、Xs の中から X を探しています。見つからない場合は、最初の節で false を返します。2 番目の節で X を見つけたら、残りのリスト Xs の中から Y を lists:member で探します。
リスト : 数列の生成 iota(N, M) when N > M -> []; iota(N, M) -> [N | iota(N + 1, M)]. % 別解 iota(N, N, A) -> [N | A]; iota(N, M, A) -> iota(N, M - 1, [M | A]). iota(N, M) -> iota(N, M, []).
最初の節で N > M になったら空リストを返します。次の節で、iota(N + 1, M) を再帰呼び出しして N + 1 から M までのリストを生成し、その先頭に N を追加します。別解は末尾再帰でプログラムしたものです。M を -1 していくところに注意してください。
リスト : 集合の生成
set_of_list([]) -> [];
set_of_list([X | Xs]) ->
case lists:member(X, Xs) of
true -> set_of_list(Xs);
false -> [X | set_of_list(Xs)]
end.
関数 set_of_list はリストから重複要素を取り除きます。先頭要素 X が残りのリスト Xs に含まれているか lists:member でチェックします。そうであれば、set_of_list を再帰呼び出しするだけです。含まれていなければ、set_of_list を再帰呼び出しして、その返り値の先頭に X を追加します。
リスト : 集合の和
union([], Ys) -> Ys;
union([X | Xs], Ys) ->
case lists:member(X, Ys) of
true -> union(Xs, Ys);
false -> [X | union(Xs, Ys)]
end.
Xs が空リストの場合は Ys を返します。これは空集合 (空リスト) と集合 Ys の和は Ys であることを表しています。次の節でリストを [X | Xs] に分解して、X が Ys に含まれていなければ、X を集合に追加します。含まれている場合は集合に追加しません。
リスト : 集合の積
intersection([], _) -> [];
intersection([X | Xs], Ys) ->
case lists:member(X, Ys) of
true -> [X | intersection(Xs, Ys)];
false -> intersection(Xs, Ys)
end.
Xs が空リストの場合は空リストを返します。これは空集合 (空リスト) と集合 Xs の積は空リストであることを表しています。次の節でリストを [X | Xs] に分解して、X が Ys に含まれていれば X を集合に追加します。含まれていない場合は集合に追加しません。
リスト : 集合の差
difference([], _) -> [];
difference([X | Xs], Ys) ->
case lists:member(X, Ys) of
true -> difference(Xs, Ys);
false -> [X | difference(Xs, Ys)]
end.
Xs が空リストの場合は空リストを返します。これは空集合 (空リスト) と集合 Ys の差は空リストであることを表しています。次の節でリストを [X | Xs] に分解して、X が Ys に含まれていなければ X を集合に追加します。含まれている場合は集合に追加しません。
リスト : リストのマージ
merge_list(_, [], Ys) -> Ys;
merge_list(_, Xs, []) -> Xs;
merge_list(P, [X | Xs], [Y | Ys]) ->
case P(X, Y) of
true -> [X | merge_list(P, Xs, [Y | Ys])];
false -> [Y | merge_list(P, [X | Xs], Ys)]
end.
要素の比較は述語 Pred で行います。Xs が空リストの場合は Ys を返し、Ys が空リストの場合は Xs を返します。次に、リストの先頭要素 X と Y を Pred で比較します。Pred(X, Y) が真の場合は X をリストに追加します。そうでなければ Y をリストに追加します。
リスト : マージソート
merge_sort(_, 0, _) -> [];
merge_sort(_, 1, [X | _]) -> [X];
merge_sort(P, 2, [X, Y | _]) ->
case P(X, Y) of
true -> [X, Y];
false -> [Y, X]
end;
merge_sort(P, N, Xs) ->
M = N div 2,
merge_list(P, merge_sort(P, M, Xs), merge_sort(P, N - M, drop(M, Xs))).
要素の比較は述語 Pred で行います。引数 N はリスト Xs の長さを表します。要素が一つしかない場合は [X] を返します。2 つある場合は要素 X と Y を Pred で比較し、Pred(X, Y) が真であれば [X, Y] を、そうでなければ [Y, X] を返します。それ以外の場合は、リスト Xs を二分割して merge_sort を再帰呼び出しし、その結果を merge_list でマージします。
リスト : 接頭辞の判定 prefix(_, []) -> true; prefix([], _) -> false; prefix([X | Xs], [X | Ys]) -> prefix(Xs, Ys); prefix(_, _) -> false.
接頭辞の判定は簡単です。最初の節は、空リストは接頭辞であることを表しています。次の節で Xs が空リストの場合、Ys は接頭辞ではないので false を返します。それ以外の場合は、Xs と Ys の先頭要素を比較して、等しい場合は prefix を再帰呼び出しして次の要素を比較します。等しくない場合は接頭辞ではないので false を返します。
リスト : 接尾辞の判定 suffix(Xs, Ys) -> drop(length(Xs) - length(Ys), Xs) =:= Ys.
接尾辞の判定も簡単です。リスト Xs と Ys の長さ (n1, n2) を求め、Xs の先頭から (n1 - n2) 個の要素を取り除きます。これで Xs と Ys の長さが等しくなるので、あとは単純に演算子 =:= で比較するだけです。
リスト : 部分リストの判定
sublist(Xs, Ys) ->
case prefix(Ys, Xs) of
true -> true;
false -> case Ys of
[] -> false;
[_ | Ys1] -> sublist(Xs, Ys1)
end
end.
sublist は prefix を使うと簡単です。最初の case で Xs が Ys の接頭辞であれば部分リストなので true を返します。false の場合は Ys をチェックします。Ys が空リストの場合、Xs は部分リストではないので false を返します。それ以外の場合は Ys の先頭要素を取り除いて、sublist を再帰呼び出しするだけです。