6.4 リスト処理の基本関数
問 6.4
null，hd，tl の各関数をパタンマッチングを使って定義せよ．
解答例
fun null nil = true
| null (h::_) = false
fun hd (h::_) = h
fun tl (_::t) = t
問 6.5
@，rev，map の各関数をパタンマッチングを使わずに定義せよ．
解答例
fun op @ (L1,L2) = if null L1 then L2 else hd L1 :: (tl L1 @ L2) fun rev L = if null L then nil else rev (tl L) @ [hd L] fun map f L = if null L then nil else f (hd L) :: map f (tl L)
問 6.6
以下のリスト処理関数を定義せよ．
-
1.
整数のリストの総和を求める関数 sumList．
-
2.
要素がリストに存在するか否かを判定する関数 member．
-
3.
リスト中の重複する要素を取り除く関数 unique．
-
4.
’a -> bool 型の関数と ’a list 型のリストを受け取り， リストから関数が true を返す要素のみを取り出す関数 filter．
-
5.
リストのリストを1つのリストにする関数 flatten． たとえば，
- flatten [[1],[1,2],[1,2,3]]; val it = [1,1,2,1,2,3] : int list のような動作をする． -
6.
文字列のリストと文字列の組を受け取り，各リストの要素を文字列でつないだ文字 列を返す関数 splice． たとえば，
- splice (["","home","ohori","papers","mltext"],"/"); val it = ”/home/ohori/papers/mltext” : string のような動作をする．
解答例
fun sumList nil = 0
| sumList (h::t) = h + sumList t
fun member a nil = false
| member a (h::tl) = a = h orelse member a tl
fun unique nil = nil
| unique (h::tl) =
let
val tl’ = unique tl
in
if member h tl’ then tl’ else h::tl’
end
fun filter P nil = nil
| filter P (h::tl) =
if P h then h :: filter P tl else filter P tl
fun flatten nil = nil
| flatten (h::tl) = h @ flatten tl
fun splice (nil,_) = ""
| splice ([x],_) = x
| splice ((h::t),s) = h ^ s ^ splice (t,s);
問 6.7
以下のリスト処理関数を定義せよ．
-
1.
与えられたリストの先頭から始まるすべての部分リストを返す関数 prefixListおよび 最後までのすべての部分リストを返す関数 suffixList． たとえば
- prefixList [1,2,3]; val it = [[1],[1,2],[1,2,3]]: int list list - suffixList [1,2,3]; val it = [[1,2,3],[2,3],[3],[]]: int list list
のような動作をする． -
2.
与えられたリストの中のすべての部分リストを返す関数 allIntervals． たとえば，
- allIntervals [1,2,3]; val it = [[1],[1,2],[1,2,3],[2],[2,3],[3]] : int list list
のような動作をする． （ヒント： suffixList， prefixList， map， flatten を組み合わせることを考えよ．） -
3.
与えられたリストを集合とみなし，そのすべての部分集合を返す関数 powerSet． ただし，与えられたリストは重複を含まないと仮定してよい．
-
4.
与えられたリストを集合とみなし，その中から与えられた数の要素 を取り出して作られるすべての順列をリストとして返す関数 allPermutations． たとえば
- allPermutations [1,2,3] 2; val it = [[1,2],[2,1],[1,3],[3,1],[2,3],[3,2]]: int list list
のような動作をする．（ヒント：flatten，powerSet，permutations を組み合わせることを考えよ．）
解答例
fun prefixList nil = nil
| prefixList (h::tl) =
let
val L = prefixList tl
in
[h] :: map (fn y => h::y) L
end
fun suffixList nil = [[]]
| suffixList (h::t) =
let
val L = suffixList t
in
(h::t)::L
end;
fun allIntervals L = flatten (map prefixList (suffixList L))
fun powerSet nil = [nil]
| powerSet (h::t) =
let
val PT = powerSet t
in
map (fn x => h::x) PT @ PT
end
fun permutations L =
let fun insertAll s nil = [[s]]
| insertAll s (h::t) =
let val L = insertAll s t
in (s::(h::t)) :: (map (fn x => h::x) L)
end
in foldr (fn (x,y) => foldr (fn (a,b) => insertAll x a @ b) nil y)
[nil]
L
end;
fun allPermutations L n =
let val subs = filter (fn x => length x = n) (powerSet L)
in flatten (map permutations subs)
end;