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

2.7 関数式

問 2.21

以上の2つの f の定義のそれぞれについて，上記の g を含むプログラムの評価を行い，実行時間を比較せよ．

解答例省略。

問 2.22

int -> bool 型の関数は，与えられた整数が条件を満たすか否かを判定する関数であるが，見方を変えれば，条件を満たす整数の集合の表現とみなすことができる．たとえば fn x => x = 1 orelse x = 2 orelse x = 3 は集合 $\{1,2,3\}$ の表現と考えることができる．ここで $exp_{1}$ orelse $exp_{2}$ は， $exp_{1}$ と $exp_{2}$ の論理和（ $exp_{1}$ または $exp_{2}$ ）を表す構文である． $exp_{1}$ と $exp_{2}$ の論理積（ $exp_{1}$ かつ $exp_{2}$ ）を表す構文は $exp_{1}$ andalso $exp_{2}$ である．

この見方に従い，以下の定義を与えよ．

1.

空集合を表す関数 emptySet．
2.

整数 $n$ を受け取り，単位集合 $\{n\}$ を生成する関数 singleton．
3.

集合 $S$ に要素 $n$ を加える関数 insert．
4.

要素 $n$ が集合 $S$ に含まれるか判定する関数 member．
5.

2つの集合の和集合，積集合，差集合を計算する関数 union， intersection， difference．

解答例

   val emptySet = fn x => false
   fun singleton n = fn x => x = n
   fun insert n S = fn x => x = n orelse S x
   fun member n S = S n
   fun union S1 S2 = fn x => S1 x orelse S2 x
   fun intersection S1 S2 = fn x => S1 x andalso S2 x
   fun difference S1 S2 = fn x => S1 x andalso not (S2 x)