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

3.6 等値演算子の型の扱い

問 3.14

以下の各式について型が正しいか判定し，正しければ結果の型を予測せよ．

•

"M" = #"M"
•

"ML" = "SML"
•

fn x => (x,x) = (x,x)
•

fn (x,f) =>(f (fn x => x), f x, x = x)

解答例

•

"M" = #"M"

左辺はstring型，右辺はchar型であるから型エラーである．

•

"ML" = "SML"

   # "ML" = "SML";
   val it = false : bool

•

fn x => (x,x) = (x,x)

   # fn x => (x,x) = (x,x);
   val it = fn : [’’a .’’a  -> bool]

•

fn (x,f) =>(f (fn x => x), f x, x = x)

部分式f (fn x => x)からfは関数を引数とする関数である．したがって，部分式f xからxも関数である．すると，x = xは関数同士の比較となり，型エラーとなる．

問 3.15

整数の組を受け取り，それぞれのフィボナッチ数を計算しその組を返す関数を定義し，それにメモ関数を適用し，メモ関数が使用可能であることを確かめよ．

解答例

   # memo;
   val it = fn : [’’a,’b.(’’a  -> ’b)  -> ’’a  -> ’’a  -> ’b]
   # fun f (x,y) = (fib x, fib y);
   val f = fn : int * int  -> int * int
   # val f = memo f (30,31);
   val f = fn : int * int  -> int * int
   # f (30,31);
   val it = ( 2178309, 832040 ) : int * int
   # f (31,30);
   val it = ( 832040, 2178309 ) : int * int

を実行すると，f (30,31)は瞬時に修了することが確認できる．

問 3.16

問2.22における集合を表現する型は int -> bool のみならず，’’a -> bool に一般化でき，したがって，問2.22で作成したプログラムは，eqtypeに属する型であれば，どのような型の集合としても使用できることを確かめよ．

解答例以下にSML#での例を示す．

   # val emptySet = fn x => false;
   val emptySet = fn : [’a .’a  -> bool]
   # fun singleton n = fn x => x = n;
   val singleton = fn : [’’a .’’a  -> ’’a  -> bool]
   # fun member n S = S n;
   val member = fn : [’a .’a  -> [’b .(’a  -> ’b)  -> ’b]]
   # fun insert n S = fn x => x = n orelse S x;
   val insert = fn : [’’a .’’a  -> (’’a  -> bool)  -> ’’a  -> bool]
   # fun union S1 S2 = fn x => S1 x orelse S2 x;
   val union = fn : [’a .(’a  -> bool)  -> (’a  -> bool)  -> ’a  -> bool]
   # fun intersection S1 S2 = fn x => S1 x andalso S2 x;
   val intersection = fn : [’a .(’a  -> bool)  -> (’a  -> bool)  -> ’a  -> bool]
   # fun difference S1 S2 = fn x => S1 x andalso not (S2 x);
   val difference = fn : [’a .(’a  -> bool)  -> (’a  -> Bool.bool)  -> ’a  -> bool]
   # singleton (1,2);
   val it = fn : int * int  -> bool
   # val S = singleton (1,"1");
   val S = fn : int * string  -> bool
   # val S = insert (2,"2") S;
   val S = fn : int * string  -> bool
   # member (1,"1") S ;
   val it = true : bool
   # member (1,"2") S ;
   val it = false : bool