今回はちょっと便利な関数を問題形式で紹介します。元ネタは P-99: Ninety-Nine Prolog Problems です。拙作のページ Prolog Programming Yet Another Prolog Problems と同じ問題ですが、あしからずご了承くださいませ。
リストの要素がただひとつか調べる述語 single を定義してください。
val single = fn : 'a list -> bool
- single([]); val it = false : bool - single([1]); val it = true : bool - single([1, 2]); val it = false : bool
リストの要素がひとつ以上あるか調べる述語 pair を定義してください。
val pair = fn : 'a list -> bool
- pair([]); val it = false : bool - pair([1]); val it = true : bool - pair([1, 2]); val it = true : bool
リスト xs はリスト ys よりも長いか調べる述語 longer(xs, ys) を定義してください。
val longer = fn : 'a list * 'b list -> bool
- longer([1,2,3], [4,5,6]); val it = false : bool - longer([1,2,3], [4,5,6,7]); val it = false : bool - longer([1,2,3,4], [5,6,7]); val it = true : bool - longer([], [5,6,7]); val it = false : bool - longer([1,2,3,4], []); val it = true : bool
リストの最後尾を求める関数 last_pair と、最後尾の要素を取り除く関数 butlast を定義してください。
exception Empty_list val last_pair = fn : 'a list -> 'a list val butlast = fn : 'a list -> 'a list
- last_pair([1,2,3,4]); val it = [4] : int list - last_pair([1]); val it = [1] : int list - butlast([1,2,3,4]); val it = [1,2,3] : int list - butlast([1]); val it = [] : int list
リストの先頭から n 個の要素を取り出す関数 take(xs, n) を定義してください。
val take = fn : 'a list * int -> 'a list
- take([1,2,3,4,5], 3); val it = [1,2,3] : int list - take([1,2,3,4,5], 5); val it = [1,2,3,4,5] : int list - take([1,2,3,4,5], 0); val it = [] : int list
リストの先頭から n 個の要素を取り除く関数 drop(xs, n) を定義してください。
val drop = fn : 'a list * int -> 'a list
- drop([1,2,3,4,5], 3); val it = [4,5] : int list - drop([1,2,3,4,5], 5); val it = [] : int list - drop([1,2,3,4,5], 0); val it = [1,2,3,4,5] : int list
リストの n 番目から m - 1 番目の要素を部分リストとして取り出す関数 subseq xs n m を定義してください。なお、リストの要素は 0 から数え始めるものとします。
val subseq = fn : 'a list -> int -> int -> 'a list
- subseq [1,2,3,4,5,6] 1 4; val it = [2,3,4] : int list - subseq [1,2,3,4,5,6] 0 6; val it = [1,2,3,4,5,6] : int list - subseq [1,2,3,4,5,6] 2 3; val it = [3] : int list - subseq [1,2,3,4,5,6] 3 3; val it = [] : int list
リストの末尾から n 個の要素を取り除く関数 butlastn(xs, n) を定義してください。
val butlastn = fn : 'a list * int -> 'a list
val it = [] : int list - butlastn([1,2,3,4,5,6], 1); val it = [1,2,3,4,5] : int list - butlastn([1,2,3,4,5,6], 2); val it = [1,2,3,4] : int list - butlastn([1,2,3,4,5,6], 6); val it = [] : int list - butlastn([1,2,3,4,5,6], 0); val it = [1,2,3,4,5,6] : int list
リスト xs を長さ n の部分リストに分割する述語 group(xs, n) を定義してください。
val group = fn : 'a list * int -> 'a list list
- group([1,2,3,4,5,6],2); val it = [[1,2],[3,4],[5,6]] : int list list - group([1,2,3,4,5,6],3); val it = [[1,2,3],[4,5,6]] : int list list - group([1,2,3,4,5,6],4); val it = [[1,2,3,4],[5,6]] : int list list - group([1,2,3,4,5,6],6); val it = [[1,2,3,4,5,6]] : int list list
リスト xs の中から述語 pred が真を返す最初の要素を求める関数 find_if を定義してください。
val find_if = fn : ('a -> bool) -> 'a list -> 'a option
- find_if (fn(x) => x = 3) [1,2,3,4,5,6]; val it = SOME 3 : int option - find_if (fn(x) => x = 30) [1,2,3,4,5,6]; val it = NONE : int option
リストの中から述語 pred が真を返す最初の要素の位置を求める関数 position_if を定義してください。なお、リストの要素は 0 から数え始めるものとします。
val position_if = fn : ('a -> bool) -> 'a list -> int option
- position_if (fn(x) => x = 3) [1,2,3,4,5,6]; val it = SOME 2 : int option - position_if (fn(x) => x = 30) [1,2,3,4,5,6]; val it = NONE : int option
リストから述語 pred が真を返す要素の個数を求める関数 count_if を定義してください。
val count_if = fn : ('a -> bool) -> 'a list -> int
- count_if (fn(x) => x mod 2 = 0) [1,2,3,4,5,6,7]; val it = 3 : int - count_if (fn(x) => x mod 2 = 1) [1,2,3,4,5,6,7]; val it = 4 : int
リストの要素の合計値を求める述語 sum_list を定義してください。
val sum_list = fn : int list -> int
- sum_list([]); val it = 0 : int - sum_list([1,2,3,4,5,6,7,8]); val it = 36 : int
リストの中から最大値を求める関数 max_list と最小値を求める関数 min_list を定義してください。
val max_list = fn : int list -> int val min_list = fn : int list -> int
- max_list([1,2,3,4,5,6,7,8]); val it = 8 : int - max_list([9,1,2,3,4,5,6,7,8]); val it = 9 : int - max_list([1,2,3,4,50,6,7,8]); val it = 50 : int - min_list([1,2,3,4,5,6,7,8]); val it = 1 : int - min_list([1,2,3,4,5,6,7,8,0]); val it = 0 : int - min_list([1,2,3,4,0,6,7,8]); val it = 0 : int
要素 x の右隣に要素 y があるかチェックする関数 adjacent x y ls を定義してください。
val adjacent = fn : ''a * ''a * ''a list -> bool
- adjacent(1,2,[0,1,2,3,4,5]); val it = true : bool - adjacent(1,2,[0,1,0,2,3,4,5]); val it = false : bool
整数 n から m までを格納したリストを作る関数 iota(n, m) を定義してください。
val iota = fn : int * int -> int list
- iota(0, 10); val it = [0,1,2,3,4,5,6,7,8,9,10] : int list - iota(10, 20); val it = [10,11,12,13,14,15,16,17,18,19,20] : int list - iota(1,0); val it = [] : int list
リストから重複要素を取り除いて集合を生成する関数 set_of_list を定義してください。
val set_of_list = fn : ''a list -> ''a list
- set_of_list([1,2,3,1,2,3,4,1,2,3,4,5,6]); val it = [1,2,3,4,5,6] : int list - set_of_list([1,2,3,4,5]); val it = [1,2,3,4,5] : int list
2 つの集合の和を求める関数 union を定義してください。
val union = fn : ''a list * ''a list -> ''a list
- union([1,2,3,4,5,6], [4,5,6,7,8,9]); val it = [1,2,3,4,5,6,7,8,9] : int list - union([1,2,3,4], [5,6,7,8]); val it = [1,2,3,4,5,6,7,8] : int list - union([1,2,3,4], [1,2,3,4]); val it = [1,2,3,4] : int list
2 つの集合の積を求める関数 intersection を定義してください。
val intersection = fn : ''a list * ''a list -> ''a list
- intersection([1,2,3,4,5], [3,4,5,6,7]); val it = [3,4,5] : int list - intersection([1,2,3,4,5], [6,7,8,9,10]); val it = [] : int list - intersection([1,2,3,4,5], [1,2,3,4,5]); val it = [1,2,3,4,5] : int list
2 つの集合の差を求める関数 difference を定義してください。
val difference = fn : ''a list * ''a list -> ''a list
- difference([1,2,3,4,5], [1,2,3,4,5]); val it = [] : int list - difference([1,2,3,4,5], [1,3,5]); val it = [2,4] : int list - difference([], [1,3,5]); val it = [] : int list
2 つのソート済みのリストをひとつのソート済みのリストにまとめる関数 merge_list を定義してください。
val merge_list = fn : ('a * 'a -> bool) * 'a list * 'a list -> 'a list
- merge_list(op <, [1,3,5,7],[2,4,6,8]); val it = [1,2,3,4,5,6,7,8] : int list - merge_list(op <, [1,3,5,7],[0,2,4,6,8]); val it = [0,1,2,3,4,5,6,7,8] : int list - merge_list(op <, [0,1,3,5,7],[2,4,6,8]); val it = [0,1,2,3,4,5,6,7,8] : int list
関数 merge_list を使ってリストをソートする merge_sort を定義してください。
val merge_sort = fn : ('a * 'a -> bool) * int * 'a list -> 'a list
- merge_sort(op <, 10, [5,6,4,7,3,8,2,9,1,0]); val it = [0,1,2,3,4,5,6,7,8,9] : int list
リスト ps がリスト ls の「接頭辞 (prefix) 」か判定する述語 prefix(ls, ps) を定義してください。接頭辞とは、列の先頭からある位置までの部分列のことです。たとえば、リスト [1, 2, 3, 4] の接頭辞は [ ], [1], [1, 2], [1, 2, 3], [1, 2, 3, 4] の 5 つになります。
val prefix = fn : ''a list * ''a list -> bool
- prefix([1,2,3,4,5],[1,2,3]); val it = true : bool - prefix([1,2,3,4,5],[1,2]); val it = true : bool - prefix([1,2,3,4,5],[1]); val it = true : bool - prefix([1,2,3,4,5],[]); val it = true : bool - prefix([1,2,3,4,5],[3,4,5]); val it = false : bool
リスト ss がリスト ls の「接尾辞 (suffix) 」か判定する述語 suffix(ls, ss) を定義してください。接尾辞とは、列のある位置から末尾までの部分列のことです。たとえば、リスト [1, 2, 3, 4] の接尾辞は [1, 2, 3, 4], [2, 3, 4], [3, 4], [4], [ ] の 5 つになります。
val suffix = fn : ''a list * ''a list -> bool
- suffix([1,2,3,4,5],[3,4,5]); val it = true : bool - suffix([1,2,3,4,5],[4,5]); val it = true : bool - suffix([1,2,3,4,5],[5]); val it = true : bool - suffix([1,2,3,4,5],[]); val it = true : bool - suffix([1,2,3,4,5],[3,4]); val it = false : bool
リスト xs がリスト ls の部分リストか判定する述語 sublist(xs, ls) を定義してください。
val sublist = fn : ''a list * ''a list -> bool
- sublist([2,3,4],[1,2,3,4,5]); val it = true : bool - sublist([2,4],[1,2,3,4,5]); val it = false : bool - sublist([3,4,5],[1,2,3,4,5]); val it = true : bool - sublist([1,2,3],[1,2,3,4,5]); val it = true : bool
リスト：要素がただひとつか fun single([_]) = true | single(_) = false
SML/NJ の場合、引数のリストと [ _ ] がマッチングすれば、そのリストの要素は一つしかないことがわかります。length でリストの長さを求める必要はありません。
リスト：要素がひとつ以上あるか fun pair(_::_) = true | pair(_) = false
たとえば、リスト [1] と x::xs を照合すると、x = 1, xs = [ ] になります。したがって、引数のリストと _::_ がマッチングすれば、そのリストの要素は一つ以上あることがわかります。length でリストの長さを求める必要はありません。
なお、述語 pair の名前は Scheme の関数 pair? から拝借しました。
リスト：リスト xs は ys よりも長いか fun longer([], _) = false | longer(_, []) = true | longer(_::xs, _::ys) = longer(xs, ys)
リストの先頭から順番にたどり、途中で ys が空リストになれば xs の方が長いことがわかります。length でリストの長さを求めて比較するよりも、このプログラムの方が効率的だと思います。
リスト： リストの最後尾を求める exception Empty_list fun last_pair([]) = raise Empty_list | last_pair([x]) = [x] | last_pair(_::xs) = last_pair(xs)
リスト：最後尾の要素を取り除く fun butlast([]) = raise Empty_list | butlast([_]) = [] | butlast(x::xs) = x :: butlast(xs)
どちらの関数も引数が空リストの場合はエラー Empty_list を送出します。last_pair は単純な再帰定義でリストの最後尾を求めています。butlast の 2 番目の節は、要素がひとつしかないリストから最後尾の要素を取り除くと空リストになることを表しています。これが再帰の停止条件になります。あとは次の節で butlast を再帰呼び出しして、xs から最後尾の要素を取り除いたリストに、引数のリストの先頭要素 x を追加していくだけです。
リスト：リストの先頭から n 個の要素を取り出す fun take(_, 0) = [] | take([], n) = [] | take(x::xs, n) = x :: take(xs, n - 1)
n が 0 の場合は空リストを返します。途中でリスト xs が空になった場合も空リストを返します。最後の節で take を再帰呼び出しして、その先頭に要素 x を追加します。
なお、SML/NJ の List モジュールには同等の機能を持つ関数 take が用意されています。
リスト：リストの先頭から n 個の要素を削除する fun drop(xs, 0) = xs | drop([], _) = [] | drop(_::xs, n) = drop(xs, n - 1)
最初の節で、削除する要素数が 0 であればリスト xs をそのまま返します。次の節で、xs が空リストの場合は空リストを返します。最後の節で drop を再帰呼び出しして、xs から n - 1 個の要素を取り除いたリストを求めます。
なお、SML/NJ の List モジュールには同等の機能を持つ関数 drop が用意されています。
リスト：部分リストを取り出す fun subseq xs s e = if s > e then [] else take(drop(xs, s), e - s)
subseq は drop と take を使うと簡単です。if 文で s と e の値をチェックして、s > e ならば空リストを返します。そうでなければ、drop で xs から s 個の要素を取り除き、そのリストから e - s 個の要素を take で取り出します。
リスト：リストの末尾から n 個の要素を取り除く fun butlastn(xs, n) = take(xs, length(xs) - n)
リスト xs の長さを m とすると、リストの末尾から n 個の要素を取り除くことは、リストの先頭から m - n 個の要素を取り出すことと同じになります。butlastn は取り出す要素の個数を計算して take で取り出すだけです。
リスト：リストの分割 fun group([], _) = [] | group(xs, n) = take(xs, n) :: group(drop(xs, n), n)
関数 group は take と drop を使うと簡単に定義できます。xs が空リストの場合は分割できないので空リストを返します。これが再帰の停止条件になります。xs が空リストでない場合、まず take で n 個の要素を格納したリストを求めます。次に、n 個の要素を取り除いたリストを drop で求め、group を再帰呼び出ししてそのリストを分割します。あとはその返り値に take で取り出したリストを追加するだけです。
リスト : 述語が真となる要素を探索する fun find_if _ [] = NONE | find_if pred (x::xs) = if pred x then SOME x else find_if pred xs
リストの先頭から順番に調べていき、pred の返り値が真であれば SOME x を返します。pred が真となる要素が見つからない場合は NONE を返します。なお、SML/NJ の List モジュールには同等の機能を持つ関数 find が用意されています。
リスト：要素の位置を求める
fun position_if pred xs =
let
fun iter [] _ = NONE
| iter (x::xs) i = if pred x then SOME i else iter xs (i + 1)
in
iter xs 0
end
局所関数 iter で要素の位置 i を求めます。リストの先頭から順番に調べていき、pred の返り値が真であれば SOME i を返します。pred が真となる要素が見つからない場合は NONE を返します。
リスト：要素の個数を求める
fun count_if pred xs =
let
fun iter [] a = a
| iter (x::xs) a = if pred x then iter xs (a + 1) else iter xs a
in
iter xs 0
end
(* 別解 *)
fun count_if1 pred xs =
foldl (fn(x, a) => if pred x then a + 1 else a) 0 xs
局所関数 iter で要素の個数をカウントします。引数 a を累積変数として使います。pred x が真の場合、a を +1 して iter を再帰呼び出しします。そうでなければ a の値をそのままにして iter を再帰呼び出しします。リストが空リストの場合は a を返します。別解は畳み込みを行う関数 foldl を使って書き直したものです。
リスト：要素の合計値を求める
fun sum_list xs =
let
fun iter [] a = a
| iter (x::xs) a = iter xs (a + x)
in
iter xs 0
end
(* 別解 *)
fun sum_list1 xs = foldl (fn(x, a) => x + a) 0 xs
局所関数 iter で要素の合計値を求めます。引数 a を累積変数として使っていて、iter を再帰呼び出しするとき、a に x を加算します。リストが空リストの場合は a を返します。別解は foldl を使って書き直したものです。
リスト：リストから最大値と最小値を求める
fun max_list [] = raise Empty_list
| max_list (x::xs) =
let
fun iter [] a = a
| iter (x::xs) a = if x > a then iter xs x else iter xs a
in
iter xs x
end
fun min_list [] = raise Empty_list
| min_list (x::xs) =
let
fun iter [] a = a
| iter (x::xs) a = if x < a then iter xs x else iter xs a
in
iter xs x
end
(* 別解 *)
fun max_list1 [] = raise Empty_list
| max_list1 (x::xs) =
List.foldl (fn(b, a) => if b > a then b else a) x xs
fun min_list1 [] = raise Empty_list
| min_list1 (x::xs) =
List.foldl (fn(b, a) => if b < a then b else a) x xs
どちらの関数も局所変数 iter で最大値 (最小値) を求めます。引数 a を累積変数として使っていて、そこに最大値 (または最小値) を保持します。最初に呼び出すとき、リストの先頭要素をセットします。あとは残りの要素を順番に調べていき、リストの先頭要素 x が a よりも大きい (または小さい) 場合は、それを a に置き換えるだけです。別解は foldl で書き直したものです。
ところで、このままでは int list だけにしか適用することができません。他のデータ型にも適用したい場合は、次のように述語を渡して高階関数にするとよいでしょう。
リスト : 高階関数バージョン fun max_list2 _ [] = raise Empty_list | max_list2 pred (x::xs) = foldl (fn(b, a) => if pred(b, a) then b else a) x xs
val max_list2 = fn : ('a * 'a -> bool) -> 'a list -> 'a
簡単な実行例を示します。
- max_list2 (op >) [1.1, 2.2, 3.3, 6.6, 5.5, 4.4]; val it = 6.6 : real - max_list2 (op >) ["abc", "def", "ghi", "ABC"]; val it = "ghi" : string - val max_real_list : real list -> real = max_list2 (op >); val max_real_list = fn : real list -> real - max_real_list [1.1, 2.2, 3.3, 6.6, 5.5, 4.4]; val it = 6.6 : real - val max_string_list : string list -> string = max_list2 (op >); val max_string_list = fn : string list -> string - max_string_list ["abc", "def", "ghi", "ABC"]; val it = "ghi" : string
リスト：a と b は隣り合っているか fun adjacent(_, _, []) = false | adjacent(_, _, [_]) = false | adjacent(a, b, x::y::ys) = if x = a andalso y = b then true else adjacent(a, b, y::ys)
関数 adjacent の定義は簡単です。リストが x::y::ys とマッチングして、x = a かつ y = b を満たせば、a と b は隣り合っていることがわかります。そうでなければ、adjacent を再帰呼び出しして残りのリスト y::ys から探します。
リスト：数列の生成
fun iota(n, m) =
let
fun iter i a =
if i < n then a else iter (i - 1) (i::a)
in
iter m []
end
局所関数 iter でリストを生成します。累積変数 a にリストを保持します。後ろ (m) から数値を生成してリストに格納していくことに注意してください。i < n になったら a を返します。
リスト：集合の生成
fun mem(_, []) = false
| mem(x, y::ys) = if x = y then true else mem(x, ys)
fun set_of_list xs =
let
fun iter [] a = rev a
| iter (y::ys) a =
if mem(y, ys) then iter ys a else iter ys (y::a)
in
iter xs []
end
関数 set_of_list はリストから重複要素を取り除きます。実際の処理は局所関数 iter で行います。リストの先頭要素 y が残りのリスト ys に含まれているか関数 mem でチェックします。同じ要素がない場合は累積変数 a に y を追加します。
リスト：集合の和
fun union([], ys) = ys
| union(x::xs, ys) =
if mem(x, ys) then union(xs, ys)
else x :: union(xs, ys)
(* 別解 *)
fun union1(xs, ys) =
foldl (fn(x, a) => if mem(x, ys) then a else x::a) ys xs
xs が空リストの場合は ys を返します。これは空集合 (空リスト) と集合 ys の和は ys であることを表しています。次の節でリストを x::xs に分解して、x が ys に含まれていなければ、x を集合に追加します。含まれている場合は集合に追加しません。別解は foldl で書き直したものです。
リスト：集合の積
fun intersection([], _) = []
| intersection(x::xs, ys) =
if mem(x, ys) then x :: intersection(xs, ys)
else intersection(xs, ys)
(* 別解 *)
fun intersection1(xs, ys) =
foldl (fn(x, a) => if mem(x, ys) then x::a else a) [] xs
xs が空リストの場合は空リストを返します。これは空集合 (空リスト) と集合 ys の積は空リストであることを表しています。次の節でリストを x::xs に分解して、x が ys に含まれていれば x を集合に追加します。含まれていない場合は集合に追加しません。別解は foldl で書き直したものです。
リスト：集合の差
fun difference([], _) = []
| difference(x::xs, ys) =
if mem(x, ys) then difference(xs, ys)
else x :: difference(xs, ys)
(* 別解 *)
fun difference1(xs, ys) =
foldl (fn(x, a) => if mem(x, ys) then a else x::a) [] xs
xs が空リストの場合は空リストを返します。これは空集合 (空リスト) と集合 ys の差は空リストであることを表しています。次の節でリストを x::xs に分解して、x が ys に含まれていなければ x を集合に追加します。含まれている場合は集合に追加しません。別解は foldl で書き直したものです。
リスト：リストのマージ
fun merge_list(_, [], ys) = ys
| merge_list(_, xs, []) = xs
| merge_list(pred, x as x1::xs, y as y1::ys) =
if pred(x1, y1) then x1 :: merge_list(pred, xs, y)
else y1 :: merge_list(pred, x, ys)
要素の比較は述語 pred で行います。xs が空リストの場合は ys を返し、ys が空リストの場合は xs を返します。次に、x と y の先頭要素 x1 と y1 を pred で比較します。pred(x1, y1) が真の場合は x1 をリストに追加します。そうでなければ y1 をリストに追加します。
リスト：マージソート
fun merge_sort(_, _, []) = []
| merge_sort(_, 1, x::_) = [x]
| merge_sort(pred, 2, x1::x2::_) =
if pred(x1, x2) then [x1, x2] else [x2, x1]
| merge_sort(pred, n, xs) =
let
val m = n div 2
in
merge_list(pred, merge_sort(pred, m, xs), merge_sort(pred, n - m, drop(xs, m)))
end
要素の比較は述語 pred で行います。引数 n はリスト xs の長さを表します。要素が一つしかない場合は [x] を返します。2 つある場合は要素 x1 と x2 を pred で比較し、pred(x1, x2) が真であれば [x1, x2] を、そうでなければ [x2, x1] を返します。それ以外の場合は、リスト xs を二分割して merge_sort を再帰呼び出しし、その結果を merge_list でマージします。
リスト：接頭辞の判定 fun prefix(_, []) = true | prefix([], _) = false | prefix(x::xs, y::ys) = if x = y then prefix(xs, ys) else false
接頭辞の判定は簡単です。最初の節は、空リストは接頭辞であることを表しています。次の節で ls が空リストの場合、ks は接頭辞ではないので false を返します。それ以外の場合は、ls と ks の先頭要素を比較して、等しい場合は prefix を再帰呼び出しして次の要素を比較します。等しくない場合は接頭辞ではないので false を返します。
リスト：接尾辞の判定
fun suffix(ls, ks) =
let
val n1 = List.length(ls)
val n2 = List.length(ks)
in
ks = drop(ls, n1 - n2)
end
接尾辞の判定も簡単です。リスト ls と ks の長さを求め、ls の先頭から (n1 - n2) 個の要素を取り除きます。これで ls と ks の長さが等しくなるので、あとは単純に演算子 = で比較するだけです。
リスト：部分リストの判定 fun sublist(ks, ls) = if prefix(ls, ks) then true else if ls = [] then false else sublist(ks, tl(ls))
sublist は prefix を使うと簡単です。最初の if で ks が ls の接頭辞であれば部分リストなので true を返します。ls が空リストの場合、ks は部分リストではないので false を返します。それ以外の場合は ls の先頭要素を取り除いて、sublist を再帰呼び出しするだけです。