関数型プログラミング事始め (30) 高階関数(3)

関数型プログラミングがはじめての方へ贈る入門の書
前節：高階関数(2)　次節：未公開
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)

高階関数も再帰関数と同様に、慣れが必要です。逆に言えば、慣れれば大丈夫です。ここでは高階関数に慣れるためにいくつかの演習をしていきます。

(3) 高階関数の演習

高階関数も再帰関数と同様に少しの慣れが必要です。でも安心してください。再帰プログラミングは繰り返しプログラミングからのパラダイムシフトが必要なため大変ですが、高階関数はそれほどではありません。安心してください。少しの慣れだけで高階関数を使えます。そこでここでは高階関数に慣れるためにいくつかの演習をしていきます。

ここではOK! ISLispを使って高階関数を学んでいきます。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。

> ISLisp Version 0.80 (1999/02/25)
>
ISLisp>

(a) 関数合成

まず高階関数の簡単な演習として、関数合成を作ってみましょう。関数合成とは複数の関数を合成した関数を作るものです。

たとえば、carとcdrを合成すれば、リストの2番目の要素を取り出すcadrを作れます。(car (cdr '(1 2 3))が2を返しますが、合成した(cadr '(1 2 3))も2を返します。

2個の関数を合成するcomposeを作ってみます。なお例外処理は省いています。

ISLisp>(defun compose (f g) (lambda (x) (funcall f (funcall g x))))
COMPOSE
ISLisp>(funcall (compose #'car #'cdr) '(1 2 3))
2
ISLisp>(defglobal cadr (compose #'car #'cdr))
CADR
ISLisp>(funcall cadr '(1 2 3))
2

(lambda (x) (funcall f (funcall g x)))では引数の関数fと関数gを合成した関数を生成します。(lambda (x) …)は1引数xの匿名関数を返します。このようにlambdaはラムダ式によって匿名関数（無名関数）を構成するものですが、このラムダ式の詳細は後日紹介するようにします。

(compose #'car #'cdr)はcarとcdrを合成して、(car (cdr x))と同じ働きをする関数を返します。この合成関数をfuncallで呼び出しして、その引数(1 2 3)の2番目の要素2を返します。

(defglobal cadr (compose #'car #'cdr))ではグローバル変数cadrに合成関数を設定します。これを(funcall cadr '(1 2 3))で呼び出しています。

(b) カリー化

カリー化(currying)とは、2引数以上の多変数関数を1引数関数に変換することです。なおこのカリー化は後日紹介するラムダ式での基本的な変換です。

ISLisp>(defun add (x y) (+ x y))
ADD
ISLisp>(add 1 2)
3
ISLisp>(defun add1 (x) (lambda (y) (add x y)))
ADD1
ISLisp>(add1 1)
#<UFUNCTION 0026E836: #<LAMBDA>>
ISLisp>(funcall (add1 1) 2)
3

(defun add (x y) (+ x y))でADD2引数関数addを定義します。(add 1 2)は3を返します。これを1引数関数add1で定義してみます。
(lambda (y) (add x y))は引数yで(add x y)を実行する匿名関数を返します。(add1 1)では引数と1を加算する関数#<UFUNCTION 0026E836: #<LAMBDA>>を返します。
(funcall (add1 1) 2)では上記の(add1 1)の関数に引数2を渡して、引数2と1を加算する関数を実行し、結果として3を返します。

(c) クイックソート

再帰プログラミングの演習で登場したクイックソートでは、比較関数は<の固定でした。このため、昇順のソート固定になっていました。この比較関数を引数で渡すことにして、任意のソートをできるようにします。

ISLisp>
(defun qsort (test list)
    (if (null list)
        list
        (qsort2 test (car list) (cdr list) nil nil) ))
QSORT
ISLisp>
(defun qsort2 (test p list left right)
    (if (null list)
        (append (qsort test left) (cons p (qsort test right)) )
        (if (funcall test (car list) p)
            (qsort2 test p (cdr list) (cons (car list) left) right)
            (qsort2 test p (cdr list) left (cons (car list) right)) )))
QSORT2
ISLisp>(qsort #'< '(2 1 3 5 4))
(1 2 3 4 5)
ISLisp>(qsort #'> '(2 1 3 5 4))
(5 4 3 2 1)

再帰プログラミングの演習で紹介したクイックソートと比べると、(< (car list) p)としていた箇所を今回の高階関数版では(funcall test (car list) p)にしただけです。比較関数<を引数の関数testをfuncallで動的に呼び出すだけの簡単なお仕事です。

このクイックソートでは比較関数を動的に変更できるようにしましたが、たとえば比較する場所を動的に変更できるようにすることも可能です。

なおCommon Lispでは多くの関数で、キーワード引数:testで比較関数を動的に設定することができます。つまり手動で高階関数を作る必要がなく、ただそれを便利に使うだけです。なおCommon Lispの関数sortでは第2引数に比較関数を設定するようになっています。なおISLispには:testはありません。

このように高階関数への変換は簡単のように見えますが、これには高階関数にする対象の関数を特定化して、1ヵ所に集中させているところがポイントです。これがコツです。

(d) 高階関数の実行速度と了解性

以上、高階関数について紹介してきました。高階関数は動的な抽象的なプログラミングをするときの基本的な手法です。このためには前述のコツを覚えていてください。これがプログラムを読みやすくする効果もあります。

しかし高階関数は動的なプログラムなので、コンパイル時に静的には呼び出す関数を特定化できません。静的な関数呼び出しではコンパイラによる各種の高速化が行えますが、高階関数の動的プログラミングではそれが行えません。このため、高階関数はここぞというところだけで使いようにします。あまりにも抽象的な動的なプログラミングは実行を遅くするということを覚えておいてください。

高階関数の使用でプログラムの了解性も少し悪くします。例えばクイックソートを動的な比較関数呼び出しにすることで、ほんのわずか悪くします。感覚的に言えば、１つの関数で１つの高階関数の使用であれば問題ないと思います（が2個以上の使用は注意してください）。

動的プログラミングの便利さと比較して、これらのトレードオフを考えてプログラミングしてください。

ということでここでの結論「高階関数は1個まで」です。

(予告) 3.3 遅延評価

次回は高階関数の適用のひとつとして、遅延評価を見ていくことにします。お楽しみに！