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

2.6 高階の関数

問 2.15

以下の関数を summation を使って定義せよ．

1.

$f(x)=1+2+\cdots+n$
2.

$f(n)=1+2^{2}+3^{2}+\cdots+n^{2}$
3.

$f(n)=1+(1+2)+(1+2+3)+\cdots+(1+2+\cdots+n)$

解答例

1.

fun f1 n = summation (fn x =>x) n;
2.

fun f2 n = summation (power 2) n;
3.

fun f3 n = summation f1 n;

問 2.16

使用しているコンパイラに応じて，以下のいずれかの問題を解け．

•

SML#コンパイラの場合：summationが整数から実数への関数 $f$ に対して， $\sum_{k=1}^{n}f(k)$ を求める関数としても使用できることを確かめよ．
•
オーバーロード多相性のサポートがないコンパイラの場合：整数から実数への関数 $f$ に対して， $\sum_{k=1}^{n}f(k)$ を求める関数
```
   summation’ : (int -> real) -> int -> real
```
を定義せよ．

解答例

•

$ smlsharp
# fun summation f n = if n = 1 then f 1 else f n + summation f (n - 1);
# val summation =
  fn : [’a::{int, word, int8, word8, ...}.  (int -> ’a) -> int -> ’a]
# summation (fn x => real x + 1.1) 10;
val it = 66.0 : real

•

   fun summation’ f n =
       if n <= 0 then 0.0
       else f n + summation’ f (n - 1);

問 2.17

$f(x)$ を実数から実数への関数とする． $f$ の $[a,b]$ の区間の定積分の値 $\int_{a}^{b}f(x)dx$ は， $n$ が十分に大きいとき，

\sum_{k=1}^{n}\left(f\left(a+{{k(b-a)}\over{n}}\right)\times\frac{b-a}{n}\right)

で近似できる． $f$ と $n$ と $a$ と $b$ を受け取り，上記の値を計算する関数 integral を定義せよ．その際， $n$ や $k$ は int 型データであるから， $b-a$ などの real 型データとの演算では，第1.2節で紹介した型変換関数 real を使用する必要がある点に注意せよ．

$\int_{0}^{1}x^{3}dx$ の近似値を， $n=1000,10000,100000$ のそれぞれに対して計算せよ．

解答例 integralの定義例：

   fun integral f n a b =
       let val unit = (b - a) / real n
       in summation’ (fn x => f(a + real x * unit) * unit) n
       end;

$n=1000,10000,100000$ に対する $\int_{0}^{1}x^{3}dx$ の近似値の計算例：

   # fun cube x = x * x * x * 1.0;
   val cube = fn : real -> real
   val it = fn : real -> real -> real
   # integral cube 1000 0.0 1.0;
   val it = 0.25050025 : real
   # integral cube 10000 0.0 1.0;
   val it = 0.2500500025 : real
   # integral cube 100000 0.0 1.0;
   val it = 0.250005000025 : real

なお、解析的な計算結果は $1/41.0^{4}=0.25$ である。

問 2.18

summation は，以下のより一般的な計算スキーマの特殊な場合と考えることができる．

{\Lambda}_{k=1}^{n}(h,f,z)=h(f(n),\cdots,h(f(1),z)\cdots)

たとえば $\sum_{k=1}^{n}f(k)=\Lambda_{k=1}^{n}(+,f,0)$ と考えられる．

1.

$\Lambda_{k=1}^{n}(h,z,f)$ を計算する高階関数 accumulate h z f n を定義せよ．
2.

summation を accumulate を使って定義せよ．
3.
accumulate を使って以下の各計算をする関数を定義せよ．
1. (a)
  
  $f_{1}(n)=1+2+\cdots+n$
2. (b)
  
  $f_{2}(n)=1\times 2\times\cdots\times n$
3. (c)
  
  $f_{3}(n,x)=1\times x^{1}+2\times x^{2}+\cdots+n\times x^{n}$

解答例 accumulateの定義例

   fun accumulate h z f n =
       if n = 0 then z
       else h(f n,accumulate h z f (n - 1));

accumulateを使ったsummation、f1、f2、f3の定義例。

1.

val summation = accumulate (op +) 0;
2.

fun f1 n = accumulate (fn (x,y) => x + y) 0 (fn x => x) n;
3.

fun f2 n = accumulate (fn (x,y) => x * y) 1 (fn x => x) n;
4.

fun f3 (n,x) = accumulate (fn (x,y) => x + y) 0 (fn n => n * power n x) n;

問 2.19

以前定義した関数 power と Power の違いは引数の渡し方のみであるから，power と Power のような関数同士は相互に変換可能なはずである．このような引数の受け渡し方の変換に関して以下の設問に答えよ．

1.

power を Power を使って定義し直せ．また逆に，Power を power を使って定義し直せ．
2.

$\tau_{1}$ * $\tau_{2}$ -> $\tau_{3}$ の型の関数を $\tau_{1}$ -> $\tau_{2}$ -> $\tau_{3}$ の型の関数に変換する高階の関数 curryおよびその逆変換関数 uncurry を定義せよ．ただし，任意の $f, x, y$ について $($ もし型が正しければ $)$ 常に

curry $f$ $x$ $y$ $=$ $f$ ( $x$ , $y$ )

uncurry $f$ ( $x$ , $y$ ) $=$ $f$ $x$ $y$

が成り立つものとする．
3.

curry と uncurry を使って Power と power の変換を行い，正しく動作することを確かめよ．

解答例

•
Powerとpowerがすでに定義されていると仮定する．この下で，以下のように定義できる．
```
   val Power = fn (m,n) => power m n
   and power = fn m => fn n => Power(m,n)
```

•

uncurryとcurryの定義例

   fun uncurry f x y = f (x,y)
   fun curry f (x,y) = f x y

•

SML#での実行結果を以下に示す．

   # fun Power(m,n) = if m = 0 then 1
   >                  else n * Power(m - 1,n);
   val Power = fn : int * int  -> int
   # fun power m n = if m = 0 then 1
   >                  else n * power (m - 1) n;
   val power = fn : int  -> int  -> int
   # fun curry f x y = f(x,y);
   val curry = fn : [’a,’b,’c.(’a * ’b  -> ’c)  -> ’a  -> ’b  -> ’c]
   # fun uncurry f (x,y) = f x y;
   val uncurry = fn : [’a,’b,’c.(’a  -> ’b  -> ’c)  -> ’a * ’b  -> ’c]
   # val Power = uncurry power
   > and power = curry Power;
   val Power = fn : int * int  -> int
   val power = fn : int  -> int  -> int
   # Power (2,3) ;
   val it = 9 : int
   # power 2 3;
   val it = 9 : int

問 2.20

問2.14で定義した fastMatrixPower の構造を一般化し， $0$ 以上の整数 $n$ ， 2項演算関数 $f$ ， $f$ に関する単位元 $e$ ，および値 $v$ を受け取り， $f$ を乗算演算とする $v$ の $n$ 乗を高速に計算する高階の関数 fastPower を定義せよ．ただし， $v^{0}=e$ とし， $n\not=0$ の場合，以下のような演算を行うものとする．

{\tt fastPower}(n,f,v,e)=\underbrace{f(v,f(v,\cdots,f}_{\mbox{$n$回の$f$の適用}}(v,% e)\cdots))

fastPower を用いて，fastMatrixPower を定義し直せ．

解答例

   fun matrixMult (a,b,c,d) (x,y,z,w) = (a*x+b*z,a*y+b*w,c*x+d*z,c*y+d*w)
   fun fastPower (n,f,v,e) =
        if n = 0 then e
        else let val m = n div 2
                 val k = n mod 2
             in if m = 0 then v
                else let val v1 = fastPower(m,f,v,e)
                          val v2 = f (v1,v1)
                      in if k = 0 then v2
                          else f(v,v2)
                      end
             end;
   fun fastMatrixPower(n,a,b,c,d) =
       fastPower(n, fn (x,y) => matrixMult x y, (a,b,c,d), (1,0,0,1));