前回までは、Scheme (Lisp) の特徴である「リスト」を基本にして、簡単なプログラムを作ってきました。前回までを「初級編」とするならば、いよいよ今回から「中級編」へとステップアップします。
Scheme には、リストのほかにもおもしろい機能や特徴があります。最近の手続き型言語、とくに Lightweight Language は Scheme (Lisp) からいろいろな機能を取り込んでいるので、以前に比べあっと驚くようなことは少なくなりましたが、それでも Scheme から学ぶことはまだまだあると思っています。今回は関数型言語でよく使われる「高階関数」を中心に、Scheme らしい機能を説明します。
Ｃ言語や Pascal が「手続き型言語」と呼ばれるのに対し、Scheme (Lisp) は「関数型言語」と呼ばれています。関数型言語は、データに関数を適用していくことでプログラムを実行します。たとえば、数学の関数を考えてください。
f(x, y) = 2x + 3y
関数 f(x, y) は引数 x と y を与えると値を返します。そして、同じ値の引数を与えれば、結果はいつも同じ値になります。関数型言語の基本的な考え方は、このような数学の関数と同じです。
ところが、Scheme (Lisp) は完全な関数型言語ではありません。引数以外の変数を定義して、define や set! で値を代入することができるからです。つまり、変数の値を書き換えることでプログラムを実行する「手続き型言語」の機能もあるわけです。とくに Common Lisp の場合、手続き型言語からいろいろな機能が持ち込まれたため、ほかの関数型言語に比べると不純度の高い関数型言語になっています。
それから、関数型言語の場合、関数はほかのデータと同等に取り扱うことができます。つまり、関数を変数に代入したり、引数として渡すことができるのです。また、値として関数を返すこともできるので、関数を作る関数を定義することができます。関数を引数として受け取る関数を「汎関数 (functional) 」とか「高階関数 (higher order function) 」と呼びます。
Scheme などの関数型言語にとって、高階関数は特別なものではありません。Scheme (Lisp) には便利な高階関数がいろいろと用意されていますし、私たちユーザーが定義することも簡単にできるのです。最初に、マップ関数から説明しましょう。
Scheme の場合、繰り返し処理といえば「再帰定義」ですね。単純な繰り返しならば、末尾再帰 (名前付き let) を使うことができます。このほかに、Scheme (Lisp) には「マップ関数 (mapping function) 」という便利な関数が用意されています。
簡単な例題として、リストの要素どうしを足し算して、その結果をリストに格納する関数を作ってみましょう。つまり、次のような処理を行います。
( 1 2 3 4 5)
+ (10 20 30 40 50)
---------------------
(11 22 33 44 55)
図 : 要素どうしの足し算
これを再帰定義でプログラムすると、次のようになるでしょう。
リスト : リストの要素を足し算する
(define (add-element x y)
(if (null? x)
'()
(cons (+ (car x) (car y))
(add-element (cdr x) (cdr y)))))
関数名は add-element としました。ところで、そろそろ「再帰定義」にも慣れてきたと思いますが、add-element の処理内容は理解できたでしょうか。よく分からない方は、次の処理手順を見て考えてください。
│(1 2 3 4) (10 20 30 40)
│ = = ─────→ (11 22 33 44)
再 ↓ ↑
帰 │(2 3 4) (20 30 40) │
呼 │ = = ─────→ (22 33 44)
び ↓ ↑
出 │(3 4) (30 40) │
し │ = = ─────→ (33 44)
↓ ↑
│(4) (40) │
│ = = ─────→ (44)
↓ ↑
() () ───→ () ─┘
図 : add-element の処理手順
実は、この処理はマップ関数 map だけで実現できるのです。まずは、実行例を見てください。
gosh> (add-element '(1 2 3 4 5) '(10 20 30 40 50)) (11 22 33 44 55) gosh> (map + '(1 2 3 4 5) '(10 20 30 40 50)) (11 22 33 44 55)
+ は足し算をする関数でした。関数の処理内容はシンボルに格納されています。つまり、map には + に格納されている関数を渡しているのです。Gauche の場合、+ の値を表示すると次のようになります。
gosh> + #<subr +>
Gauche の場合、プリミティブの関数は #<subr 名前> と表示されます。このように、関数を引数として渡すことができるのが Scheme (Lisp) の特徴のひとつです。map は渡された関数をリストの各要素に適用して、その結果をリストに格納して返します。もし、各要素に対して乗算 * を適用したい場合は、関数 * を map に渡せばいいのです。
gosh> (map * '(1 2 3 4 5) '(10 20 30 40 50)) (10 40 90 160 250)
もちろん、私たちが定義した関数を渡すこともできます。もし、リストの要素を 2 乗したい場合は、数を 2 乗する関数 square を定義して、それを map に渡せばいいのです。
gosh> (define (square x) (* x x)) square gosh> (map square '(1 3 4 5 7)) (1 9 16 25 49)
map を使う場合、渡された関数にとって必要なだけの引数を用意しないと、当然のことですがエラーになります。引数のリストの長さが異なる場合は、短いリストの要素がなくなった時点で処理を終了します。
gosh> (map cons '(a b c d) '(1 2 3 4 5)) ((a . 1) (b . 2) (c . 3) (d . 4))
なお、シンタックス形式の関数を map に渡すことはできません。その場合はエラーになります。
それではここでマップ関数を作ってみましょう。プログラムを簡単にするため、マップ関数に渡すことができる関数は引数をひとつだけ取るものに限定します。プログラムは次のようになります。
リスト : マップ関数
(define (my-map func ls)
(if (null? ls)
'()
(cons (func (car ls)) (my-map func (cdr ls)))))
関数名は my-map としました。引数 func はリストの要素に適用する関数です。func を呼び出す方法は、今までの関数呼び出しとまったく同じで、リストの先頭の要素に func を書くだけです。func に格納された値は関数なので、func を評価するとその「関数」が得られます。リストの先頭の要素が関数なので、Scheme は func に格納されている値を関数として呼び出すのです。もしも、func の値が関数でなければエラーになります。
ちなみに、Common Lisp の場合、変数 func に格納された関数をそのまま呼び出すことはできません。funcall という特別な関数を使って、(funcall func ...) というようにプログラムする必要があります。関数の扱い方は Scheme の方が関数型言語らしくてすっきりしていると思います。
フィルター (filter) はリストの要素に関数 predicate を適用し、predicate が真を返す要素をリストに格納して返す関数です。
ところで、Scheme の仕様書 R5RS は必要最低限の機能しか定義されていないため、多くの Scheme 処理系で機能追加や拡張が行われています。この拡張機能の標準化を目的に SRFI (Scheme Requests For Implementation) という仕様が定められています。Gauche でも多くの SRFI がサポートされています。
その中で、SRFI-1 にはリスト操作を行う関数が多数定義されています。SRFI-1 には filter や remove という関数が定義されていますが、ここでは勉強のため述語が真を返す要素を削除する関数 remove-if を作ってみましょう。名前は Common Lisp から拝借しました。
リスト ; 述語が真となる要素を削除する
(define (remove-if predicate ls)
(cond ((null? ls) '())
((predicate (car ls))
(remove-if predicate (cdr ls)))
(else
(cons (car ls) (remove-if predicate (cdr ls))))))
remove-if も簡単ですね。要素に predicate を適用して結果が真ならば要素をリストに加えません。結果が偽ならば要素をリストに加えるだけです。
簡単な実行例を示しましょう。
gosh> (remove-if odd? '(1 2 3 4 5)) (2 4) gosh> (remove-if even? '(1 2 3 4 5)) (1 3 5)
odd? は引数が奇数のときに #t を返す述語で、even? は偶数のときに #t を返す述語です。remove-if に odd? を渡すとリストから奇数の要素を削除することができ、even? を渡すと偶数の要素を削除することができます。
もちろん、フィルターも簡単に定義することができます。remove-if とは逆に、述語が真を返すとき要素をリストに追加し、偽を返すときはリストに加えません。
リスト : 述語が真となる要素を取り出す
(define (filter predicate ls)
(cond ((null? ls) '())
((predicate (car ls))
(cons (car ls) (filter predicate (cdr ls))))
(else
(filter predicate (cdr ls)))))
簡単な実行例を示しましょう。
gosh> (filter odd? '(1 2 3 4 5)) (1 3 5) gosh> (filter even? '(1 2 3 4 5)) (2 4)
前回作成したコマンドラインパラメータからオプションを取り出す関数 get-option やオプションを取り除く関数 remove-option は、フィルターを使うと簡単にプログラムすることができます。
リスト : オプションの取得と削除
; オプションか？
(define (option? item)
(char=? #\- (string-ref item 0)))
; オプションを取り出す
(define (get-option ls)
(filter option? ls))
; オプションを取り除く
(define (remove-option ls)
(remove-if option? ls))
関数 option? は - で始まる文字列ならば #t を、そうでなければ #f を返します。オプションを取り出す get-option は filter に option? を渡すだけで実現できます。オプションを取り除く remove-option は remove-if に option? を渡すだけです。
2 つの引数を取る関数 f とリストを引数に受け取る関数 reduce を考えます。reduce はリストの各要素に対して関数 f を次のように適用します。
(1) (a1 a2 a3 ... an-1 an) => (f (f ... (f (f a1 a2) a3) ...) an-1) an) (2) (a1 a2 a3 ... an-1 an) => (f a1 (f a2 (f a3 ... (f an-1 an) ... )))
関数 f を適用する順番で 2 通りの方法があります。たとえば、関数 f が単純な加算関数とすると、reduce の結果はどちらの場合もリストの要素の和になります。
f(x, y) = x + y の場合 : reduce => a1 + a2 + a3 + ... + an-1 + an
このように、reduce はリストのすべての要素を関数 f を用いて結合します。この操作を「縮約」とか「畳み込み」といいます。また、reduce の引数に初期値 g を指定することがあります。この場合、reduce は次のような動作になります。
(1) (a1 a2 a3 ... an-1 an) => (f ... (f (f g a1) a2) ...) an-1) an) (2) (a1 a2 a3 ... an-1 an) => (f a1 (f a2 (f a3 ... (f an g) ...)))
SRFI-1 には fold, fold-right, reduce, reduce-right という同等の機能を持つ関数が定義されているので、ここでは (1) の動作を行う関数 my-reduce と、(2) の動作を行う関数 my-reduce-right を作ってみましょう。プログラムは次のようになります。
リスト ; 畳み込み
(define (my-reduce f g ls)
(if (null? ls)
g
(my-reduce f (f g (car ls)) (cdr ls))))
(define (my-reduce-right f g ls)
(if (null? ls)
g
(f (car ls) (my-reduce-right f g (cdr ls)))))
第 1 引数 f が適用する関数、第 2 引数 g が初期値、第 3 引数がリストです。最初に、ls が空リストかチェックします。これが再帰呼び出しの停止条件になりますが、my-reduce, my-reduce-right に空リストが与えられた場合にも対応します。この場合は初期値 g を返します。次の else 節で関数 f を適用して my-reduce, my-reduce-right を再帰呼び出しします。
my-reduce の場合、引数 g とリストの要素が関数 f の引数になり、その返り値が my-reduce を再帰呼び出しするときの第 2 引数 g になります。つまり、リストの要素が f の第 2 引数になり、第 1 引数にはこれまでの処理結果が渡されます。
my-reduce-right の場合は逆になり、関数 f の第 1 引数にリストの要素が渡されて、これまでの処理結果は第 2 引数に渡されます。my-reduce-right はリストの最後尾から処理を行うため、my-reduce-right を再帰呼び出しした結果を関数 f の第 2 引数に渡します。
たとえば、(my-reduce-right f g '(a1 a2 a3)) は次のように展開されます。
(my-reduce-right f g (a1 a2 a3))
↓
(f a1 (my-reduce-right f g (a2 a3)))
↓
(f a1 (f a2 (my-reduce-right f g (a3))))
↓
(f a1 (f a2 (f a3 (my-reduce-right f g ()))))
↓
(f a1 (f a2 (f a3 g)))
図 : my-reduce-right の動作
これで reduce の (2) の動作を実現することができます。それでは、簡単な実行例を示しましょう。
gosh> (my-reduce + 0 '(1 2 3 4 5)) 15 gosh> (my-reduce-right + 0 '(1 2 3 4 5)) 15 gosh> (my-reduce cons '() '(a b c d e)) (((((() . a) . b) . c) . d) . e) gosh> (my-reduce-right cons '() '(a b c d e)) (a b c d e) gosh> (my-reduce list 0 '(1 2 3 4 5)) (((((0 1) 2) 3) 4) 5) gosh> (my-reduce-right list 6 '(1 2 3 4 5)) (1 (2 (3 (4 (5 6)))))
cons や list を用いてリストの要素を結合してみると、畳み込みの動作や my-reduce と my-reduce-right の違いがよくわかると思います。
ところで、reduce と 2 引数の関数を組み合わせると、いろいろな関数を実現することができます。たとえば、length, map, filter などの例を示します。
リスト : reduce の応用例
; リストの長さ
(define (my-length ls)
(define (f x y) (+ x 1))
(my-reduce f 0 ls))
; 述語が真となる要素を数える
(define (count-if predicate ls)
(define (f x y)
(if (predicate y) (+ x 1) x))
(my-reduce f 0 ls))
; マップ関数
(define (my-map f ls)
(define (f1 x y) (cons (f x) y))
(my-reduce-right f1 '() ls))
; フィルター
(define (my-filter f ls)
(define (f1 x y)
(if (f x)
(cons x y)
y))
(my-reduce-right f1 '() ls))
my-reduce の場合、関数 f の第 2 引数にリストの要素、第 1 引数に今までの計算結果が渡されます。したがって、my-length は初期値を 0 にして第 1 引数の値を +1 することで実現できます。count-if は Common Lisp の関数と同じで、条件を満たしている要素の個数を数えます。関数 f の引数 y を predicate に適用し、真を返す場合は x を +1 します。
my-reduce-right の場合、関数 f の第 1 引数にリストの要素、第 2 引数に今までの計算結果が渡されます。したがって、my-map は初期値を空リストにして第 1 引数の計算結果を第 2 引数のリストに追加するだけです。my-filter の場合も初期値を空リストにして、第 1 引数が条件を満たしていれば第 2 引数のリストに追加します。
なお、どちらの関数も内部関数から引数 f の関数を呼び出しています。Scheme の場合、内部関数から外側の関数の局所変数にアクセスすることができます。このことについては次回で詳しく説明します。
次は apply を説明します。
apply は最初の引数 func を関数として呼び出します。このとき、第 2 引数のリストの要素が func の引数として渡されます。apply は func の評価結果を返します。簡単な使用例を示しましょう。
gosh> (apply + '(1 2 3)) 6 gosh> (apply car '((1 2 3))) 1
また apply は次のように、func と args-list の間に引数を与えることができます。
gosh> (apply + 4 5 6 '(1 2 3)) 21
apply はリストに格納されている要素を引数として関数に渡す場合に便利です。
ところで、高階関数を使うようになると、数を 2 乗する square のような小さな関数を、いちいち定義するのが面倒になります。とくに、その高階関数でしか使わないのであれば、なおさらそう思うでしょう。
このような場合、Scheme (Lisp) では「ラムダ式 (lambda expression) 」を使うことができます。ラムダはギリシャ文字のλのことです。それでは、理屈はともかくラムダ式の使用例を見てください。
gosh> (map (lambda (x) (* x x)) '(1 2 3 4 5)) (1 4 9 16 25)
(lambda (x) (* x x)) がラムダ式です。このように、ラムダ式はリストで、かつ、その第 1 要素には lambda というシンボルがセットされています。ラムダ式の構造は、関数を定義する define とよく似ています。
(lambda (define (<関数名>
(<仮引数名> ....) <仮引数名> ... )
処理１ 処理１
処理２ 処理２
・・・ ・・・
処理Ｍ) 処理Ｍ)
（１）ラムダ式 （２）defun による関数定義
図 : ラムダ式の構文
define と関数名の代わりに lambda を書かけば、あとは define と全く同じです。実は、define で定義する関数の実体がこのラムダ式なのです。次の例を見てください。
gosh> (lambda (x) (* x x)) #<closure #f> gosh> (define square (lambda (x) (* x x))) square gosh> (square 10) 100
Scheme の場合、ラムダ式を評価すると関数を表すデータになります。Scheme ではこれを「クロージャ (closure) 」といいます。クロージャには重要な働きがあるのですが、ここではクロージャは関数を表すデータ型のひとつと考えてください。クロージャについては次回で詳しく説明します。
そして、このクロージャを define で変数に束縛すれば、関数を定義することができるのです。Scheme プログラマの中には、ラムダ式による関数定義を好む人も多いようです。また、次のようにラムダ式をリストの先頭要素にもってくれば、それを評価することができます。
gosh> ((lambda (x) (* x x)) 2) 4
このように、ラムダ式を使えば名前のない関数を定義することができます。ちなみに 参考文献 [9-1] によると、『昔の Lisp プログラムは最初はラムダ式で書かれていた』 とのことです。このドキュメントでは、関数を定義する define から説明しましたが、Lisp の歴史ではラムダ式の方が先輩だったのですね。
高階関数でラムダ式を使うのは便利で、なおかつ、その場で実行される処理内容が確認できるという利点があります。しかし、同じラムダ式があちこちに現れるようでは問題があります。プログラムに変更はつきもので、もし、その処理を変更しようとした場合、該当するラムダ式をすべて修正しなくてはなりません。これは面倒なことですね。この場合は、define で関数を定義した方がよいのです。そうすると、その関数を修正するだけで済みます。
ところで、リストに同じ要素があるか調べる場合、関数 memq, memv, member を用いることができます。これらの関数は等値関係を述語 eq?, eqv?, equal? でテストしますが、場合によってはある条件を満たす要素を探したいこともあります。このような場合、リストを探索する関数を高階関数として定義しておくと便利です。実際、SRFI-1 には便利な関数が用意されていますが、ここで勉強のため実際に作ってみましょう。
最初は関数 find を作ります。find はリストの中から predicate が真を返す最初の要素を返します。find はリストの先頭から順番に探索します。見つからない場合は #f を返します。プログラムは次のようになります。
リスト : リストの探索
(define (find predicate ls)
(let loop ((ls ls))
(cond ((null? ls) #f)
((predicate (car ls))
(car ls))
(else
(loop (cdr ls))))))
リスト ls の要素を先頭から順番に調べていきます。ls が空リストの場合は探索失敗なので #f を返します。リストの要素に predicate を適用して真となる場合はその要素を返します。そうでなければ次の要素を調べます。
簡単な使用例を示します。
gosh> (find odd? '(1 2 3 4 5 6)) 1 gosh> (find (lambda (x) (< 10 x)) '(5 10 15 20 25)) 15
次は find と似ていますが、見つけた要素の位置を返す関数 position を作ります。次のリストを見てください。
リスト : 見つけた要素の位置を返す
(define (position predicate ls)
(let loop ((ls ls) (n 0))
(cond ((null? ls) #f)
((predicate (car ls)) n)
(else
(loop (cdr ls) (+ n 1))))))
position はリストの中から predicate が真となる最初の要素の位置を返します。局所変数 n で要素の位置を求めます。predicate が真となる要素を見つけたら n を返します。次の要素を調べるときは、変数 n の値を +1 することをお忘れなく。
簡単な使用例を示しましょう。
sosh> (position even? '(1 2 3 4 5 6)) 1 gosh> (postion odd? '(1 2 3 4 5 6)) 0
最後に、述語が真となる要素を数える関数 count を作ります。reduce を使わなくても末尾再帰でプログラムを作ることができます。次のリストを見てください。
リスト : 述語が真となる要素を数える
(define (count predicate ls)
(let loop ((ls ls) (n 0))
(cond ((null? ls) n)
((predicate (car ls))
(loop (cdr ls) (+ n 1)))
(else
(loop (cdr ls) n)))))
predicate が真となる要素を局所変数 n でカウントします。find, position と違って、リストを最後まで調べることに注意してください。リスト ls が空リストの場合、変数 n の値を返します。loop を再帰呼び出しする場合、predicate が真のときは n を +1 して、そうでなければ n の値はそのままです。
簡単な使用例を示しましょう。
gosh> (count odd? '(1 2 3 4 5 6)) 3 gosh> (count (lambda (x) (< 10 x)) '(5 10 15 20 25)) 3
ところで、数当てゲーム [2] で「マスターマインド」を作成しましたが、bulls を数える関数 count-bulls を再帰定義で作りましたね。実は、今回説明した map と count を組み合わせると、とても簡単に count-bulls を作ることができるのです。まず、再帰版のプログラムを再度示しましょう。
リスト : bulls を求める (再帰版)
(define (count-bulls answer data)
(cond ((null? answer) 0)
((= (car answer) (car data))
(+ 1 (count-bulls (cdr answer) (cdr data))))
(else
(count-bulls (cdr answer) (cdr data)))))
count-bulls は同じ位置にある要素を比較して、等しい要素の個数を数えます。この「同じ位置にある要素を比較する」処理は map を使えば簡単に実現できます。
gosh> (map = '(1 2 3 4) '(1 4 3 6)) (#t #f #t #f)
map に関数 = を渡せば、2 つのリストの要素を比較して、その結果をリストに格納して返します。あとは count で #t の個数を数えればいいのです。したがって count-bulls は次のようになります。
リスト : bulls を求める(map 版)
(define (count-bulls answer data)
(count (lambda (x) (eq? x #t)) (map = answer data)))
このように、高階関数を使うとプログラムを簡単に作ることができます。
ここでもうひとつ、Scheme (Lisp) らしいデータ構造を紹介しましょう。「連想リスト (association list : a-list) 」はドット対を要素とするリストです。ドット対の CAR 部がキーで、CDR 部がデータに対応します。次の図を見てください。
┌───┬───┬───┬──→ データ
│ │ │ │
連想リスト => ((a . b) (c . d) (e . f) (g . h))
│ │ │ │
└───┴───┴───┴──→ キー
図 : 連想リストの構造
上図の場合、a, c, e, g がキーで、b, d, f, h がデータとなります。キーやデータはシンボル以外の S 式でもかまいません。そして、連想リストからデータを探索する関数が assq, assv, assoc です。
assoc は member と同様に Lisp の伝統的な関数です。assoc は連想リスト a-list から obj と等しいキーを探します。見つからない場合は #f を返します。等値関係のテストは member と同様に、assq が eq? を、assv が eqv? を、assoc が equal? を用います。
簡単な使用例を示しましょう。
gosh> (define z '((a . b) (c . d) (e . f) (g . h))) z gosh> (assoc 'e z) (e . f) gosh> (assoc 'h z) #f
assq, assv, assoc は、見つけたキーのデータを返すのではなく、ドット対を返すことに注意してください。
連想リストにデータを追加する場合、cons でも簡単にできますが acons を使うと便利です。
acons は (cons (cons key data) a-list) と同じです。R5RS にはありませんが、Gauche には用意されています。
gosh> (acons 'x 1 z) ((x . 1) (a . b) (c . d) (e . f) (g . h))
assoc はキーを探索しますが、データ（ドット対の CDR 部）を探索する関数が rassoc です。SRFI-1 にはありませんが、Gauche のライブラリ (util.list) に用意されています。
rassoc は連想リスト a-list から obj と等しいデータ (CDR 部) を探します。見つからない場合は #f を返します。等値関係のテストは assoc と同様に、rassq が eq? を、rassv が eqv? を、rassoc が equal? を用います。
簡単な使用例を示しましょう。
gosh> (define z '((a . b) (c . d) (e . f) (g . h))) z gosh> (rassoc 'f z) (e . f) gosh> (rassoc 'g z) #f
assoc と同様にドット対を返すことに注意してください。
今回はここまでです。簡単に復習しておきましょう。
次回は「クロージャ」について説明します。