Syntax highlighter

(はじめよう Scheme 4)

繰り返し


ある処理をn回繰り返す、例えば1からnまでの数字を足すということを考えてみる。Schemeにはいくつかの方法が用意されているが、ここでは名前付letdoで行ってみる。

まずは名前付let
(define n 10)

(let loop ((i 1) (r 0))
  (if (> i n) 
      r 
     (loop (+ i 1) (+ r i))))
名前付letlet二つ目に名前(シンボル)を取る。上記はカウンタ変数inより大きくなったら足し算の結果rを返し、そうでないのであればloopを二つの変数irを更新して続行する*1loopletで定義された変数と同じだけの引数を受け取る必要がある。

次にdo
(define n 10)

(do ((i 1 (+ i 1)) (r 0 (+ r i)))
    ((> i n) r))
doは以下の定義をとる;
(do ((<variable> <init> <step>))
    ((<test>) <expression> ...) 
  <command> ...)
一つ目の括弧では、変数名(<variable>)、その初期値(<init>)及びその変数を次の繰り返し開始時にどう更新するか(<step>)をそれぞれ定義する。
二つ目の括弧では、終了条件(<test>)及びdo式が返す値(<expression> ...)を定義する。
最後の<command> ...は繰り返し処理で何をするかを定義する。今回のような単純な処理であれば名前付letと同様特に記述する必要はないが、例えば計算の途中結果を見たい場合などに以下のように書くことができる。
(do ((i 1 (+ i 1)) (r 0 (+ r i)))
    ((> i n) r)
 (display r) (newline))
#|
0
1
3
6
10
15
21
28
36
45
55
|#

設問 4.1
nの階乗を計算する手続きfactを作成せよ

高階関数

高階関数とは手続きを引数に取ったり戻り値として返したりする手続きである。高階関数を使うとパターンの切り出しが容易になる。例えば上記の1からnまでの足し算を行う手続きsumを書いてみよう。普通に書けば以下のように書けるだろう。
(define (sum n)
  (let loop ((i 1) (r 0))
    (if (> i n)
        r
        (loop (+ i 1) (+ r i)))))
この手続きには1からnまで繰り返すというパターンが含まれている。そこで、実際に足し算を行う処理と繰り返しのパターンを分けてみよう。
(define (iterate-n n proc)
  ;; 手続きprocに0回目(初期値)を与える
  (let loop ((i 1) (r (proc 0 0)))
    (if (> i n)
        r
        (loop (+ i 1) (proc i r)))))

(define (sum n)
  (iterate-n n (lambda (n r) (+ n r))))
iterate-nは与えられたn回数procを繰り返すだけで、実際の処理はprocに依存している。

高階関数を使えば、あるパターンのみを行う手続きと実際の処理を行う手続きを分けて記述することができコードの再利用が容易になるというメリットがある。

設問 4.2
iterate-nを用いてnの階乗を計算する手続きfact2を作成せよ。

*1:本当の意味は多少違うが、ここでは便宜上こう書いておく。

No comments:

Post a Comment