再帰的データ構造としてのconsセル
「すべてリストである」で見たように、consセルは再帰的なデータ構造になっています。carとcdrを再帰的に適用することでどんな構造のconsセルでも処理することができます。
(define (odd-sigma ls)
(cond ((not (pair? ls)) ;; リストが空か?
0) ;; 0を返す
((odd? (car ls)) ;; 先頭要素が奇数か?
(+ (car ls) (odd-sigma (cdr ls)))) ;; 先頭要素と残りの奇数要素の総和
(else ;; 先頭要素が偶数
(odd-sigma (cdr ls))))) ;; 残りの奇数要素の総和
リスト要素が奇数のものだけの総和を計算するodd-sigma手続きは、carとcdrを再帰的に適用することで上記のように書けました。ただしodd-sigmaはちょっと不恰好です。もっとエレガントに書けないでしょうか?
Gaucheで外部ライブラリを使う
Gaucheにはモジュールと呼ばれる外部ライブラリを利用する機能があります。
(use モジュール名)
use式を書くことでモジュールを利用することができます。Gaucheでは数多くのモジュールが提供されています。ここではリスト処理に便利なsrfi-1モジュールを使うことにします。
gosh> (use srfi-1)
これでsrfi-1モジュールが使用できるようになりました。
再帰が見えなくなる
odd-sigma手続きをエレガントに書き直すために、srfi-1モジュールに含まれるfilter手続きを導入してみましょう。
(filter 判定式 リスト)
filter手続きは、リスト中の要素を判定式で判定し、真の要素だけのリストを返します。
奇数の要素だけのリストを得るには、
gosh> (filter odd? (list 0 1 2 3 4 5))
(1 3 5)
odd?手続きで奇数かどうか判定させれば良いのです。
filterを使ってodd-sigmaを書き直してみましょう。
gosh> (define (odd-sigma ls)
(apply + (filter odd? ls)))
odd-sigma
gosh> (odd-sigma (list 0 1 2 3 4 5))
9
+手続きがリストに対してそのまま適用できないことに注意してください。
gosh> (+ (list 1 3 5))
*** ERROR: number required, but got (1 3 5)
Stack Trace:
_______________________________________
+手続きをリストに適用するにはapplyを使います。
gosh> (apply + (list 1 3 5))
9
filterを導入することで、odd-sigma手続きは一見再帰を使っていないかのように見えるようになりました。では本当に再帰が使われていないのでしょうか?
「計算機プログラムの構造と解釈第二版」ではfilter手続きは次の通りに書かれています。
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
filter手続きはリストに対してcar、cdrを再帰的に適用し、自分自身を呼び出している再帰的手続きです。
filter手続きを導入したことで、実際には再帰を使っているにもかかわらず、まるで再帰していないかのように書くことができました。
上記のfilter手続きが、再帰を素直に使ったodd-sigma手続きに似ていることに気づいたかも知れません。
(define (odd-sigma ls)
(cond ((not (pair? ls)) ;; リストが空か?
0) ;; 0を返す
((odd? (car ls)) ;; 先頭要素が奇数か?
(+ (car ls) (odd-sigma (cdr ls)))) ;; 先頭要素と残りの奇数要素の総和
(else ;; 先頭要素が偶数
(odd-sigma (cdr ls))))) ;; 残りの奇数要素の総和
filter手続きはodd-sigma手続きのうち、任意の判定式を与えて要素を取り出す部分を一般化したものとも考えられます。
現実的なプログラミングでは再帰を明示的に書くことはむしろ稀です。filter手続きを始めとする高階手続きを使うことで、あたかも再帰を使っていないかのように書くのが普通です。
高階手続きとは手続きを引数にとる手続きのことです。filterと並んで多く使われる高階手続きとしてmap、foldがあげられます。
by えんどうやすゆき
