関数型プログラミング事始め (29) 高階関数(2)
関数型プログラミングがはじめての方へ贈る入門の書
前節：高階関数(1) 次節：高階関数(3)
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)
(2) 高階関数のライブラリ
高階関数は前節で紹介したように、動的なプログラミングができる便利なものです。しかし慣れないとこの高階関数は難しいものです。
一方、高階関数の使い方は同じような使われ方をしてパターン化してきます。そこで多くの関数型プログラミング言語では高階関数のライブラリが用意されています。この関数ライブラリを使うだけで、高階関数の動的プログラミングができるようになり、大きな効果があります。今回はこのライブラリを見ていきます。
ここではOK! ISLispを使って関数型プログラミングの手習いをやっていきます。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。
> ISLisp Version 0.80 (1999/02/25)
>
ISLisp>
(a) map関数
引数の関数をリストの要素に適用するmap関数の高階関数ライブラリがあります。以下に例を示します。
ISLisp>(mapcar #'+ '(1 2 3) '(4 5 6))
(5 7 9)
ISLisp>(mapcan #'list '(1 2 3) '(4 5 6))
(1 4 2 5 3 6)
ISLisp>(maplist #'list '(1 2 3))
(((1 2 3)) ((2 3)) ((3)))
ISLisp>(defun println (x) (format (standard-output) "~s~%" x) x)
PRINTLN
ISLisp>(mapc #'println '(1 2 3))
1
2
3
(1 2 3)
ISLisp>(mapl #'println '(1 2 3))
(1 2 3)
(2 3)
(3)
(1 2 3)
(mapcar #'+ '(1 2 3) '(4 5 6))は引数のリスト(1 2 3)と(4 5 6)の各要素に関数+を適用して(+ 1 4)、(+ 2 5)、(+ 3 6)の結果をリスト(5 7 9)にして返します。
(mapcan #'list '(1 2 3) '(4 5 6))は関数listを適用して(list 1 4)、(list 2 5)、(list 3 6)の結果を連結したリスト(1 4 2 5 3 6)を返します。
(maplist #'list '(1 2 3))は引数のリストのサブリスト(1 2 3)、(2 3)、(3)に関数listを適用して(list '(1 2 3))、(list '(2 3))、(list '(3))の結果をリストにして返します。
mapcとmaplは結果を蓄積せずに関数実行の副作用をする関数になります。副作用しかしないため、改行付き印字関数のprintln (print with line feed)を定義して、印字の副作用を画面表示するようにしています。
(mapc #'println '(1 2 3))は結果をリストに蓄積しないmapcarです。引数の(1 2 3)の各要素に対して、関数printlnを適用して、1, 2, 3を印字します。なおmapcの値は引数のリストを返します。(mapl #'println '(1 2 3))は結果を蓄積しないmaplistです。
(b) reduce関数
reduceは畳み込み関数と呼ばれる関数で、(reduce #'+ '(1 2 3 4))が(+ (+ (+ 1 2) 3) 4)となる関数です。
なおISLispにはreduceは存在しませんので、（例外処理を手抜きし、かつreduceの引数を1個に限定した簡易）reduce関数を定義してみます。
ISLisp>
(defun reduce (fun list) (reduce2 fun (car list) (cdr list)))
REDUCE
ISLisp>
(defun reduce2 (fun head list)
(let ((ret (funcall fun head (car list))))
(if (null (cdr list))
ret
(reduce2 fun ret (cdr list)) )))
REDUCE2
ISLisp>(reduce #'+ '(1 2 3 4))
10
ISLisp>(reduce #'- '(1 2 3 4))
-8
(reduce #'+ '(1 2 3 4))は(+ (+ (+ 1 2) 3) 4)のように実行し、結果として10を返します。(reduce #'- '(1 2 3 4))は(- (- (- 1 2) 3) 4)のように実行し、結果として-8を返します。
（注意）なおローカル変数retを使っているのは、(funcall fun head (car list))のプログラムコードの重複をなくすためだけであり、副作用は生じていませんのでご安心ください。このようなときは関数型プログラミングでもローカル変数を気にせずに使ってください。
なお以下のプログラムではローカル変数を使っていません。
(defun reduce2 (fun head list)
(if (null (cdr list))
(funcall fun head (car list))
(reduce2 fun (funcall fun head (car list)) (cdr list)))))
(c) 高階関数ライブラリ虎の巻
高階関数ライブラリとしてmap関数とreduce関数を見てきました。mapとreduceはペアで紹介されることが多いのですが、実際はreduce関数はあまり使う機会が少なく、一方map関数は使い手があります。つまりmap関数だけで十分です。きっと。
map関数は結果をどのように蓄積するか、または蓄積しないかで、色々なバリエーションがあります。でも一番多く使うのはmapcarです。mapcarは引数リストの各要素を取り出して関数を適用し、結果をリストで返すという「自然」な動きをします。
はっきり言いましょう。mapcarで十分です。まずはmapcarの適用を考え、少し不便さを感じたり、もっと効率の良い方法があるのではと思ったときに、バリエーションを探してみてください。もしかしたらreduce関数の登場かもしれません。
ということでここでの結論「mapcarで十分」です。
(予告) (3) 高階関数の演習
次回は高階関数の演習として、関数合成やクイックソートを見ていくことにします。お楽しみに！
いいなと思ったら応援しよう！
