プログラミング言語 Standard ML 入門 (問題の解答例)

6.5 リスト処理の一般構造と汎用のリスト処理関数

問 6.8

以下の各関数が行う処理に関して上記の分析を行い，対応する $Z$ と $f$ を MLの式として定義せよ．

•

map
•

@
•

flatten
•

filter
•

permutations

解答例

•

map $f$ $L$
リストがnilの時はnil、リストが $h$ :: $t$ の形なら，部分リスト $t$ に対する値 $R$ を計算すると、 $R$ は、 $t$ に $f$ をmapした結果であるから、全体の結果はf h :: $R$ である。従って、 $Z=\mbox{\tt nil}$ 、 $f=\mbox{\tt fn (h,R) => f h :: R}$ である。
•

$L1$ @ $L2$
第一要素L1でfoldする。 L1がnilの時は第２要素L2、 L1が $h$ :: $t$ の形なら， $R$ はtとL2の連結結果のはずであるから、全体の結果はh :: $R$ である。従って、 $Z=\mbox{\tt L2}$ 、 $f=\mbox{\tt fn (h,R) => h :: R}$ である。
•

flatten L
リストがnilの時はnil、リストが $h$ :: $t$ の形なら，部分リスト $t$ に対する値 $R$ を計算すると、 $h$ はリスト、 $R$ は $t$ をflattenした結果のはずであるから、全体の結果はh @ $R$ である。従って、 $Z=\mbox{\tt nil}$ 、 $f=\mbox{\tt fn (h,R) => h @ R}$ である。
•

filter P L
リストがnilの時はnil、リストが $h$ :: $t$ の形なら，部分リスト $t$ に対する値 $R$ を計算すると、 $R$ は $t$ をfilterした結果のはずであるから、全体の結果は、もし $P$ hがtrueならh @ $R$ 、folseなら $R$ である。従って、 $Z=\mbox{\tt nil}$ 、 $f=\mbox{\tt fn (h,R) => if P h then h::R else R}$ である。
•

permutations
リストがnilの時は[nil]、リストが $h$ :: $t$ の形なら，部分リスト $t$ に対する値 $R$ を計算すると、 $R$ は $t$ をpermutationした結果のはずであるから、全体の結果は、 $R$ の各要素に対して、その可能な位置に $h$ を挿入したリストすべてである。従って、 $Z=\mbox{\tt[nil]}$ 、 $f=\mbox{\tt fn (h,R) => foldr (fn (a,b) => insertAll h a @ b) nil R}$ である。

問 6.9

以下のリスト処理関数を foldr を使って定義せよ．

1.

map， flatten， member， unique， prefixList， permutations の各関数．
2.

リストと条件（bool型の関数）を受け取り，リストの中に条件を満たす要素が存在するか否か判定する関数 existsおよび，リストの中のすべての要素が条件を満たすか判定する関数 forall．定義上，任意の条件関数 $P$ に対して，exists $P$ nil は false，forall $P$ nil は true を返すことに注意せよ．
3.

整数リストのプレフィックス和を求める関数 prefixSum．ただし，整数リスト $[a_{1},a_{2},\mbox{$\cdots$},a_{n}]$ のプレフィックス和は $[a_{1},a_{1}+a_{2},\cdots,a_{1}+\cdots a_{n-1},a_{1}+\cdots+a_{n}]$ である．

解答例

   fun map f L = foldr (fn (h,R) => f h :: R) nil L

   fun flatten L = foldr (fn (h,R) =>  h @ R) nil L

   fun member e L = foldr (fn (h,R) => R orelse e = h) false L

   fun unique L =
       foldr (fn (h,R) => if member h R then R else h :: R) nil L

   fun prefixList L =
       foldr (fn (x,l)=> [x]::(map (fn y => x::y) l)) nil L;

   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 exists p L =
       foldr (fn (y,r) => p y orelse r) false L

   fun forall p L =
       foldr (fn (y,r) => p y andalso r) true L

   fun prefixSum L =
       foldr (fn (x,y) => x::(map (fn z => z + x) y)) nil L

問 6.10

foldr の処理は，以下のような等式の結果を求めることと理解できる．

\mbox{{\tt foldr $f$ $Z$ [$a_{1}$,$a_{2}$,$\cdots$,$a_{n}$]}}=f(a_{1},f(a_{2},% f(\cdots,f(a_{n},Z)\cdots)))

これに対して，以下のような動作をする foldl もトップレベルで定義されている．

\mbox{{\tt foldr $f$ $Z$ [$a_{1}$,$\cdots$,$a_{n-1}$,$a_{n}$]}}=f(a_{n},f(a_{n% -1},f(\cdots,f(a_{1},Z)\cdots)))

1.

foldl の定義を与えよ．
2.

foldl を使って rev を定義せよ．

解答例

   fun foldl f z nil = z
     | foldl f z (h::t) = foldl f (f (h,z)) t

   fun rev L = foldl (op ::) nil L

問 6.11

関係のリスト表現で，同一の要素が一回しか含まれないとき，正規形と呼ぶことにする．上で定義した tc は，入力が正規形であっても結果は正規形とは限らない．

1.

tc $R$ が正規形とならない正規形のリスト $R$ の例を挙げよ．
2.

正規形の入力に対しては，必ず正規形の結果を返すように，tc の定義を修正せよ．

解答例正規形の入力 $R$ に対して、tc $R$ が正規形にならない例： tc [(1,1),(1,2),(2,3)]。

正規形を維持するためのtcの改良：簡単な解決法は、

   fun normalTc R = unique (tc R)

問 6.12

関係のリスト表現に関する以下の関数を定義せよ．

1.

関係 $R$ と組 $(a,b)$ に対して， $(a,b)\in R$ か否かを判定する関数 isRelated．
2.

関係 $R$ と点 $a$ に対して，集合 $\{x\ |\ (a,x)\in R\}$ を求める関数 targetOf．
3.

関係 $R$ と点 $a$ に対して，集合 $\{x\ |\ (x,a)\in R\}$ を求める関数 sourceOf．
4.

関係 $R$ の逆 $R^{-1}$ を求める関数 inverseRel．

解答例

   fun isRelated (R,a) = member a R

   fun targetOf (R,a) = filter (fn (x,y) => x = a) R

   fun sourceOf (R,a) = filter (fn (x,y) => y = a) R

   fun inverseRel R = map (fn (a,b) => (b, a)) R