高階関数とラムダ式
Ｃ言語や Pascal が「手続き型言語」と呼ばれるのに対し、Lisp は「関数型言語」と呼ばれています。関数型言語は、データに関数を適用していくことでプログラムを実行します。たとえば、数学の関数を考えてください。
関数 f(x, y) は引数 x と y を与えると値を返します。そして、同じ値の引数を与えれば、結果はいつも同じ値になります。関数型言語の基本的な考え方は、このような数学の関数と同じです。
ところが、Lisp は完全な関数型言語ではありません。引数以外の変数を定義して、setq などで値を代入することができるからです。つまり、変数の値を書き換えることでプログラムを実行する「手続き型言語」の機能もあるわけです。とくに Common Lisp の場合、手続き型言語からいろいろな機能が持ち込まれたため、ほかの関数型言語に比べると不純度の高い関数型言語になっています。
それから、関数型言語の場合、関数はほかのデータと同等に取り扱うことができます。つまり、関数を変数に代入したり、引数として渡すことができるのです。また、値として関数を返すこともできるので、関数を作る関数を定義することができます。関数を引数として受け取る関数を「汎関数 (functional)」とか「高階関数 (higher order function)」と呼びます。ここでは、高階関数とラムダ式について説明します。
●マップ関数 mapcar
Common Lisp の場合、単純な繰り返しは dotimes, dolist, do, loop などを使って簡単にプログラムできます。もっと複雑な処理ならば、再帰定義でプログラムを作成することができます。このほかに、Common Lisp には「マップ関数 (mapping function)」という便利な関数が用意されています。
簡単な例題として、リストの要素同士を足し算して、その結果をリストに格納する関数を作ってみましょう。次の例を見てください。
( 1 2 3 4 5) + (10 20 30 40 50) -------------------- (11 22 33 44 55)
これを再帰定義でプログラミングすると、次のようになるでしょう。
リスト : リストの要素を足し算する
(defun add-element (xs ys)
(if (or (null xs) (null ys))
nil
(cons (+ (car xs) (car ys))
(add-element (cdr xs) (cdr ys)))))
関数名は add-element としました。実は、この処理はマップ関数 mapcar だけで実現できるのです。まずは、実行例を見てください。
* (add-element '(1 2 3 4 5) '(10 20 30 40 50)) (11 22 33 44 55) * (mapcar #'+ '(1 2 3 4 5) '(10 20 30 40 50)) (11 22 33 44 55)
mapcar の引数に見慣れぬ記号 #' がありますね。#'+ は (function +) の省略形です。function は特殊形式で、シンボルに格納されている関数を取り出す働きをします。#'+ であれば、シンボル + から加算を行う処理を取り出します。つまり、mapcar にはシンボル + に格納されている値ではなく、「関数 (function)」を渡しているのです。実際に function を実行してみましょう。
* (function +) #<FUNCTION +> * (typep #'+ 'function) T * (type-of #'+) FUNCTION
関数のデータ型は function になります。このように、関数を引数として渡すことができるのが Lisp の特徴のひとつです。
mapcar は渡された関数をリストの各要素に適用して、その結果をリストに格納して返します。もし、各要素に対して乗算 * を実行したい場合は、#'* を mapcar に渡せばいいのです。
* (mapcar #'* '(1 2 3 4 5) '(10 20 30 40 50)) (10 40 90 160 250)
もちろん、私達が定義した関数も渡すことができます。もし、リストの要素を 2 乗したい場合は、数を 2 乗する関数 square を定義して、それを mapcar に渡せばいいのです。
* (defun square (x) (* x x)) SQUARE * (mapcar #'square '(1 3 4 5 7)) (1 9 16 25 49)
このように、マップ関数を使ってデータを簡単に変換することができますが、それだけではなく、リストからデータを取り出すことも簡単にできます。
* (mapcar #'car '((a . 1) (b . 2) (c . 3))) (A B C) * (mapcar #'cdr '((a . 1) (b . 2) (c . 3))) (1 2 3)
それから、指定した関数に必要な引数を用意しないと、当然のことですがエラーになります。引数のリストの長さが異なる場合は、短いリストの要素がなくなった時点で処理を終了します。次の例を見てください。
* (mapcar #'cons '(a b c d) '(1 2 3 4 5)) ((A . 1) (B . 2) (C . 3) (D . 4))
mapcar のように、関数を引数として受け取る関数を「汎関数 (functional)」とか「高階関数 (higher order function)」と呼ぶことがあります。Lisp の世界では、高階関数は特別なものではありません。Lisp には便利な高階関数がいろいろと用意されていますし、私達ユーザーが定義することもできるのです。そのためには、重要な 2 つの高階関数 funcall と apply が必要になります。
●apply
まず apply から説明しましょう。
apply func args-list
apply は、最初の引数 func を第 2 引数 args-list に適用して、その結果を返します。args-list はリストでなければいけません。簡単な使用例を示しましょう。
* (apply #'+ '(1 2 3)) 6 * (+ 1 2 3) 6 * (apply #'car '((1 2 3))) 1 * (car '(1 2 3)) 1
また、apply は次のように func と args-list の間に引数を与えることができます。
* (apply #'+ 4 5 6 '(1 2 3)) 21
apply はリストに格納されている要素を、引数として関数に渡す場合に便利です。たとえば、リストに格納された文字列の文字数の合計を求める処理を考えてみましょう。mapcar に関数 length を渡せば、各要素の文字数を数えることができます。
* (mapcar #'length '("abc" "defg" "hijkl" "mnopqr"))
(3 4 5 6)
あとは各要素を足し算するだけですが、リストのままでは関数 + を使うことができません。この場合は apply を使うといいのです。
* (apply #'+ (mapcar #'length '("abc" "defg" "hijkl" "mnopqr")))
18
dolist のような繰り返し関数を使うと、次のようになるでしょう。
リスト : 文字数の合計を求める
(let ((total 0))
(dolist (x '("abc" "defg" "hijkl" "mnopqr") total)
(setq total (+ total (length x)))))
dolist を使うと変数 total が必要になるので、プログラムが少しだけ複雑になります。
●funcall
次は funcall を説明しましょう。
funcall func args ...
funcall は最初の引数 func を残りの引数 args に適用し、その結果を返します。簡単な使用例を示しましょう。
* (funcall #'+ 1 2 3) 6 * (+ 1 2 3) 6 * (funcall #'car '(a b c)) A * (car '(a b c)) A
さて、これだけでは funcall が何の役に立つのかわかりませんね。ところが funcall を使うことで、関数を引数として扱う高階関数を定義することができるのです。次の例を見てください。
リスト : 高階関数の定義（誤例） (defun execfunc (func arg1 arg2) (func arg1 arg2))
関数 execfunc は第 1 引数に処理を行う関数を受け取り、残りの引数をその関数に適用します。上記のリストを実際に試してみると、"The function COMMON-LISP-USER::FUNC is undefined." というエラー [*1] が表示されます。
* (execfunc #'+ 1 2) => エラー
シンボルは変数の値と関数を別々に格納しています。この場合、シンボル func に定義されている関数を実行しようとします。ところが、シンボル func には関数が定義されていないのでエラーとなるのです。ここで実行しようとする関数は変数 func に値として格納されているので、リストの先頭に func を書いてはいけません。変数 func に格納された関数を実行する場合は funcall を使います。
リスト : 高階関数の定義（正解） (defun execfunc (func arg1 arg2) (funcall func arg1 arg2))
これで、変数 func に格納されている値（関数）が取り出され、それが funcall に渡されるので正常に動作します。
* (execfunc #'+ 1 2) 3
[*1] SBCL では defun で execfunc を定義した時点でワーニングが表示されます。
●関数はシンボルで渡すこともできる
Common Lisp の場合、プリミティブ (primitive) な関数や defun で定義された関数は、シンボルを使って高階関数に渡すこともできます。
* (apply '+ '(1 2 3)) 6 * (funcall '* 1 2 3 4 5) 120 * (mapcar 'square '(1 2 3 4 5)) (1 4 9 16 25)
高階関数にシンボルを渡すと、そのシンボルに格納されている関数を使います。まだ説明していませんが、Common Lisp には「局所関数 (local function)」を定義する機能があります。局所関数を高階関数に渡すとき、シンボルを使ってはいけません。局所的な関数ではなく、大域的な関数が渡されてしまいます。局所関数を渡すときは #' を使用することになります。
●キーワード引数
Common Lisp の関数 member は等値の判定に述語 eql を使うのがデフォルトの動作です。Common Lisp には「キーワード引数 (keyword argument)」によって関数の基本動作を変更する仕組みが用意されています。次の例を見てください。
* (member '(a d) '((a b) (a c) (a d) (a e))) NIL * (member '(a d) '((a b) (a c) (a d) (a e)) :test #'equal) ((A D) (A E)) * (member '(a d) '((a b) (a c) (a d) (a e)) :test 'equal) ((A D) (A E))
2 番目の例で、コロン ( : ) から始まる引数がありますね。Common Lisp では、これを「キーワード (keyword)」といいます。キーワードはシンボルの一種 (データ型は keyword) です。T や NIL と同じように、その値は自分自身で初期化されていて、値を書き換えることはできません。
* :test :TEST * (typep :test 'symbol) T * (type-of :test) KEYWORD
キーワードの次がキーワード引数です。:test は等値の判定で使用する述語を指定するキーワードです。:test に #'equal を指定することで、等値の判定を eql から equal に変更することができます。指定できるキーワードは関数によって異なります。
最初の例は述語 eql で等値を判定するので、リストとリストの比較は必ず偽になります。したがって、(A D) を見つけることができず返り値は NIL になります。2 番目の例で述語を equal に変更すると、リストとリストの比較ができるので、(A D) を見つけることができます。
●ラムダ式は無名の関数を定義する
Lisp はリストの先頭要素がシンボルの場合、それを関数として呼び出しました。実は、もうひとつ関数として呼び出す形式があります。それは、リストの先頭要素がリストで、そのリストの先頭要素が lambda というシンボルの場合です。言葉で説明すると難しいので、さっそく例をみてください。
((lambda (x) (* x x)) 2) => 4 ~~~~~~~~~~~~~~~~~~~~
下線で示した部分がリストの先頭要素です。リストになっていますね。このリストの先頭要素が lambda になっています。このように、先頭要素が lambda のリストを「ラムダ式 (lambda expression)」といい、ラムダ式が先頭要素の S 式を「ラムダフォーム (lambda form)」といいます。ラムダはギリシャ文字λのことです。ラムダ式の構造は関数を定義する defun とよく似ています。次の図を見てください。
defun と関数名の代わりに lambda を書けば、あとは defun とまったく同じです。
CLHS: Macro LAMBDA, CLHS: Symbol LAMBDA によると、ANSI Common Lisp の lambda はマクロとして定義されていて、ラムダ式は次の S 式と同じになります。
(lambda (x) (* x x)) == (function (lambda (x) (* x x)) == #'(lambda (x) (* x x))
* (lambda (x) (* x x))
#<FUNCTION (LAMBDA (X)) {1001BE8D9B}>
そして、ラムダフォームは次の S 式と同じになります。
((lambda (x) (* x x) 2) == (funcall #'(lambda (x) (* x x)) 2)
* ((lambda (x) (* x x)) 2) 4 * (funcall #'(lambda (x) (* x x)) 2) 4
この場合、実引数 2 がラムダ式の仮引数 x に代入され、S 式 (* x x) が評価されて 4 という結果になります。このように、ラムダ式を使えば「名前の無い関数 (無名関数や匿名関数という)」を定義することができます。
ところで、高階関数を使うようになると、数を 2 乗する square のような小さな関数を、いちいち定義するのが面倒になります。高階関数に与える関数はラムダ式でも有効です。たとえば、リストの要素を 2 乗する処理は次のようにラムダ式を使って実現できます。
* (mapcar (lambda (x) (* x x)) '(1 2 3 4 5)) (1 4 9 16 25)
わざわざ関数 square を定義しなくてもいいので簡単ですね。このように、高階関数でラムダ式を使うのはとても便利で、なおかつ、その場で実行される処理内容が確認できるという利点があります。
しかし、同じラムダ式があちこちに現れるようでは問題があります。プログラムに変更はつきものです。もし、その処理を変更しようとした場合、該当するラムダ式をすべて修正しなくてはなりません。これではラムダ式を使う意味がありませんね。このような場合、defun で関数を定義した方がよいでしょう。そうすると、その関数を修正するだけで済みます。
ところで、大昔の Lisp には function 特殊形式 (#') がなく、高階関数に関数を渡すときは '+ や '(lambda ...) のようにクォートを使いました。昔の Lisp (ANSI Common Lisp 以前) では、#' を使わずに ' でもラムダ式を渡すことができましたが、ANSI Common Lisp ではエラーになります。ご注意くださいませ。
●マッピング
それでは、関数型言語でよく使用される高階関数を実際に作ってみましょう。最初はマッピングです。Common Lisp には mapcar や maplist など便利なマップ関数が用意されていますが、私達でも簡単にプログラムを作ることができます。次のリストを見てください。
リスト : マップ関数
(defun map1 (fn xs)
(if (null xs)
nil
(cons (funcall fn (car xs))
(map1 fn (cdr xs)))))
(defun map2 (fn xs ys)
(if (or (null xs) (null ys))
nil
(cons (funcall fn (car xs) (car ys))
(map2 fn (cdr xs) (cdr ys)))))
各関数の引数 FN はリストの要素に適用する関数です。map1 はリスト XS の要素に関数 fn を適用し、その結果をリストに格納して返します。map2 は二つのリスト XS, YS の要素に関数 FN を適用します。なお、三つ以上のリストに対応させることも可能ですが、まだ可変個引数の話をしていないので、ここまでにしておきましょう。
簡単な実行例を示します。
* (map1 #'- '(1 2 3)) (-1 -2 -3) * (map2 #'+ '(1 2 3) '(4 5 6)) (5 7 9)
●フィルター
「フィルター (filter)」はリストの要素に述語を適用し、述語が真を返す要素をリストに格納して返す関数です。関数 filter を再帰定義でプログラムすると次のようになります。
リスト : フィルター
(defun filter (pred xs)
(cond ((null xs) nil)
((funcall pred (car xs))
(cons (car xs) (filter pred (cdr xs))))
(t (filter pred (cdr xs)))))
引数 PRED が述語で、XS がリストです。述語が真を返すとき要素を返り値のリストに追加し、偽を返すときはリストに加えません。
簡単な実行例を示します。
* (filter #'evenp '(1 2 3 4 5 6)) (2 4 6) * (filter #'oddp '(1 2 3 4 5 6)) (1 3 5)
Common Lisp には条件を満たす要素を削除する remove-if という高階関数があります。
●畳み込み
2 つの引数を取る関数 f とリストを引数に受け取る関数 reduce を考えます。reduce はリストの各要素に対して関数 f を下図のように適用します。
(1) (a1 a2 a3 a4 a5)
=> f( f( f( f( a1, a2 ), a3 ), a4 ), a5 )
(2) (a1 a2 a3 a4 a5)
=> f( a1, f( a2, f( a3, f( a4, a5 ) ) ) )
図 : 関数 reduce の動作
関数 f を適用する順番で 2 通りの方法があります。上図 (1) はリストの先頭から f を適用し、上図 (2) はリストの後ろから f を適用します。たとえば、関数 f が単純な加算関数とすると、reduce の結果はどちらの場合もリストの要素の和になります。
f(x, y) = x + y の場合 reduce => a1 + a2 + a3 + a4 + a5
このように、reduce はリストのすべての要素を関数 f を用いて結合します。このような操作を「縮約」とか「畳み込み」といいます。また、reduce の引数に初期値 g を指定することがあります。この場合、reduce は下図に示す動作になります。
(1) (a1 a2 a3 a4 a5)
=> f( f( f( f( f( g, a1 ), a2 ), a3 ), a4 ), a5 )
(2) (a1 a2 a3 a4 a5)
=> f( a1, f( a2, f( a3, f( a4, f( a5, g ) ) ) ) )
図 : 関数 reduce の動作 (2)
ここでは簡単な例題として、上図 (1) の動作を行う関数 fold-left と、上図 (2) の動作を行う関数 fold-right を作ってみましょう。プログラムは次のようになります。
リスト : 畳み込み
(defun fold-left (fn a xs)
(if (null xs)
a
(fold-left fn (funcall fn a (car xs)) (cdr xs))))
(defun fold-right (fn a xs)
(if (null xs)
a
(funcall fn (car xs) (fold-right fn a (cdr xs)))))
第 1 引数 FN が適用する関数、第 2 引数 A が初期値、第 3 引数 XS がリストです。最初の if が再帰呼び出しの停止条件ですが、XS に空リストが与えられた場合にも対応します。この場合は初期値 A を返します。そして、次の else 節でリストの要素を取り出して関数 FN を呼び出します。
たとえば、リストが (1 2 3) で a が 0 とします。最初は (funcall fn 0 1) が実行され、その返り値が fold-left の第 2 引数に渡されます。次は (funcall fn a 2) が実行されますが、これは fn(fn(0, 1), 2) と同じことです。そして、その結果が fold-left の第 2 引数になります。最後に (funcall fn a 3) が実行されますが、これは fn(fn(fn(0, 1), 2), 3) となり、図 (1) と同じ動作になります。
fold-left の場合、リストの要素が関数 FN の第 2 引数になり、第 1 引数にはこれまでの処理結果が渡されます。これに対し、fold-right の場合は逆になり、関数 FN の第 1 引数にリストの要素が渡されて、これまでの処理結果は第 2 引数に渡されます。これで図 (2) の動作を実現することができます。
簡単な実行例を示します。
* (fold-left #'+ 0 '(1 2 3 4 5)) 15 * (fold-right #'+ 0 '(1 2 3 4 5)) 15
なお、Common Lisp には畳み込みを行う関数 reduce が用意されています。
●問題
次に示す関数を定義してください。
- s から e までの整数に関数 fn を適用し、その合計値を求める関数 sum-of fn e s
- s から e までの整数に関数 fn を適用し、その結果をリストに格納して返す関数 tabulate fn e s
- リスト xs の要素に関数 fn を適用するが、その結果を累積しない関数 foreach fn xs
- 関数 fn にリストを渡すマップ関数 my-maplist fn xs
- 述語 pred を満たす要素の個数を数える my-count-if pred xs
- 述語 pred を満たす最初の要素を返す my-find-if pred xs
- リスト xs を先頭から畳み込むとき、計算途中の累積値をリストに格納して返す scan-left fn a xs
- リスト xs を末尾から畳み込むとき、計算途中の累積値をリストに格納して返す scan-right fn a xs
- 2020/04/25 問題 7, 8 を追加
●解答１
リスト : 関数 fn を適用した結果の合計値を求める
(defun sum-of (fn s e)
(do ((n s (1+ n))
(a 0))
((> n e) a)
(incf a (funcall fn n))))
* (sum-of #'identity 1 10) 55 * (sum-of (lambda (x) (* x x)) 1 10) 385 * (sum-of (lambda (x) (* x x x)) 1 10) 3025
関数 identity は「恒等関数 (identity function)」といって、引数をそのまま返します。identity は関数なので、quote と違って引数を評価することに注意してください。
* (identity 100) 100 * (identity (+ 1 2)) 3 * (identity 'a) A
●解答２
リスト : 関数 fn を適用した結果をリストに格納して返す
(defun tabulate (fn s e)
(if (> s e)
nil
(cons (funcall fn s) (tabulate fn (1+ s) e))))
* (tabulate #'identity 1 10) (1 2 3 4 5 6 7 8 9 10) * (tabulate (lambda (x) (* x x)) 1 10) (1 4 9 16 25 36 49 64 81 100) * (tabulate (lambda (x) (* x x x)) 1 10) (1 8 27 64 125 216 343 512 729 1000)
●解答３
リスト : 関数 fn を適用するだけ (結果は捨てる) (defun foreach (fn xs) (dolist (x xs) (funcall fn x)))
* (foreach #'print '(a b c d e)) A B C D E NIL
Common Lisp には関数 foreach と同様の働きをする関数 mapc があります。
* (mapc #'print '(a b c d e)) A B C D E (A B C D E)
●解答４
Common Lisp には関数 maplist があるので、名前を my-maplist としました。
リスト : 関数 fn にリストを渡すマップ関数
(defun my-maplist (fn xs)
(if (null xs)
nil
(cons (funcall fn xs) (my-maplist fn (cdr xs)))))
my-maplist は関数 FN にリスト XS をそのまま渡します。そして、再帰呼び出しするとき XS に cdr を適用します。
* (my-maplist #'identity '(a b c d e)) ((A B C D E) (B C D E) (C D E) (D E) (E)) * (my-maplist #'length '(a b c d e)) (5 4 3 2 1) * (maplist #'identity '(a b c d e)) ((A B C D E) (B C D E) (C D E) (D E) (E))
●解答５
Common Lisp には関数 count-if があるので、名前を my-count-if としました。
リスト : 述語 pred を満たす要素をカウントする
(defun my-count-if (pred xs)
(let ((c 0))
(dolist (x xs c)
(if (funcall pred x) (incf c)))))
* (my-count-if #'evenp '(1 2 3 4 5)) 2 * (my-count-if #'oddp '(1 2 3 4 5)) 3
●解答６
Common Lisp には関数 find-if があるので、名前を my-find-if としました。
リスト : 述語 pred を満たす最初の要素を返す
(defun my-find-if (pred xs)
(dolist (x xs)
(if (funcall pred x) (return x))))
* (my-find-if #'symbolp '(1 2 3 a b c)) A * (my-find-if #'stringp '(1 2 3 a b c)) NIL
●解答７
リスト : 累積値リストの生成 (1)
(defun scan-left (fn a xs)
(if (null xs)
(list a)
(cons a (scan-left fn (funcall fn (car xs) a) (cdr xs)))))
;;; 別解
(defun scan-left1 (fn a xs)
(nreverse (fold-left (lambda (a x) (cons (funcall fn x (car a)) a)) (list a) xs)))
* (scan-left #'+ 0 '(1 2 3 4 5 6 7 8 9 10)) (0 1 3 6 10 15 21 28 36 45 55) * (scan-left #'cons nil '(1 2 3 4 5)) (NIL (1) (2 1) (3 2 1) (4 3 2 1) (5 4 3 2 1)) * (scan-left #'* 1 '(1 2 3 4 5 6 7 8 9 10)) (1 1 2 6 24 120 720 5040 40320 362880 3628800)
scan-left はリストの最後の要素が最終の累積値になります。xs が空リストのとき、累積変数 a の値をリストに格納して返します。そうでなければ、scan-left を再帰呼び出しして、その返り値に累積変数 a の値を追加して返します。scan-left を再帰呼び出しするときは、関数 fn を呼び出して累積変数の値を更新することに注意してください。別解は fold-left を使ったバージョンです。返り値のリストは逆順になるので、nreverse で反転しています。
●解答８
リスト : 累積値リストの生成 (2)
(defun scan-right (fn a xs)
(if (null xs)
(list a)
(let ((ys (scan-right fn a (cdr xs))))
(cons (funcall fn (car xs) (car ys)) ys))))
;;; 別解
(defun scan-right1 (fn a xs)
(fold-right (lambda (x a) (cons (funcall fn x (car a)) a)) (list a) xs))
* (scan-right #'+ 0 '(1 2 3 4 5 6 7 8 9 10)) (55 54 52 49 45 40 34 27 19 10 0) * (scan-right #'cons nil '(1 2 3 4 5)) ((1 2 3 4 5) (2 3 4 5) (3 4 5) (4 5) (5) NIL)
scan-right はリストの先頭の要素が最終の累積値、最後の要素が初期値になります。リスト xs が空リストの場合は (list a) を返します。そうでなければ、scan-right を再帰呼び出しします。このとき、累積変数 a の値は更新しません。返り値のリストは変数 ys にセットします。この ys の先頭要素が一つ前の累積値になるので、この値と xs の要素を関数 fn に渡して評価します。あとは、fn の返り値を ys の先頭に追加して返せばいいわけです。別解は畳み込み fold-right を使ったバージョンです。