高階関数の利用
前章までで，mapやfilterといった，リスト構造を中心としたいくつかの処理パターンを見てきました．ラムダ式などの関数定義を引数の値としてとる関数定義を高階関数と呼びますが，上記の処理パターンは，引数に実際の処理の一部を指定するという意味で，高階関数の特徴を最も活用しているといえます[1]．実用面では，mapやfilter，assoc相当がよく使われる一方，他の有用な関数処理を定義できる高階関数という意味では，畳み込み処理foldや逆畳み込み処理unfoldが有用です．
ここでは，便宜上fpLISPに組み込んだ高階関数である，foldとunfoldの活用について解説します．注意してほしいのは，定義の幅を広げることができるといった都合から，先の章で示したそれぞれのラムダ式とは，引数の扱いや処理の順番などが若干異なることです．
畳み込み関数fold
fpLISPに組み込まれたfoldは，初期値iに対してリストaの先頭要素を左から関数適用します．また，初期値iは，適用する関数fの直後に置きます．
(fold f i a)
たとえば，
(fold (lambda (acc x) (cons acc x)) nil (quote (10 20 30 40 50)))
は，実際には次の処理に置き換わります．
(cons (cons (cons (cons (cons nil 10) 20) 30) 40) 50)
=> (((((nil . 10) . 20) . 30) . 40) . 50)
処理の流れを順番に見ていくと，まず，ラムダ式の引数accが初期値nilに，引数xがリスト(10 20 30 40 50)の先頭要素10にそれぞれ置き換わります．
acc = nil, x = 10
そして，ラムダ式の本体である(cons acc x)によって(nil . 10)となり，accがそれに置き換わります．一方，xはリストの次の先頭要素20に置き換わります．
acc = (nil . 10), x = 20
以降，リストが空になるまで同じ処理が繰り返されます．結果として，引数accに処理結果が累積されていくことになります．
acc = ((nil . 10) . 20), x = 30
acc = (((nil . 10) . 20) . 30), x = 40
acc = ((((nil . 10) . 20) . 30) . 40), x = 50
acc = (((((nil . 10) . 20) . 30) . 40) . 50), x = nil
したがって，たとえばラムダ式の本体を(cons x acc)に変更すると，次のような結果となります．
(fold (lambda (acc x) (cons x acc)) nil (quote (10 20 30 40 50)))
acc = nil, x = 10
acc = (10 . nil), x = 20
acc = (20 . (10 . nil)), x = 30
acc = (30 . (20 . (10 . nil))), x = 40
acc = (40 . (30 . (20 . (10 . nil)))), x = 50
acc = (50 . (40 . (30 . (20 . (10 . nil))))), x = nil
=> (50 40 30 20 10)
これは，リスト要素を逆順にする処理reverseに相当します．
前章までで登場したリスト処理のいくつかは，foldのみで表現可能です．上記のreverse相当を含め，記述例と処理名を一覧にすると次のようになります．なお，consを用いた累積処理は結果のリスト要素が逆順となってしまうため，必要に応じてreverse処理を併用しています．
- リストの要素を逆順にする（reverse）
(fold (lambda (acc x) (cons x acc)) nil (quote (a b c d e)))
(e d c b a)
- ふたつのリストの要素を結合する（append）
(fold (lambda (acc x) (cons x acc))
(quote (x y z))
(fold (lambda (acc x) (cons x acc)) nil
(quote (a b c))))
(a b c x y z)
- リストの各要素に同じ関数を適用する（map）
(fold (lambda (acc x) (cons x acc)) nil
(fold (lambda (acc x) (cons (* x x) acc)) nil
(quote (1 2 3 4 5))))
(1 4 9 16 25)
- リストから条件に沿った要素のみを取り出す（filter）
(fold (lambda (acc x) (cons x acc)) nil
(fold (lambda (acc x) (if (eq (% x 2) 1) (cons x acc) acc)) nil
(quote (1 2 3 4 5))))
(1 3 5)
- リストの要素数を返す（length）
(fold (lambda (acc x) (+ acc 1)) 0 (quote (a b c d e)))
5
- リスト要素の数値の合計を返す（sum）
(fold (lambda (acc x) (+ acc x)) 0 (quote (1 2 3 4 5)))
15
- 同じ位置にある各要素に関数規則を適用する（ふたつのリストの版のmap）
※fpLISPのfoldはリストをふたつ指定することが可能です．
(fold (lambda (acc x) (cons x acc)) nil
(fold (lambda (acc x y) (cons (- x y) acc)) nil
(quote (10 20 30 40 50)) (quote (1 2 3 4 5))))
(9 18 27 36 45)
(fold (lambda (acc x) (cons x acc)) nil
(fold (lambda (acc x y) (cons (cons x y) acc)) nil
(quote (a b c d e)) (quote (1 2 3 4 5))))
((a . 1) (b . 2) (c . 3) (d . 4) (e . 5))
逆畳み込み関数unfold
fpLISPに組み込まれたunfoldは，初期値seedに対して指定したラムダ式fを次々と適用していき，適用結果が偽となるまで続けた結果をリストとして返すリスト生成関数です．ただし，偽ではなかった時の適用結果は，(cons 次の値を生成する処理 リストに追加する時の処理)という構成とする必要があり，また，値の追加はリストの先頭に行われていきます．更に，リストの初期値はnilですが，この初期値は指定可能です．
(unfold f seed i) ※リストの初期値iは省略可能
たとえば，
(unfold (lambda (x) (if (lt x 0) nil (cons (- x 1) x))) 9)
の結果は次の通りです．
(0 1 2 3 4 5 6 7 8 9)
こちらも処理の流れを順番に見ていきます．まず，ラムダ式の引数xが初期値9に置き換わり，(lt x 0)（(cons (- x 1) x)の処理が行われます．consの左側8はxの次の値となり，右側9は最初のリスト要素となります．
(cons 8 9) => x = 8, リスト = (9)
次のラムダ式適用でも依然(lt x 0)（$x<0）が偽であり，(cons (- x 1) x)の処理が行われるため，xの次の値は7，リストの先頭には8が追加されます．
(cons 7 8) => x = 7, リスト = (8 9)
同様の処理がunfoldの式は，初期値9から値を1ずつ減らして0より小さくなるまで，値をリストの先頭に追加していく処理となります．
(cons 6 7) => x = 6, リスト = (7 8 9)
(cons 5 6) => x = 5, リスト = (6 7 8 9)
(cons 4 5) => x = 4, リスト = (5 6 7 8 9)
(cons 3 4) => x = 3, リスト = (4 5 6 7 8 9)
(cons 2 3) => x = 2, リスト = (3 4 5 6 7 8 9)
(cons 1 2) => x = 1, リスト = (2 4 5 6 7 8 9)
(cons 0 1) => x = 0, リスト = (1 2 4 5 6 7 8 9)
(cons -1 0) => x = -1, リスト = (0 1 2 4 5 6 7 8 9)
以下に，unfoldを用いたリスト生成処理の例をいくつか一覧として示します．なお，一部のfoldの例と同じく，必要に応じてreverse処理を併用しています．
- リストの要素を逆順にする（reverse）
(unfold (lambda (x) (if (eq x nil) nil (cons (cdr x) (car x))))
(quote (a b c d e)))
(e d c b a)
- 等差数列を生成する（range）
(unfold (lambda (x) (if (eq x nil) nil (cons (cdr x) (car x))))
(unfold (lambda (x) (if (lt 20 x) nil (cons (+ x 3) x))) 0))
(0 3 6 9 12 15 18)
- 1以上の十進数の整数を二進数のリストに変換する
(unfold (lambda (x) (if (eq x 0) nil (cons (/ x 2) (% x 2))))
18)
(1 0 0 1 0)
- 1000未満の値までのフィボナッチ数列を生成する
(unfold (lambda (x) (if (eq x nil) nil (cons (cdr x) (car x))))
(unfold (lambda (x)
(if (lt 1000 (car x)) nil
(cons (cons (cdr x) (+ (car x) (cdr x)))
(car x))))
(cons 0 1)))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987)
遅延評価とストリーム
遅延評価の考え方
foldは，指定したリストの要素を全て処理した結果を求めます．また，unfoldは，指定したラムダ式が終了を判定するまで要素を繰り返し生成し，その結果を全てリストとします．ここで，必要な要素に対する処理のみ行わせるには，どのようにしたらよいでしょうか？
たとえば，次はfoldを用いた連結リストに対するfilter処理の例です．assoc処理と似ていますが，連結リストのうち，キーが2に一致したペアの値を全てcdrで求め，リストとしています．ただし，結果の値は逆順となります．
(fold (lambda (acc x) (if (eq (car x) 2) (cons (cdr x) acc) acc))
nil
(quote ((1 . a) (2 . b) (3 . c) (2 . d) (2 . e))))
(e d b)
ここで，結果のリストの2番目であるdのみ欲しい場合は，とりあえず(car (cdr ...))で括れば取り出すことが可能です．ですが，元の連結リストの該当するペア全てにcdrを行ってリストを生成した後，2番目の要素のみを取り出すのですから，余分なcdr処理が行われることになります[2]．
(car (cdr
(fold (lambda (acc x) (if (eq (car x) 2) (cons (cdr x) acc) acc))
nil
(quote ((1 . a) (2 . b) (3 . c) (2 . d) (2 . e))))))
((1 . a) (2 . b) (3 . c) (2 . d) (2 . e))
=> ((2 . e) (2 . d) (2 . b))
=> (e d b)
=> d
d
必要なのは，2番目の該当ペアのcdr処理のみですから，それ以外の該当するペアのcdr処理は行わなくても良いようにしたいところです．そこで，該当のペアのリストを取り出してから2番目のペアを取り出し，そのペアに対してcdrを行うことにします．
(cdr
(car (cdr
(fold (lambda (acc x) (if (eq (car x) 2) (cons x acc) acc))
nil
(quote ((1 . a) (2 . b) (3 . c) (2 . d) (2 . e)))))))
((1 . a) (2 . b) (3 . c) (2 . d) (2 . e))
=> ((2 . e) (2 . d) (2 . b))
=> (2 . d)
=> d
d
これで，一応は目的を達成できます．ここで，この遅延させたcdr処理の記述を，foldに指定したラムダ式の中に留めたままとできるならば，どのような処理を遅延させたかがわかりやすくなります．具体的には，次のように記述できれば良いことになります．
(遅延させた処理の実行
(car (cdr
(fold (lambda (acc x) (if (eq (car x) 2)
(cons (処理の遅延 (cdr x)) acc)
acc))
nil
(quote ((1 . a) (2 . b) (3 . c) (2 . d) (2 . e)))))))
実のところ，これまで使用してきたラムダ式を用いれば，この処理の遅延と必要な時の実行を行わせることが可能です．といいますのも，ラムダ式は引数変数に具体的な値を指定するまでは，本体の関数処理を実行することがないためです．これは，引数変数のないラムダ式でも同様です．fpLISPの場合の具体的な例は次の通りです．
(lambda () (+ 12 13))
(lambda nil (+ 12 13) nil)
()はnilに置き換わり，関数本体の後にもnilが入ります．後者のnilは，このラムダ式が独自にもつ環境の初期値で，変数と値の対応を格納しておく領域です．ラムダ式本体と併せてクロージャと呼ばれており，fpLISPでは，変数と値の対応は連想リストで構成されています[3]．
このように，本体にどのような関数規則が記述されていても，ラムダ式を評価しただけでは，環境を初期化したラムダ式が返ってくるのみです．このラムダ式の本体をあらためて実行（評価）するには，そのラムダ式を関数定義として呼び出せば良いのですが，上記は引数変数がないため，括弧で囲むだけで実行されます．
((lambda () (+ 12 13)))
25
つまり，処理の遅延は引数変数なしのラムダ式で囲み，遅延させた処理の実行は括弧で囲むだけで良いことになります．
((car (cdr
(fold (lambda (acc x) (if (eq (car x) 2)
(cons (lambda () (cdr x)) acc)
acc))
nil
(quote ((1 . a) (2 . b) (3 . c) (2 . d) (2 . e)))))))
d
このような，実際に必要になるまで実行（評価）が行われないようにする仕組みは，遅延評価と呼ばれます．ここで，本当にcdr処理が遅延しているかを見るため，括弧で囲む部分を外してみます．
(car (cdr
(fold (lambda (acc x) (if (eq (car x) 2)
(cons (lambda () (cdr x)) acc)
acc))
nil
(quote ((1 . a) (2 . b) (3 . c) (2 . d) (2 . e))))))
(lambda nil (cdr x) ((acc (lambda nil (cdr x) ((acc) (x 2 . b)))) (x 2 . d)))
わかりにくいですが，((acc ...の部分はラムダ式の環境部分で，変数と値の対応が連想リストで表示されています．この対応のうち，ラムダ式本体で参照されているのはxのみですので，括弧で囲んで遅延した処理を実行しようとすると，xに対応する(2 . d)が(cdr x)のxに渡され，処理結果としてdが返ります．
遅延ストリームの活用
前節の遅延評価の例は，foldで指定するラムダ式の内部で必要な遅延を発生させることができました．一方，リストを生成するunfoldで似たようなことを行う，すなわち，リスト要素の生成そのものを遅延させるには，unfoldの処理内部で遅延処理を行う必要があります．特に，生成されるリストの要素を先頭から必要な数だけ遅延評価させることで取得できれば，要素生成の停止条件を記述する必要もなくなります．
このような処理を行う高階関数は，第四章で登場したunfoldの定義例である
(((lambda (u) (u u))
(lambda (u)
(lambda (f x)
((lambda (r)
(if (eq r nil) nil
(cons (car r) ((u u) f (cdr r)))))
(f x)))))
(lambda (x) (if (lt 10 x) nil (cons (* x x) (+ x 1))))
0)
(0 1 4 9 16 25 36 49 64 81 100)
を修正して記述すると，次のようになります．
(car ((cdr ((cdr
(((lambda (u) (u u))
(lambda (u)
(lambda (f x)
((lambda (r)
(cons (car r) (lambda () ((u u) f (cdr r)))))
(f x)))))
(lambda (x) (cons (* x x) (+ x 1)))
0)
)))))
4
終了判定をなくす代わりに，次の要素を求める処理((u u) f (cdr r))を引数変数なしのラムダ式で囲んで遅延させています．ここでは，遅延させたリスト生成に対してcdrと遅延処理実行((cdr ...))を2回行った後に先頭要素を取り出しているため，3番目の生成要素4が出力されています．
このような処理は大変有用であるため，fpLISPでは，遅延させたリスト処理を生成する高階関数unfold-stream，遅延させたリスト処理に対して指定した要素数を先頭から取り出す高階関数take-streamを組み込んでいます．次は，これらの組込関数の利用例です．unfold-streamで指定するラムダ式の本体が，組込関数unfoldと異なり，(cons リストに追加する時の処理 次の値を生成する処理)となっていることに注意して下さい[4]．
(take-stream (unfold-stream (lambda (x) (cons x (+ x 2))) 0) 9)
(0 2 4 6 8 10 12 14 16)
(take-stream
(unfold-stream
(lambda (x) (cons (car x) (cons (cdr x) (+ (car x) (cdr x)))))
(cons 0 1))
18)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597)
なお，一連の要素をもった生成リストはストリームと呼ばれ，遅延評価が可能なストリームは遅延ストリームと呼ばれています．
練習問題
次のfold，unfoldを用いた記述がどのような評価結果となるかを実行前に予想し，予想通りとなるかを確認して下さい．
(fold - 0 (quote (1 2 3 4 5)))
(car (cdr (cdr
(unfold (lambda (x) (if (lt 100 x) nil (cons (* x 2) (lambda () x)))) 9)
)))
(take-stream (unfold-stream (lambda (x) (cons x (- x 1))) 5) 10)
-
ラムダ式の章で述べました『関数出力としてラムダ式を返す』ことができることも，高階関数の機能のひとつです． ↩︎
-
プログラムコードの直後にある処理手順の表現は正確ではなく，実際には，該当する3つのペアに
cdr処理を行った結果を順次リストに追加していくことで(e d b)を生成しています． ↩︎ -
多くのLISP系言語では，ラムダ式の環境がこのように直接表示されることはありません ↩︎
-
他のプログラミング言語で同様の仕組みを提供する関数の仕様に合わせています． ↩︎