日: 2014年2月6日

これも東大の Scheme演習のページから。

　cf. Scheme演習 第３回

の問2。

(map proc list)

リストlistの要素一つ一つに対して一引数関数procを適用し、結果をリストにして返す関数。
実行例

> (map (lambda (x) (+ x 1)) (list 1 2 3 4))
(2 3 4 5)

(define map
  (lambda (proc lis)
    (if (null? lis)
        (quote ())
        (cons (proc (car lis)) (map proc (cdr lis))))))

(print (map (lambda (x) (+ x 1)) (list 1 2 3 4)))

^o^ > gosh map.scm
(2 3 4 5)

(add-squares list)

数のリストlistの要素の平方の和を返す関数。
実行例

> (add-squares (list 1 10 100))
10101

(define add-squares
  (lambda (lis)
    (if (null? lis)
        0
        (+ (* (car lis) (car lis)) (add-squares (cdr lis))))))

(print (add-squares (list 1 10 100)))

cond じゃなくて if を使ってみた。

^o^ > gosh add-squares.scm
10101

(reverse list)

リストlistを逆順にしたリストを返す関数。
実行例

> (reverse (list 1 2 3 4))
(4 3 2 1)

(define reverse
  (lambda (lis)
    (define rev
      (lambda (l1 l2)
        (if (null? l1)
            l2
            (rev (cdr l1) (cons (car l1) l2)))))
    (rev lis (quote ()))))

(print (reverse (list 1 2 3 4)))

^o^ > gosh reverse.scm
(4 3 2 1)

(assq obj alist)

ペアやリストを直接の要素とするリスト（連想リストという）alistを受け取り、その要素のうちcar部がobjと等しいような最左のものを返す関数
（ここで等しいとは、eq?による比較）
見つからない場合は#fを返す。

> (define dic '((ami net) (ame rain) (ame candy)))
> (assq 'ame dic)
(ame rain)
> (assq 'amedama dic)
#f

(define assq
  (lambda (obj alist)
    (cond
      ((null? alist) #f)
      ((eq? (car (car alist)) obj) (car alist))
      (else (assq obj (cdr alist))))))

(define dic '((ami net) (ame rain) (ame candy)))

(print (assq 'ame dic))
(print (assq 'amedama dic))

^o^ > gosh assq.scm
(ame rain)
#f

「Scheme手習い」10章に入る前に、少し離れて東大のScheme演習から。

　cf. Scheme演習 第２回

問2（if文）

次のような新しい if 文を関数として定義した。

(define (new-if test then-exp else-exp)
  (cond (test then-exp)
        (else else-exp)))

例えば、(new-if (= 1 2) (+ 3 4) (+ 5 6)) などとすれば、正しく 11 を返す。（確かめてみよ。）

これを使って、fac4 を次のように定義した。

(define (fac4 n)
  (new-if (= n 0)
          1
          (* n (fac4 (- n 1)))))

これを使って (fac4 3) としたら、無限ループにおちいってしまった。（確かめてみよ。）これはなぜか。

まずは前半がちゃんと動くのかを確かめてみよう。

gosh> (define (new-if test then-exp else-exp)
  (cond (test then-exp)
        (else else-exp)))
new-if
gosh> (new-if (= 1 2) (+ 3 4) (+ 5 6))
11

うん、動いてるね。
つぎは後半だ。本当に無限ループに陥るのか確かめてみよう。

gosh> (define (fac4 n)
  (new-if (= n 0)
          1
          (* n (fac4 (- n 1)))))
fac4
gosh> (fac4 3)
out of memory (32).  aborting...

うーん、無限ループなのかどうかはよくわからないけど、時間がかかった上にメモリが足りなくなって Gauche ごと落ちてしまった。とにかく、期待どおりに動かないのは確かなようだ。

で、なぜかといえば、if文が特殊形式（東大のScheme演習のページではシンタックス形式、Gauceh のユーザマニュアルでは Special Form と呼んでいる）なのにたいして、new-if は単なる関数適用だ。Scheme は正格評価なので、(new-if ...) の値を決める前に、その引数である (= n 0)、1、(* n (fac4 (- n 1))) のすべてを評価する。言い換えると (fac4 3) を評価する前に (fac4 2) を評価する必要があるわけだ。同様に、(fac4 2) の前に (fac4 1) を、(fac4 1) の前に (fac4 0)を、さらに (fac4 0) の前には (fac4 -1) を･･････といった具合で永遠に続くことになる。これが無限ループの正体だ。

問3（関数を返す関数）

関数 f(x) の導関数 f'(x) は、小さい数 dx を使って近似的に下のように表せる。

[math]f'(x)=\frac{f(x+dx)-f(x)}{dx}[/math]

1 引数関数 f と小さい数 dx を受けとったら、その導関数を返すような関数 deriv を作れ。すなわち、((deriv f dx) n) のように実行すると、結果として f'(n) の値を返す。

> (define (f1 x) (* x x))
> ((deriv f1 0.001) 5)
10.001000000002591

これは簡単。

(define deriv
  (lambda (f dx)
    (lambda (x)
      (/ (- (f (+ x dx)) (f x)) dx))))

(define f1
  (lambda (x) (* x x)))

(print ((deriv f1 0.001) 5))

^o^ > gosh deriv.scm
10.001000000002591

OK。つぎ、問3の後半部分。

Newton 法を使って、1 引数の関数 f が与えられた時にf(x) = 0 の実数解を１つ求めるプログラムを作れ。精度は、f(x) と 0 の差の絶対値が 0.001 以下とする。

• 用いる dx は0.001とする。
• 実際に、f(x) = x2 – 4 やその他の関数に対して適用してみよ。

これにはヒントが与えられている。

おさらいとヒント

一般の関数に対する Newton 法は、関数 f(x) とその導関数 f'(x) が与えられたとき、その零点の近似値を次の式で更新していく。

[math]a_{n+1}=a_n-\frac{f(a_n)}{f'(a_n)}[/math]

従って、f(an) と 0 との誤差が 0.001 以下になるまで、順に an を求めていく補助再帰関数を定義し、適当な初期値をその補助関数に与えてやればよい。

これでどうだ。

(define deriv
  (lambda (f dx)
    (lambda (x)
      (/ (- (f (+ x dx)) (f x)) dx))))

(define newton
  (lambda (f init)
    (if (< (abs (- (f init) 0)) 0.001)
        init
        (newton f (- init (/ (f init) ((deriv f 0.001) init)))))))

(define f
  (lambda (x)
    (- (* x x) 4)))

(print (newton f 1.0))

^o^ > gosh newton.scm
2.0000002513546535

まあ、うまくいってるかな。