7.6 無限なデータ構造の定義と利用

問 7.13

FILTER を使い naturalNumbers から偶数の無限リスト evenNumbers を定義しテストを行え．

   # NTH 10000000  evenNumbers;
   val it = 20000000 : int

となるはずである．

解答例定義とテストのSML#セッションを以下に示す。

   # val evenNumbers = FILTER (fn x => x mod 2 = 0) naturalNumbers;
   val evenNumbers = CONS (0, fn) : int inflist
   # NTH 10000000  evenNumbers;
   val it = 20000000 : int

問 7.14

無限リストに対する以下の関数を定義せよ．

•

最初の $n$ 個の要素を除いたリストを返す関数
DROP : int -> ’a inflist -> ’a inflist
•

最初の $n$ 個の要素を通常のリストにして返す関数
TAKE : int -> ’a inflist -> ’a list
•

$n$ 番目の要素から始まる $m$ 個の要素を通常のリストにして返す関数
VIEW : int * int -> ’a inflist -> ’a list

解答例定義例を以下に示す。

   fun DROP 0 L = L
     | DROP n L = DROP (n - 1) (TL L);
   fun TAKE 0 L = nil
     | TAKE n L = HD(L) :: TAKE (n - 1) (TL L);
   fun VIEW (n,m) L = TAKE m (DROP n L);

問 7.15

’a inflist inflist 型のデータは，2次元の無限配列とみなすことができる．このデータに関する以下のプログラムを作成せよ．

1.

外側のリストの $n$ 番目を $x$ 座標，内側のリストの $m$ 番目を $y$ 座標とする点 $(x,y)$ を求める関数 point を定義せよ．
2.

int * int -> ’a 型の関数 $f$ が与えられたとき， $f$ のグラフを表す’a inflist inflist 型のデータを返す関数 graph を定義せよ．たとえば以下のような動作をする．
- fun f (x,y) = x + y; val f = fn : int * int -> int - point (10,15) (graph f); val it = 25 : int
3.

2次元空間に配置された無限列は，図enum.pdf に示す順に座標をたどることによって通し番号を付けることができる． ’a inflist inflist 型のデータを，この通し番号に従い並べて得られる無限リストを求める関数 enumerate を定義せよ．

解答例以下に各関数の定義例を示す。

   fun point(x,y) L = NTH y (NTH x L);
   fun graph f  =
       let fun fromx x =
               let fun fromy y  = CONS(f(x,y),fn () => fromy (y + 1))
               in CONS(fromy 0,fn () => fromx (x + 1))
               end
       in fromx 0
       end
   fun enumerate G =
       let fun next (0,a) = (a+1,0)
             | next (a,b) = (a - 1, b + 1)
           fun from a = CONS(point a G, fn () => from (next a))
       in from (0,0)
       end