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

3.5 多相型の使用の制限

問 3.12

fn f => twice twice f が関数を引数に $4$ 回適用する高階の関数であることを確かめよ． fn f => twice fourTimes f および fn f => fourTimes twice f はそれぞれどのような関数か．

解答例例えば以下のように確かめることができる．

   # fun printStar () = print "*";
   val printStar = fn : unit  -> unit
   # twice twice printStar ();
   ****val it = () : unit

以下の例からわかるように、fn f => twice fourTimes f および fn f => fourTimes twice fは、どちらも関数を16回適用する高階関数である．

   # twice fourTimes printStar ();
   ****************val it = () : unit
   # fourTimes twice printStar ();
   ****************val it = () : unit

（補足） twice fourTimes f xは，その定義から， fourTimes (fourTimes f) x である．さらにfourTimesの定義にしたがって展開すると (fourTimes f) ((fourTimes f) ((fourTimes f) (fourTimes f x))) となる．このことから，twice fourTimes f xはfをxに $4^{2}$ 回適用する関数となることがわかる．一般に，関数を $m$ 回適用する関数を $M$ ，関数を $n$ 回適用する関数を $N$ とするとM Nは関数を $n^{m}$ 回適用する関数となる．以下に $m=4，n=3$ の例を示す．

   # fun threeTimes f x = f (f (f x));
   val threeTimes = fn : [’a .(’a  -> ’a)  -> ’a  -> ’a]
   # fourTimes threeTimes printStar ();
   *********************************************************************************val it = () : unit

問 3.13

以下の各式が値式であるか否か判定せよ．

1.

fn x => x 1
2.

(fn x => x) 1
3.

(fn x => x,fn x => x)
4.

let fun f x = x in f end
5.

let val a = 1 + 1 in fn x => x end

解答例以下のものがは値式である．

•

fn x => x 1
•

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

（補足）以下の各式は値式ではない．

•

let fun f x = x in f end
•

let val a = 1 + 1 in fn x => x end

しかし，ランク１多相性を実現しているSML#では以下のように多相型が与えられる．

   # let fun f x = x in f end;
   val it = fn : [’a .’a  -> ’a]
   # let val a = 1 + 1 in fn x => x end;
   val it = fn : [’a .’a  -> ’a]