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

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

高階関数は引数や値に関数を使う関数です。関数を引数にすることで、高階関数の中でその引数関数を動的に実行できます。また高階関数の値として関数を返し、その値関数を動的に実行できます。このような動的プログラミングができます。しかし高階関数は使いにくいものです。プログラミングでもそうですが、デバッグのときはさらに面倒です。そこで言語仕様として用意されている高階関数のライブラリ関数があります。高階関数は使うパターンが比較的決まっています。それをライブラリにした関数が用意されていますので、このライブラリ関数を使うのいいでしょう。

3.2 高階関数

高階関数は引数や値に関数を使う関数です。関数の引数や値に高階関数でない普通の関数を使う高階関数は2階関数と呼ばれます。関数の引数や値に2階関数を使うときは3階関数になります。このように関数の階数を高くすることができます。逆に関数の引数や値に関数を使わない普通の関数は1階関数と呼びます。

ここではOK! ISLispを使って関数型プログラミングの手習いをやっていきます。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。

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

(1) はじめての高階関数

最初に高階関数の例として、引数に関数を渡して、その関数を実行するだけの例を見ていきます。

ISLisp>(defun add (x y) (+ x y))
ADD
ISLisp>(defun sub (x y) (- x y))
SUB
ISLisp>(defun call (fun x y) (funcall fun x y))
CALL
ISLisp>(call #'add 1 2)
3
ISLisp>(call #'sub 1 2)
-1

まず関数の引数に渡す関数として、addとsubを定義します。そして高階関数の一番簡単な例としてcallを定義します。このcallは単に引数の関数funを実行するだけの関数になります。

(call #'add 1 2)を実行すると、callの本体で(funcall #'add 1 2)を実行し、結果の3を返します。同様に(call #'sub 1 2)を実行すると-1を返します。また(call #'+ 1 2)や(call #'- 1 2)のようにシステム関数を渡すことも同様にできます。

次に実用的な関数として、全数検索の関数findsを作ってみます。全数検索は浅い検索で検索関数が真になる要素をすべて取り出す関数です。

ISLisp>
(defun finds (fun key list)
    (if (null list)
        nil
        (append
            (if (funcall fun key (car list))
                (list (car list)) )
            (finds fun key (cdr list)) ) ))
FINDS
ISLisp>(finds #'= 2 '(1 2 3 2 1))
(2 2)
ISLisp>(finds #'< 2 '(1 2 3 4 5))
(3 4 5)

関数findsは引数に検索関数funと検索キーkey、検索対象listをセットし、listの要素を順に検索関数とキーで(funcall fun key (car list))のように検索し、真となったときはlistの要素(car list)をappendで蓄えて返す関数です。なお次の要素検索は(finds fun key (cdr list))のように再帰呼び出しで実装しています。

(finds #'= 2 '(1 2 3 2 1))の実行では、最初に(= 2 (car '(1 2 3 2 1))を実行し、順次(1 2 3 2 1)の要素を検索して、(2 2)を返します。同様に(finds #'< 2 '(1 2 3 4 5))は2より大きい要素を検索し、(3 4 5)を返します。

この高階関数版の全数検索を、固定化された1階の検索関数で作ってみます。

ISLisp>
(defun find= (key list)
     (if (null list)
          nil
         (append
            (if (= key (car list)) (list (car list)) )
        (find= key (cdr list)) ) ))
FIND=
ISLisp>(find= 2 '(1 2 3 2 1))
(2 2)

関数find=とfindsは、(= key (car list))と(funcall fun key (car list))が違うだけです。つまり1階の固定化された検索関数=をfuncall funのようにしたものが高階関数のfindsです。

プログラムに大きな差異はありません。固定化された検索関数を引数の関数を実行するプログラムに変えるだけです。この意味では高階関数は恐れる必要はありません。たぶん。

でも一般的には高階関数は作成が面倒になります。それこそ平屋建ての住宅から2階建ての住宅になるようなものです。高さの次元が増えて面倒で、階段の上り下りで疲れます。

そこで言語仕様で用意されている高階関数のライブラリを使うことにします。手作りする必要はあまりありません。きっと。

ということでここでの結論「高階関数、恐れるに足りず」です。

(予告) (2) 高階関数のライブラリ

次回は高階関数のライブラリ関数を見ていくことにします。お楽しみに！