再帰呼び出しを作るためには、関数の仕様をよく理解することが肝心である。
前回の練習問題の解答例を見ながら、コツを示す。
仕様：数値のリストを入力し、その中の数値の合計を返す関数 (sum 〈数値のリスト〉)
リストの２番目以降の要素から成るリストの合計値に、１番目の要素の値を加えると、全体の合計値となる。つまり、(sum (cdr 〈リスト〉)) と (car 〈リスト〉)の和が、〈リスト〉の合計値である。
ここで、(sum (cdr 〈リスト〉)) の返り値に操作をして返り値を作るので、以下のようなプログラムになり、再帰的プロセスを持つ再帰関数となる：
(define sum
(lambda (lst)
(if (null? lst)
0
(+ (car lst) (sum (cdr lst))))))
|
sum で最後に実行する部分（下線部）に注目して、プログラムの動作をトレース（追跡）しよう。
(sum (list 1 2 3 4 5)) ... 最初の呼び出し (+ 1 (sum (list 2 3 4 5))) ... sum の部分を評価して下記の通りに展開 (+ 1 (+ 2 (sum (list 3 4 5)))) (+ 1 (+ 2 (+ 3 (sum (list 4 5))))) (+ 1 (+ 2 (+ 3 (+ 4 (sum (list 5)))))) (+ 1 (+ 2 (+ 3 (+ 4 (+ 5 (sum (list ))))))) ... (null? lst) が成立 (+ 1 (+ 2 (+ 3 (+ 4 (+ 5 0))))) (+ 1 (+ 2 (+ 3 (+ 4 5)))) (+ 1 (+ 2 (+ 3 9))) (+ 1 (+ 2 12)) (+ 1 14) 15 |
では、反復的プロセスを持つ再帰関数を作るために、関数の仕様を少し変えてみよう。
仕様：数値のリスト、および、合計値計算の途中の結果を入力し、リストの数値の合計を返す関数 (sum2 〈数値のリスト〉 〈途中の合計値〉)
リスト全体に対しての計算をするのだが、その途中の状態を考えてみよう。すなわち、リストの先頭から合計値を求めているとして、その途中では、「既に計算した部分」と「未だ計算していない部分」がある。未計算の部分を lst1 としよう。計算済み部分の合計値を s としよう。
では、未計算のところを１段階進めるとすると、lst1 の先頭要素と s の和、および、lst1 の２番目以降のリストを使って計算の続きをすればよい。
たとえば、次のように計算すればよい。リスト全体が (list 1 2 3 4 5) とする。(list 1 2 3) までが計算済みとすると (sum2 (list 4 5) 6) を計算すればリスト全体の合計値が得られる。ここで、１段階進めると、(sum2 (list 5) 10) を計算することになる。
問によると、１引数の関数を作ることが要求されているので、sum2 を呼び出す関数 sum を作る。
以上により、下記のプログラムが作られる。
(define sum
(lambda (lst)
(define sum2
(lambda (lst1 s)
(if (null? lst1)
s
(sum2 (cdr lst1) (+ s (car lst1))))))
(sum2 lst 0)))
|
sum2 で最後に実行する部分（下線部）に注目して、トレースしよう。
(sum2 (list 1 2 3 4 5) 0) ... 最初の評価が、(sum2 lst 0) だから。 (sum2 (list 2 3 4 5) 1) (sum2 (list 3 4 5) 3) (sum2 (list 4 5) 6) (sum2 (list 5) 10) (sum2 (list ) 15) ... この呼出しに対して (null? lst1) が成立 15 ... tail recursion なので、実際のところすぐに結果が返される。 |
仕様：数値のリストを入力し、その中の偶数値だけのリストを作って返す関数 (even 〈数値のリスト〉)
ポイント：リストの先頭要素が偶数のときは、その要素の後に、リストの２番目以降の要素から成るリストから抽出した偶数値だけのリストを置く。すなわち、(car 〈リスト〉) の後に (even (cdr 〈リスト〉)) により得られるリストを置く。もっといえば、(cons (car 〈リスト〉) (even (cdr 〈リスト〉))) とする。一方、リストの先頭要素が偶数でないときは、その要素は捨てて、リストの２番目以降の要素から成るリストから抽出した偶数値だけのリストを返す。
(define even
(lambda (lst)
(if (null? lst)
()
(if (even? (car lst))
(cons (car lst) (even (cdr lst)))
(even (cdr lst))))))
|
このプログラムをトレースしてみよう。
(even (list 1 2 3 4 5 6)) (even (list 2 3 4 5 6)) (cons 2 (even (list 3 4 5 6))) (cons 2 (even (list 4 5 6)) (cons 2 (cons 4 (even (list 5 6)))) (cons 2 (cons 4 (even (list 6)))) (cons 2 (cons 4 (cons 6 (even (list ))))) (cons 2 (cons 4 (cons 6 ()))) (list 2 4 6) |
反復的プロセスを持つ再帰関数として作ろうとするとき、たとえば、以下のプログラムが思いつくかもしれない。
(define even
(lambda (lst)
(define even2
(lambda (lst1 lst2)
(if (null? lst1)
lst2
(if (even? (car lst1))
(even2 (cdr lst1) (cons (car lst1) lst2)) ... ※1
(even2 (cdr lst1) lst2)))))
(even2 lst ())))
|
このプログラムをトレースしてみよう。
(even2 (list 1 2 3 4 5 6) ()) (even2 (list 2 3 4 5 6) ()) (even2 (list 3 4 5 6) (list 2)) ... (cons 2 ()) より (list 2) を得る (even2 (list 4 5 6) (list 2)) (even2 (list 5 6) (list 4 2)) ... (cons 4 (list 2)) より (list 4 2) を得る (even2 (list 6) (list 4 2)) (even2 (list ) (list 6 4 2)) ... (cons 6 (list 4 2)) より (list 6 4 2) を得る (list 6 4 2) |
期待する結果が得られただろうか？ ポイントは、※1の行である。新しく見つけた偶数値(car lst1) の後に、以前に見つけた偶数値のリスト lst2 を置くようになっている。そのため、得られる偶数値のリストは、見つけた順の逆順になる。
ちなみに、even? の結果に依らず ※1 のような処理をすると、リストの要素の出現順序が入れ換わる。my-reverse のヒントにしよう。
情報工学演習３では、反復的プロセスを持つ再帰呼出しにこだわってはいない。再帰的プロセスを持つ再帰呼出しのプログラムが作成できれば十分である。以下にリストの要素に対する処理を実施する関数の雛型を示す：
(define 名前
(lambda (lst)
(if (null? lst)
〈空のときの処理〉
〈先頭要素の処理〉 と〈２番目以降の要素の処理の結果〉を統合)))
|
高階関数とは、関数を扱う関数である。関数を引数として受けとる関数や、関数を返り値とする関数のことである。高階関数の処理内容は、ある部分は性質が見えるが、ある部分は実行時にどのような関数を扱うか判明するまで見えてこない。
実は、上記の「要点」にまとめたことは、高階関数としてある程度は定義することができる。
下記の関数は、上記の「要点」に対して、「リストが空のときは空を返す」、「リストの先頭の要素は、関数 func で処理する」、「その処理結果は、残りのリストの処理結果のリストの先頭に置くこととして、全体では処理結果のリストを返す」という考えで作ったものである。
(define collect
(lambda (lst func)
(if (null? lst)
()
(cons (func (car lst)) (collect (cdr lst) func)))))
|
たとえば、リストの各要素の値を３倍にする関数は次のように実現できる。
> (collect (list 1 2 3 4 5) (lambda (x) (* x 3))) |
このラムダ式の部分では、リストのことは忘れ、１つの要素に対する処理だけを考えて、プログラムを作ることができる。
返り値にラムダ式を設置することで、関数を返す関数を作ることができる。例題を見ながら理解しよう。
面積の計算式を返す関数 menseki1
(define menseki1
(lambda (fig)
(cond ((equal? fig 'maru) (lambda (r) (* r r 3.14)))
((equal? fig 'sankaku) (lambda (w h) (* w h 0.5)))
((equal? fig 'chouhoukei) (lambda (w h) (* w h))))))
|
実行例：
> (menseki1 'maru) #<procedure:3:30> ← 返り値は関数である。ラムダ式の内部表現。 > ((menseki1 'maru) 2) 12.56 ← 関数の返り値に、2 を与えて処理してもらった結果 |
((menseki2 'sankaku) (list 4 5)) ⇒ 10.0(2) (1) の続きで、図形名とサイズをまとめたリストを、さらに、１個以上まとめてリストにしたとき、各図形の面積をリストで返す関数 keisan を作成せよ。ただし、keisan 関数は、上記の collect を使うこととして、再帰呼び出しであってはいけない。そして、面積計算の関数は、menseki2 を使って得られることにする。たとえば、次の実行ができるようにする。
(keisan menseki2 (list (list 'maru 2) (list 'sankaku 3 4) (list 'chouhoukei 5 6))) ⇒ (list 12.56 6.0 30)
小レポートには、関数 collect、関数 menseki2、関数 keisan のプログラムを印刷し、各行にコメントを手書きすること。