区間 [a,b] の関数 f の積を計算する高階関数 product を sumにならって定 義せよ。 さらに、product を使って階乗を求める関数 factorial を定義し直せ。
> (define (product term next a b)
(if (> a b)
1
(* (term a)
(product term next (next a) b))))
> (define (factorial n)
(product identity inc 1 n))
> (factorial 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
関数 sum と product は、a から b までの関数 f の値を加算や乗算で集める という点で共通している。そこで、これらを抽象化した高階関数 accumulate を定義せよ。この関数は (accumulate combiner null-value term next a b) のように5引数の関数であり、combinerが数の集め方(加算や乗算)、 null-value が範囲外に来たときの値(加算だったら 0、乗算だったら 1)であ るとする。 さらに、sum, productを accumulateを使って定義し直せ。
> (define (accumulate combiner null-value term next a b)
(if (> a b)
null-value
(combiner (term a)
(accumulate combiner null-value term next
(next a) b))))
;; sum と product の再定義
> (define (sum term next a b)
(accumulate + 0 term next a b))
> (define (product term next a b)
(accumulate * 1 term next a b))
;; 確認
> (sum identity inc 1 10)
55
> (product identity inc 1 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
>
次のような関数 foo があったとき、(foo 1) の値はいくつになるか。また、
その理由を説明せよ。
(define (foo a)
(let ((a (+ a a))
(b (+ a a)))
(+ a b)))
まず let を lambda を使った形式に書き直すと、 (define (foo a) ((lambda (a b) (+ a b)) (+ a a) (+ a a))) のようになる。その上で、(foo 1)を評価する(適用的順序とする)。 1. (foo 1) 2. ((lambda (a b) (+ a b)) (+ 1 1) (+ 1 1))) (aを1で置換) 3. ((lambda (a b) (+ a b)) 2 2 )) 4. (+ 2 2) (a,bを2で置換) 5. 4 このような結果となる。1→2の際に、lambda式の本体の式(+ a b)の中のaは置 換されない。これは、let式で言うと、letの本体部分のaに相当している。
Pascal の procedure, function は一級データか? また、C の関数ポインタは一級データか? もしそうなら、Scheme の関数との 違いはあるか?
Pascalのprocedure, functionは、名前を付けることができるが、関数の引数
として渡す・関数の返り値として受け取る・データ構造の中に入れる、ことは
いずれもできない。よって一級データではない。
一方、Cの関数ポインタは、名前を付ける・関数の引数として渡す・関数の返
り値として受け取る・データ構造の中に入れる、といった操作は全て可能であ
る。よってこれは一級データである。
Schemeの関数との違いは、Schemeでは関数の内部に関数を定義できるのに対し
て、Cではそれができないことである。例えば、
> (define (adder x)
(lambda (y) (+ x y)))
> (define add-10 (adder 10))
> (add-10 3)
13
のような関数はCでは定義できない。
(gccではできるようだが、これは独自の拡張である。)
関数を引数として受け取り、「その関数を2回適用するような関数」を返す関 数double を定義せよ。つまり ((dobule f) x) が (f (f x))となる。 そのときの (((double (double double)) inc) 5) の値は何か?
> (define (double f)
(lambda (x)
(f (f x))))
> (((double (double double)) inc) 5)
21
与式を、以下のように置き換えてゆく。(下線部が置き換える部分である。)
この置き換えは正規順序でも適用的順序でもない。
1. (((double (double double)) inc) 5)
~~~~~~~~~~~~~~~~~~~~~~~~
2. (((lambda (x) ((double double) ((double double) x))) inc) 5)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3. (((double double) ((double double) inc)) 5)
~~~~~~~~~~~~~~~
4. (((double double) ((lambda (x) (double (double x))) inc)) 5)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
5. (((double double) (double (double inc))) 5)
~~~~~~~~~~~~~~~
6. (((lambda (x) (double (double x))) (double (double inc))) 5)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
7. ((double (double (double (double inc)))) 5)
doubleは、「2回適用する関数を作る」関数なので、incを2×2×2×2=16回適
用する関数を作ることになる。結局、それに5を適用すると21を得る。
二つの関数 f,g を合成するような関数 compose を定義せよ。つまり、 (compose f g)が(f (g x))となるようなものである。 そのときの((compose square inc) 6)の値は何か?
> (define (compose f g)
(lambda (x) (f (g x))))
> ((compose square inc) 6)
49
>
これは、
1. ((compose square inc) 6)
2. ((lambda (x) (square (inc x))) 6)
3. (square (inc 6))
4. (square 7)
5. 49
のようにして得られる。
関数 f と自然数 n を受け取り、「f を n 回適用するような関数」を返す関 数 repeatを定義せよ。 (頭の体操)関数 repeat, inc だけを使って和、積、冪乗を計算する関数をそ れぞれ定義せよ。
n=0の場合は、「fを0回適用する関数」なので恒等関数(identity)になる。
n>0の場合、fと「fをn-1回適用する関数」を合成すればよい。
> (define (repeat f n)
(if (= n 0)
identity
(compose f (repeat f (- n 1)))))
> ((repeat inc 10) 0)
10
;; 和: x+y は inc を x 回合成したものに y を適用
> (define (add x y) ((repeat inc x) y))
> (add 3 4)
7
;; 積: x*y は 「x加える」関数を y 回合成
> (define (mul x y) ((repeat (repeat inc x) y) 0))
> (mul 3 4)
12
;; 冪乗: 「x乗じる」関数を y 回合成
> (define (power x y)
((repeat (lambda (n) (mul n x)) y) 1))
> (power 2 8)
256
>