ここで解説する関数は以下の4つのカテゴリの７つのアイテムです。
引数xsはリストを、fは関数を表します。
＜再帰の利用とlet式による局所変数定義＞
- (a) ( list−ref n xs ) リストのn番目の要素を返す関数
- (b) ( fold f z xs ) リストの要素を後ろから順に関数fでz倍する関数
＜他の関数の利用＞
- (c) ( min xs ) リストの中で一番小さな要素を返す関数
＜リストを返す関数＞
- (d) ( reverse xs ) リスト内の要素を後ろから順に並べ替える関数
- (d) ( reverse xs ) リスト内の重複する要素を削除する関数
＜複雑な処理をする関数＞
- (f) ( gen f x n ) 関数fをxに対してn回繰り返す関数
- (g) ( quicksort xs ) リスト内の要素を小さい順に並べ替える関数
＜再帰の利用とlet式による局所変数定義＞
関数を定義するには、多くの場合、再帰的な記述が必要となります。
また、関数内部だけで使用する変数をlet式によって定義することで、すっきりした簡潔な記述ができます。
ここでは、再帰の利用およびlet式の典型的な使い方を解説します。
(a) ( list−ref n xs )
リストのn番目の要素を返す関数です。
( list−ref 6 ’(4 6 7 8 0 3 1))
→3
( define ( list−ref n xs ) ;関数定義。nはアトム、xsはリストをとる。
( if ( or ( null? xs ) ;例外を処理。xsが空リストの場合および
( zero? n )) ;nがゼロである場合に空リストを返して終了。
’()
( let (( x ( car xs )) ;変数定義。リストxsのcar部（１番目）をx、
( rest ( cdr xs ))) ;cdr部(２番目以降)をrestに代入している。
( if ( = ( − n 1 ) 0 ) ;再帰の終了条件。n=1の時にxを返して終了。
x
( list−ref ( − n 1 ) rest ))))) ;n=1になるまで再帰的に関数を呼び出す。
＜ポイント 1： 例外処理＞
関数を実行する際に引数として期待されたもの以外が代入された場合には、例外として処理する必要があります。
「リストxsのn番目の要素を返す」ためには、この関数で期待される引数の条件は、n>0とxsが空ではないリストであることです。
したがって、x=0またはxsが空リストの場合には、例外として空リストを返すような処理を記述します。
＜ポイント 2： letによる局所変数定義＞
ここではリストxsのcar部（１番目の要素）をx、cdr部（２番目以降の要素）をrestと定義しています。
この定義は典型的なもので、記述がより簡潔になります。簡潔な記述を心がけてください。
＜ポイント 3： 再帰＞
まず、再帰を終了する条件として、「n=1の場合はxを返す」と定義しておきます。
その上で、( list−ref ( − n 1 ) rest )を返すことにします。
これによって、n=1になるまで、返されるリストrestが更にcar部とcdr部に分けられてxとrestに代入し直されるために、n−1とrestを引数とする関数list−refを繰り返し実行する処理が記述できます。
最終的にはn=1となったときに、n番目の要素がxに、それ以降の要素がrestに代入された状態になり、xが返されます。
<実際に値を代入したときの処理過程の例> ( list−ref 3 ’(a b c d e)) → ( list−ref 2 ’(b c d e)) → ( list−ref 1 ’(c d e)) → c
このような処理によって、関数( list−ref n xs )が実行されています。
これは再帰およびletの典型的な使い方です。
(b) ( fold f z xs )
リストの後ろの要素から順に関数fと引数zで処理して、その結果にさらに同じ処理を繰り返す関数です。
( fold * 2 ’(1 2 3 4 5) )
→ 240
; (* 1(* 2(* 3(* 4(*5 2)))))を計算し240を結果として返します。
(define (fold f z xs) ;関数定義。は関数、zはアトム、xsはリスト。
(cond ((null? xs) #f) ;例外処理。xsが空リストの場合は#fを返す。
((null? (cdr xs)) (f z (car xs)))
;再帰の終了条件。xsの要素が１つの場合に終了。
(else (let ((x (car xs)) ;局所変数定義。
(rest (cdr xs)))
(f x (fold f z rest)))))) ;xsの要素が１つになるまで再帰的に関数を呼び出す。
少し複雑な再帰の例です。
基本的なしくみは前と同じです。
＜ポイント 1： 例外処理＞
xsが空リストの場合に#fを返します。
＜ポイント 2： 局所変数定義＞
let式によってxsのcar部をxに、cdr部をrestに代入します。
＜ポイント 3： 再帰＞
終了条件として、「xsのcdr部が空のときに(f z (car xs))を返す」と定義します。
即ち、xsの要素が１つになったら(f z (car xs))を返して終了します。
リストxsの要素が１つだけになるまで(f x (fold f z rest))を繰り返すことで、結果が１つの数になるまでリストの後ろから順に関数fで処理することになります。
<実際に値を代入したときの処理過程の例> (fold * 2 ’(1 2 3)) → (* 1 (fold * 2 ’(2 3))) → (* 1 (* 2 (fold * 2 ’(3)))) → (* 1 (* 2 (* 2 3))) → (* 1 (* 2 6)) → (* 1 12) → 12
＜他の関数の利用＞
補助的に他の関数を用いること（補助関数）で、関数定義の記述を簡潔にすることができます。
ここでは、補助関数によって目的の関数を定義する方法を示します。
(c) ( min xs )
リストの中で一番小さな要素を戻す関数です。
(min ’(3 5 4 1 8 7 2))
→1
(define (min xs) ;関数定義。xsはリスト。
(cond ((null? xs) ’()) ;例外処理xsが空リストの場合は空リストを返す。
(let ((x (car xs)) ;局所変数定義。
(rest (cdr xs)))
(append (reverse rest) (list x)))))
;再帰処理。xsが空リストになるまで再帰的に関数を呼び出す。
＜ポイント 1： 例外処理＞
リストxsが空リストの場合は空リストを返します。
＜ポイント 2： 局所変数定義＞
他の例と同様に、リストxsのcar部をx、cdr部をrestとします。
＜ポイント 3： 再帰＞
リストxsのcdr部のxを引数にとったreverseと、xsのcar部をリストにしたものとをappendでつなげて返します。
関数listとappendの働きは以下の通りです。
(list ’(x) ’(y)) → ((x) (y)) (append ’(x) ’(y)) → (x y)
<実際に値を代入したときの処理過程の例> (reverse ’(1 2 3)) → (append (reverse ’(2 3)) ’(1)) → (append (append (reverse ’(3)) ’(2)) ’(1)) → (append (append (append ’() ’(3)) ’(2)) ’(1)) → (append (append ’(3) ’(2)) ’(1)) → (append ’(3 2) ’(1)) → (3 2 1)
この２つの違いに注意してください。
(d) ( nub xs )
リスト内の重複する要素を削除する関数です。
( nub ’(4 6 5 3 4 2 6))
→ (4 6 5 3 2)
(define (nub xs) ;関数定義。xsはリスト。
(if (null? xs) ;例外処理および再帰終了条件。
’() ;xsが空リストの場合、空リストを返す。
(let* ((k (car xs)) ;局所変数定義。
(rest (filter (lambda (x) (= x k)) (cdr xs))))
;cdr部からkと同じ要素を除いたものをrestと定義。
(cons k (nub rest))))) ;再帰処理。xsが空リストになるまで再帰的に関数を呼び出す。
;補助関数 (filter f xs) 条件fを満たす要素をxsから除く。
(define (filter f xs)
(if (null? xs)
’()
(let ((x (car xs))
(other (cdr xs)))
(if (f x) ;f=xかどうか。
(filter f other) ;f=xの場合、残りの部分otherを対象にfilterを繰り返す。
(cons x (filter f other)))))) ;f=xでない場合、再帰を行う。
＜ポイント 1： 例外処理＞
リストxsが空リストの場合は空リストを返します。
＜ポイント 2： 局所変数定義＞
補助関数 (filter f xs) を定義しています。
これは、関数fを満たす要素をリストxsから除くという役割をします。
kをxsのcar部、restをcdr部としていますが、このとき、filterによって、cdr部のうちkと同じ要素を除いています。
関数lambda中でkの値を使うため、letではなくlet*を用いています。
＜ポイント 3： 再帰＞
(cons k (nub rest))を返すことで、再帰的に同一要素が排除されたリストが返されます。
<実際に値を代入したときの処理過程の例> (nub ’(1 2 1 3 2)) → (cons 1 (nub ’(2 3 2))) → (cons 1 (cons 2 (nub ’(3)))) → (cons 1 (cons 2 (cons 3 ’()))) → (cons 1 ’(2 3)) → (1 2 3)
＜複雑な処理をする関数＞
複雑な処理を行う関数も、分解してみれば単純な関数の組み合わせで表現されています。
即ち、どんなに複雑な処理を行う関数もごく単純な関数の組み合わせで記述することができます。
(e) ( gen f x n )
関数fをxに対してn回繰り返す関数です。
与えられたxを２倍する関数”nibai”があるとするとき
( gen nibai 3 4 )
→ ( 3 6 12 24 48 )
(define (gen f x n) ;関数定義。fは関数、x、nは数値をとる。
(reverse (bgen f x n))) ;bgenによって返されるリストを反転したものを返す。
;補助関数 ( bgen f x n )
(define (bgen f x n)
(if (= −1 n) ;再帰終了条件。n=−1の場合は空リストを返す。
’()
(cons (f_list f x n) (bgen f x (− n 1)))))
;再帰処理。n>=0の場合、再帰的に関数を呼び出す。
;補助関数 ( f_list f x n ) fn(x)を返す。
(define (f_list f x n)
(cond ((zero? n) x)
(else (f (f_list f x (− n 1))))))
;補助関数 ( nibai x ) xを２倍する。
(define (nibai x) (* x 2))
補助関数( f_list f x n )、( bgen f x n )、( reverse xs )を用いて定義します。
それぞれの関数の役割は以下の通りです。
( f_list f x n ) ;xに関数fをn回適用したもの、即ち、fn(x)を返します。 ( bgen f x n ) ;リスト( fn(x) fn−1(x)・・・f2(x) f(x) x ) を返します。 ( reverse xs ) ;リストxsを反転したものを返します。
最終的には ( bgen f x n ) で返されるリストを ( reverse xs ) で反転させることによって、目的
の関数 ( gen f x n ) を実現します。
(f) ( quicksort xs )
リスト内の要素を小さい順に並べ替える関数です。
(quicksort ’(4 9 2 1 3 8 7 5 0))
→ (0 1 2 3 4 5 7 8 9)
(define (quicksort xs)
(cond ((null? xs) ’()) ;例外処理。xsが空リストの場合空リストを返す。
((null? (cdr xs)) xs) ;再帰終了条件。xsの要素が1または2の場合終了。
((null? (cdr (cdr xs))) (sort xs))
(else (let* ((k (car xs))
(rest (cdr xs))
(ys (filter (lambda (x) (> x k)) rest))
;k以下の要素のリストをysと置く。
(zs (filter (lambda (x) (<= x k)) rest)))
;kより大きい要素のリストをzsと置く。
(append (quicksort ys) (cons k (quicksort zs)))))))
;再帰処理。リストの要素が3以上の場合、再帰的に関数を呼び出す。
;補助関数 ( sort xs ) 対（ペア）の要素を比較し、小さい順に並べ替える。
(define (sort xs)
(let ((x (car xs))
(y (car (cdr xs))))
(if (< x y)
xs
(reverse xs))))
;補助関数 ( filter f xs ) 関数fを満たす要素をリストから除く。
(define (filter f xs)
(if (null? xs)
’()
(let ((x (car xs))
(other (cdr xs)))
(if (f x)
(filter f other)
(cons x (filter f other))))))
補助関数 ( sort xs )、( filter f xs )を用いて定義します。
それぞれの関数の役割は以下の通りです。
( sort xs ) xsを要素が2つのリストと想定して、並べ替えを行う関数です。 ( filter f xs ) リストxsから関数fを満たす要素を除いたリストを返します。
メインの関数では、まずリストxsの要素数によって条件分岐を行います。
要素数が１以下の場合は、そのままリストを返します。
要素数が２の場合は、( sort xs ) を適用した結果を返します。
要素数が３以上の場合は、次の処理を行います。
リストの先頭の要素をkとし、残りの要素をkと比較して、(k以下の要素のリスト)、k、(kより大きい要素のリスト)の順に並べ替えます。
並べ替えた各リストをさらに再帰的に ( quicksort xs ) 関数へ適用することによって、最終的には全ての要素を並べ替えることができます。