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

\tau

6.1 リスト構造

問 6.1

本問では，無限集合の簡単な扱いに慣れている読者のために，リストの数学的なモデルを考察する．ポインタ構造を無視すると，上記のリスト構造は以下のように入れ子になった組とみなせる．

({\rm v1},({\rm v2},\cdots({\rm vn},{\rm nil})\cdots))

v1,v2, $\cdots$ ,vnが属する集合を $A$ とし，集合 $A$ と $B$ の直積 $A\times B$ を以下のように定義する．

A\times B=\{(a,b)|a\in A,b\in B\}

さらに，nilを唯一の要素とする集合を $N i l$ とする．すると， $n$ 個の要素からなるリストは以下のような集合の要素と考えられる．

\underbrace{A\times(A\times(\cdots(A}_{\mbox{$n$個の$A$}}\times Nil)\cdots))

$n$ 個に限らず，集合 $A$ の要素からなるすべてのリストの集合は，集合に関する以下のような方程式の解と考えることができる．

L=Nil\cup(A\times L)

この方程式の最小解を以下の手順で求めよ．

1.

集合の系列 $X_{i}$ を以下のように定める．

$\displaystyle X_{0}$ $\displaystyle=$ $\displaystyle Nil$

$\displaystyle X_{i+1}$ $\displaystyle=$ $\displaystyle X_{i}\cup(A\times X_{i})$

もし $L$ に関する方程式が解を持てば，任意の $i$ に対して，

$X_{i}\subseteq L$

であることを $i$ に関する数学的帰納法で示せ．
2.

この系列を用いて，集合 $X$ を以下のように定義する．

$X=\bigcup_{i\geq 0}X_{i}$

このとき， $X$ は上記の方程式を満たすことを示し，したがって， $X$ が上記方程式の最小解であることを確認せよ．

解答例

1.

${\cal L}$ を方程式の任意の解とし、 $X_{i}\subseteq{\cal L}$ を $i$ に関する数学的帰納法で示す。

$(i=0)$ の場合。

$\displaystyle X_{0}$ $\displaystyle=$ $\displaystyle Nil$

$\displaystyle\subseteq$ $\displaystyle Nil\cup(A\times{\cal L})$

$\displaystyle=$ $\displaystyle{\cal L}$

$(i>k+1)$ の場合。

$\displaystyle X_{k+1}$ $\displaystyle=$ $\displaystyle X_{k}\cup(A\times X_{k})$

$\displaystyle\subseteq$ $\displaystyle{\cal L}\cup(A\times{\cal L})$

$\displaystyle=$ $\displaystyle{\cal L}$
2.

$X=Nil\cup A\times X$

を示せば良い。集合の等式であるから、 $X\subseteq Nil\cup(A\times X)$ および $Nil\cup(A\times X)\subseteq X$ を示せばよい。

$X\subseteq Nil\cup(A\times X)$ は、 $X=\bigcup_{i\geq 0}X_{i}$ の要素集合 $X_{i}$ について、 $X_{i}\subseteq Nil\cup(A\times X)$ を示せばよい。定義の形から、ほぼ自明である。厳密には、 $i$ に関する帰納法による。 $X_{0}=Nil\subseteq Nil\cup(A\times X)$ であり、成立する。 $i=K+1$ の場合、 $X_{k+1}=X_{k}\cup A\times X_{k}$ である。帰納法の仮定から $X_{k}\subseteq Nil\cup(A\times X)$ である、また、定義から、 $A\times X_{k}\subseteq A\times X$ であり、従って、 $X_{k+1}\subseteq A\times X$ である。

$Nil\cup A\times X\subseteq X$ を示すには、 $Nil\subseteq X$ と任意の $i$ に関して、 $A\times X_{i}\subseteq X$ を示せば十分である。前者は、 $Nil=X_{0}\subseteq X$ であり、成立する。後者は、定義より、 $A\times X_{i}\subseteq X_{i}\cup A\times X_{i}=X_{i+1}\subseteq X$ であり成立する。

	$\displaystyle X_{0}$	$\displaystyle=$	$\displaystyle Nil$
	$\displaystyle X_{i+1}$	$\displaystyle=$	$\displaystyle X_{i}\cup(A\times X_{i})$

$\displaystyle X_{k+1}$	$\displaystyle=$	$\displaystyle X_{k}\cup(A\times X_{k})$
	$\displaystyle\subseteq$	$\displaystyle{\cal L}\cup(A\times{\cal L})$
	$\displaystyle=$	$\displaystyle{\cal L}$