前章では，関数を引数として渡せることが抽象化への可能性をどれ程大きくするかを見た． 関数に対して行える操作が豊かな程，その可能性を深く利用できる． 新しい関数を生成して返す関数を定義することで， 関数を引数に取るユーティリティの効果を増幅できる．
この章で示すユーティリティは関数に対して動作する． 多くのユーティリティを式に対して動作するように書く方が（少なくともCommon Lispでは）自然だろう． つまり，マクロとして書くのだ． 第15章では，これらのオペレータの幾つかにマクロの層が挿入される． しかしそれらの関数が結局はマクロを通じてのみ呼び出されるとしても， 機能のどの部分が関数で実現できるのかを知ることは重要なことだ．
Common Lispには元々コンプリメント関数(complement function)の対が幾つかある．
関数remove-ifと
remove-if-notもそういった対の一つだ．
predが引数を1個取る述語だとすると
(remove-if-not #'pred lst)
と
(remove-if #'(lambda (x) (not (pred x))) lst)
とは等価だ．
引数として渡された関数をそうした関数に変えることで，もう片方の機能を複製できる．
そのとき，どうして両方の必要があるだろう？
CLtL2はそのような状況を意図した関数を新しく含んでいる：
complementは述語pを取り，常に反対の値を返す関数を返す．
pが真を返すとき，コンプリメント関数は偽を返す．逆も同じだ．
するとcomplementを使えば
(remove-if-not #'pred lst)
は等価な
(remove-if (complement #'pred) lst)
で置き換えられる．
-if-notの類の関数を使い続けることを正当化する理由はほとんどない
\footnote{remove-if-notは別だろう．
これはremove-ifよりも使われている．}．
実際CLtL2 (p. 391) は，それらの使用は現在では推奨されないと記している．
それらがCommon Lispに残されるとしたら，その理由は互換性を保つために過ぎないだろう．
新しいオペレータcomplementは重要な主題
---関数を返す関数--- の氷山の一角だ．
それはSchemeの慣用法の中では長らく重要な位置を占めていた．
Schemeは関数をレキシカルクロージャにした最初のLispで，
返り値に関数を使うことを興味深いものにしたのもそれだ．
ダイナミックスコープのLispでは関数を返せない訳ではない． 次の関数はダイナミックスコープのLispでもレキシカルスコープのLispでも 同じように動作するだろう：
(defun joiner (obj)
(typecase obj
(cons #'append)
(number #'+)))
これはオブジェクトを引数に取り， その型に応じてそれらのオブジェクトを加え合わせる関数を返す． これは数やリストに対して働く多態的な(polymorphic)連結関数の定義に使える：
(defun join (&rest args) (apply (joiner (car args)) args))
しかし予め決めた中から選んで関数を返す程度が，
ダイナミックスコープの下でできることの限界だ．
実行時に関数を生成することは（上手には）できない．
joinerは2個の関数の中どちらかを返せるが，返せる2個は固定されている．
これとは別にpropページで関数を返す関数を見た． それはレキシカルスコープによるものだ：
(defun make-adder (n) #'(lambda (x) (+ x n)))
make-adderを呼ぶとクロージャが生成されるが，
その振る舞いは元々引数として与えられた値に依存する．
> (setq add3 (make-adder 3)) #<Interpreted-Function BF1356> > (funcall add3 2) 5
レキシカルスコープの下では，選択肢の中からどれかの関数を選ぶだけでなく，
実行時にクロージャを生成することができる．
ダイナミックスコープの下ではその技法は不可能だ
\footnote{ダイナミックスコープの下でもmake-adderのようなものを作れるが，
それはまともに動作しないだろう．
返された関数が最終的に呼び出された環境にnの束縛が左右され，
制御することはできないだろう．}．
complementがどのように書かれているかを考えれば，
それがクロージャを返す他ないということが分かる：
(defun complement (fn) #'(lambda (&rest args) (not (apply fn args))))
complementの返した関数は，
complementが呼ばれた時点でのパラメータfnの値を使っている．
だから固定された選択肢の中から関数を選ぶだけでなく，
complementはどの関数のコンプリメント関数でも求めに応じて生成できる：
> (remove-if (complement #'oddp) '(1 2 3 4 5 6)) (1 3 5)
関数を引数として渡せることは抽象化のための強力な道具だ． 関数を返す関数が書けることで，それを最大限に利用できるようになる． 残りの節では関数を返すユーティリティの例を幾つか挙げる．
直交的(orthogonal)なプログラミング言語とは，
少数のオペレータを多数の様々な方法で結合させることで，
多様な意味が表現できるもののことだ．
おもちゃのブロックは極めて直交的だが，プラモデルはほとんど直交的でない．
complementの主な長所は，プログラミング言語を一層直交的にしていることだ．
complementの登場以前，
Common Lispにはremove-ifとremove-if-not，
subst-ifとsubst-if-not等の関数の組があった．
complementがあれば，それらの片方で事は足りる．
マクロsetfもLispの直交性を高めている．
Lispの方言の古いものでは，データを読む関数と書く関数の組があったりしたものだ．
すると例えば属性リストがあれば，
属性を設定する関数が1個，求める関数がもう1個必要だろう．
Common Lispには後者に当たるgetしかない．
属性を設定するにはgetをsetfと組み合わせて使う：
(setf (get 'ball 'color) 'red)
Common Lispの体系そのものを小さくすることは難しいが，代わりにいい方法がある．
Common Lispの小規模な部分集合だけを使うことだ．
私達をこのゴールへ導いてくれる，
complementやsetf等の新しいオペレータを定義できないものだろうか？
関数を組にまとめられる方法が少なくとも一つある．
多くの関数には等価で破壊的な別の関数がある．
remove-ifとdelete-if，reverseとnreverse，
appendとnconc等だ．
ある関数と等価で破壊的な関数を返すオペレータを定義することで，
破壊的な関数を明示する必要がなくなる．
(defvar *!equivs* (make-hash-table)) (defun ! (fn) (or (gethash fn *!equivs*) fn)) (defun def! (fn fn!) (setf (gethash fn *!equivs*) fn!))\caption{等価で破壊的な関数を返す．} \label{fig:DestructiveEquiv}
第\ref{fig:DestructiveEquiv}図には「等価で破壊的な関数」の考えを補助するコードを示した．
グローバルなハッシュ表*!equivs*は，
ある関数とそれに等価で破壊的な関数との対応付けを行う．
def!によって等価で破壊的な関数を設定し，!はそれを返す．
オペレータ!（びっくりマーク）は，
Schemeで副作用のある関数の名前に!を付け加える慣習から取った．
(def! #'remove-if #'delete-if)
さて上のように定義してしまえば
(delete-if #'oddp lst)
とする代わりに
(funcall (! #'remove-if) #'oddp lst)
とすればいい． ここではCommon Lispの造りがまずいせいでこの考えの元々の美点が隠れてしまっているが， Schemeではもっとはっきり見える：
((! remove-if) oddp lst)
直交性の向上もさることながら，オペレータ!は他にも幾つかの利点をもたらす．
(! #'foo)はfooと等価で破壊的な関数だと見てすぐ分かるので，
プログラムがさらに簡潔になる．
また，破壊的な操作がソースコード内で目立って認識しやすい形を取るようになる．
それらはバグを探すときに特別な注意を払うべきものだから，これはいいことだ．
ある関数とそれに等価で破壊的な関数との関係は，普通は実行する前に明らかになるので，
!はマクロとして定義するのが一番効率的だ．
そのためのリードマクロを定義してもいいだろう．
計算コストの高い関数を同じ引数で複数回呼び出したいときがあるなら， 値をメモワイズ(memoize)しておくのが得だ． 以前の返り値をみな保管しておき， 関数が呼び出される度にまず保管場所を見て，値が既に得られていないか調べる．
(defun memoize (fn)
(let ((cache (make-hash-table :test #'equal)))
#'(lambda (&rest args)
(multiple-value-bind (val win) (gethash args cache)
(if win
val
(setf (gethash args cache)
(apply fn args)))))))
\caption{メモワイズユーティリティ．}
\label{fig:Memoizing}
第\ref{fig:Memoizing}図には一般的なメモワイズユーティリティを示した．
memoizeに関数を渡すと，等価なメモワイズ機能付き関数が返る．
それは以前の返り値を蓄えるハッシュ表を持ったクロージャだ．
> (setq slowid (memoize #'(lambda (x) (sleep 5) x))) #<Interpreted-Function C38346> > (time (funcall slowid 1)) Elapsed Time = 5.15 seconds 1 > (time (funcall slowid 1)) Elapsed Time = 0.00 seconds 1
メモワイズ機能付き関数では，呼び出しの繰り返しはハッシュ表の検索に過ぎない．
もちろん新しい値で呼んだときにも検索してしまうという余分な負荷はあるが，
十分計算コストの高い関数だけにメモワイズ機能を付けるのだから，
その負荷は比較すれば無視できると想定していいだろう．
さて上のmemoizeの実装方法は大抵の場合には適しているが，幾つか制限もある．
呼び出し方を同じと見なすのは引数リストがequalのときだが，
これは関数がキーワード引数を取るときには厳しすぎるだろう．
また返り値が1個の関数のみを想定していて，多値を蓄えたり返したりはできない．
関数fのコンプリメント関数は〜fと表記される． 第5.1節では〜をLispの関数として定義するクロージャを示した． 関数に対してよく使われる操作には他に合成があり，○で表記される． fとgが関数ならばf◯gも関数で，f◯g(x)=f(g(x))である． これもクロージャでLispの関数として定義できる．
(defun compose (&rest fns)
(if fns
(let ((fn1 (car (last fns)))
(fns (butlast fns)))
#'(lambda (&rest args)
(reduce #'funcall fns
:from-end t
:initial-value (apply fn1 args))))
#'identity))
\caption{合成関数のためのオペレータ．}
\label{fig:FunctionalCompo}
第\ref{fig:FunctionalCompo}図では関数composeを定義した．
これは任意の数の関数を引数に取り，それらの合成を返す．
例えば
(compose #'list #'1+)
が返すのは
#'(lambda (x) (list (1+ x)))
と等価な関数だ．
composeの引数に渡された関数は，
最後以外はみな引数が1個の関数でなければならない\note{last}．
最後の関数には制限は何もなく，それがどんな引数を取っても，
composeの返す関数も同じ引数を取る．
> (funcall (compose #'1+ #'find-if) #'oddp '(2 3 4)) 4
notがLispの関数なので，complementはcomposeの特殊形と言える．
それは
(defun complement (pred) (compose #'not pred))
として定義できる．
(defun fif (if then &optional else)
#'(lambda (x)
(if (funcall if x)
(funcall then x)
(if else (funcall else x)))))
(defun fint (fn &rest fns)
(if (null fns)
fn
(let ((chain (apply #'fint fns)))
#'(lambda (x)
(and (funcall fn x) (funcall chain x))))))
(defun fun (fn &rest fns)
(if (null fns)
fn
(let ((chain (apply #'fun fns)))
#'(lambda (x)
(or (funcall fn x) (funcall chain x))))))
\caption{関数生成方法の更なる例．}
\label{fig:FunctionBuilders}
関数の組み合わせ方は合成だけではない．例えば
(mapcar #'(lambda (x)
(if (slave x)
(owner x)
(employer x)))
people)
のような式をよく見かける．
このような関数を自動的に生成するオペレータが定義できる．
第\ref{fig:FunctionBuilders}図のfifを使い
(mapcar (fif #'slave #'owner #'employer)
people)
とすれば同じ結果になる．
第\ref{fig:FunctionBuilders}図にはよく使われる種類の関数を生成する関数を幾つか示した．
2番目のfintを使うのは次のようなときだ：
(find-if #'(lambda (x)
(and (signed x) (sealed x) (delivered x)))
docs)
find-ifの第2引数に与えられた述語が，
その内部で呼ばれている3個の述語の共通部分を定義している．
fint（"function intersection" 関数の共通部分）を使えば
(find-if (fint #'signed #'sealed #'delivered) docs)
と書ける．
同様に，関数集合の合併を返すオペレータも定義できる．
関数funはfintと似ているが，andでなくorを使っている．
Lispのプログラムでは再帰関数は極めて重要なので， それらを生成するユーティリティを定義しておいて損はない． この章と次の章では，よく使われる2種類の再帰関数を生成する関数について説明する． ただCommon Lispでは，これらの関数を使うのはまずい方法だ． 話題がマクロまで進めば， この仕組みにさらにこなれた外見を与える方法を知ることになるだろう． 再帰関数を生成するマクロについては第15.2, 15.3章で議論する．
プログラム内に繰り返した形が現れるのは，より高いレベルの抽象的手法が使えることの印だ． そういう形はLispプログラムの中では次のような関数より頻繁に見られる：
(defun our-length (lst)
(if (null lst)
0
(1+ (our-length (cdr lst)))))
または
(defun our-every (fn lst)
(if (null lst)
t
(and (funcall fn (car lst))
(our-every fn (cdr lst)))))
これら2個は構造がかなり共通している． 共にリストの連続したcdr部に再帰的に作用し，毎回同じ式を評価している． ベース・ケースでは別で，他とは違った値を返す． この形はLispのプログラム内で大変頻繁に現れるので， 経験を積んだプログラマは思考を中断せずに読みこなしたり新しいのを書いたりできる． 実際，そういった形を新しい抽象化構造に組み込む方法はすぐに理解できる．
(defun lrec (rec &optional base)
(labels ((self (lst)
(if (null lst)
(if (functionp base)
(funcall base)
base)
(funcall rec (car lst)
#'(lambda ()
(self (cdr lst)))))))
#'self))
\caption{平坦なリストに対する再帰関数を定義する関数．}
\label{fig:FlatListRecur}
しかし形そのものはみな同じだ．
これらの関数を手で書く代わりに，
自分のためにそれらを生成してくれる関数を書けるようになっておくべきだ．
第\ref{fig:FlatListRecur}図にはlrec ("list recurser") という関数生成関数を示した．
これはリストの連続したcdr部に再帰的に作用する関数のほとんどを生成してくれる筈だ．
lrecの第1引数は，その時点でのリストのcar部と，
再帰を続けるために呼ばれる関数という2個の引数を取る関数でなければならない．
lrecを使えば，our-lengthは
(lrec #'(lambda (x f) (1+ (funcall f))) 0)
として表現できる．
リストの長さを得るには要素を調べたり途中で止まる必要はないので，
オブジェクトxは常に無視してよく，常に関数fを呼び出せばよい．
しかしour-everyを表現する可能性の利点は両方とも活用する必要がある．
例えばoddpだ
\footnote{広く使われているあるCommon Lisp処理系では，
functionpは誤ってtとnilに真を返す．
その処理系ではlrecの第2引数に渡しても機能しないだろう．}：
(lrec #'(lambda (x f) (and (oddp x) (funcall f))) t)
lrecの定義では，selfというローカルな再帰関数を生成するためにlabelsを使った．
再帰途中に関数recに与えられる引数は，
その時点でのリストのcdr部と再帰呼び出しを形成する関数の2個だ．
our-every等の再帰呼び出しを行う部分が最後に来る関数には，
第1引数が偽を返したその時点で止まって欲しい．
これは再帰呼び出しに渡された引数は値でなく，
必要があれば呼び出して値を求められる関数でなければならないということだ．
; copy-list (lrec #'(lambda (x f) (cons x (funcall f)))) ; remove-duplicates (lrec #'(lambda (x f) (adjoin x (funcall f)))) ; find-if, for some function fn (lrec #'(lambda (x f) (if (fn x) x (funcall f)))) ; some, for some function fn (lrec #'(lambda (x f) (or (fn x) (funcall f))))\caption{
lrecで表現された関数．}
\label{fig:lrec}
第\ref{fig:lrec}図に示したのは，既存のCommon Lispの関数をlrecを使って定義したものだ
\footnote{処理系によっては，これらの関数を表示する前に
*print-circle*をtに設定しなければならないかもしれない．}．
lrecを使っても求める関数の最も効率のよい実装方法に必ず行き着く訳ではない．
実際，この章で定義されたようなlrecを始めとする再帰関数生成関数は，
末尾再帰による方法に一歩及ばないことが多い．
このためこれらはプログラム開発の初期のうちや，速度が重要でない箇所で使うのが一番だ．
%}}}
Lispプログラムによく見られる再帰の形には他のものもある：部分ツリーに対する再帰だ． この形は（おそらく入れ子になった）リストについて， そのcar部とcdr部の両方を再帰的に下っていきたい場合に見られる．
Lispのリストは多目的な構造体で， 連続構造，集合，対応，配列，ツリーを含む色々なものを表現できる． リストをツリーとして解釈する方法は幾つかある． 一番よく使われるのは，リストを二分ツリー（binary tree）に， car部とcdr部をそれぞれ左右の枝に見なす方法だ． （実際，リストの内部表現は大抵そうだ．） 第\ref{fig:ListsAsTrees}図にはリストとそれが表現するツリーの例を3個示した． そういうツリーの内部節点はドット対（dotted-pair）表現したリストの点に対応するので， リストをその形式で考えればツリーの構造は解釈しやすいだろう：
(a b c) = (a . (b . (c . nil))) (a b (c d)) = (a . (b . ((c . (d . nil)) . nil)))
どのリストも二分ツリーとして解釈できる．
そのためcopy-listとcopy-tree等のCommon Lispの関数の組がある．
前者はリストを連続構造としてコピーする．
リストが部分リストを含むとき，それは連続構造の要素に過ぎないのでコピーされない：
> (setq x '(a b)
listx (list x 1))
((A B) 1)
> (eq x (car (copy-list listx)))
T
それとは対照的に，copy-treeはリストをツリーとしてコピーする．
部分リストは部分ツリーなので，やはりコピーされる：
> (eq x (car (copy-tree listx))) NIL
copy-treeは次のように定義できる：
(defun our-copy-tree (tree)
(if (atom tree)
tree
(cons (our-copy-tree (car tree))
(if (cdr tree) (our-copy-tree (cdr tree))))))
この定義は実は広く使われる形の一つだということが分かる． （この後出てくる関数は形をはっきりさせるために少し妙な方法で書かれている．） 例えばツリーの葉を数えるユーティリティを考えてみよう：
(defun count-leaves (tree)
(if (atom tree)
1
(+ (count-leaves (car tree))
(or (if (cdr tree) (count-leaves (cdr tree)))
1))))
ツリーの持つ葉の数は，リストとして表現されたときに見えるアトムの数より多い：
> (count-leaves '((a b (c d)) (e) f)) 10
ツリーの持つ葉とは，ツリーをドット対表現で見たときに見えるアトムの全てだ．
ドット対表現では((a b (c d)) (e) f)は4個のnilを含むが，
リスト表現ではそれらは見えない（括弧1組につき1個あるのだが）．
だからcount-leavesは10を返す．
前の章では，ツリーに作用するユーティリティを幾つか定義した．
例えばflatten（jooページ）はツリーを引数に取り，
その中の全てのアトムをリストに括って返す．
つまりflattenに入れ子になったリストを渡すと，
一番外側以外の括弧が無くなっただけのようなリストが返る：
> (flatten '((a b (c d)) (e) f ())) (A B C D E F)
この関数は（かなり非効率的だが）次のようにも定義できる：
(defun flatten (tree)
(if (atom tree)
(mklist tree)
(nconc (flatten (car tree))
(if (cdr tree) (flatten (cdr tree))))))
最後にfind-ifの再帰版であり，
平坦なリストだけでなくツリーにも作用できるrfind-ifについて考えよう：
(defun rfind-if (fn tree)
(if (atom tree)
(and (funcall fn tree) tree)
(or (rfind-if fn (car tree))
(if (cdr tree) (rfind-if fn (cdr tree))))))
find-ifをツリーにも作用するように一般化するには，
葉のみを検索するのか，それとも部分ツリー全体を検索するのかを決めなければならない．
ここでのrfind-ifは前者を採ることにする．
つまり呼び出し側は第1引数として渡された関数はアトムにのみ適用されると考えてよい：
> (rfind-if (fint #'numberp #'addp) '(2 (3 4) 5)) 3
copy-tree，count-leaves，flattenにrfind-ifといった
4個の関数の構造は，何と似ていることだろう！
実際，それらはみな部分ツリーに作用する関数の典型的な例だ．
cdr部での再帰もそうだが，こういうものの原型を曖昧なままに放っておく事はない
---そのインスタンスを生成する関数を書くことができる．
(defun ttrav (rec &optional (base #'identity))
(labels ((self (tree)
(if (atom tree)
(if (functionp base)
(funcall base tree)
base)
(funcall rec (self (car tree))
(if (cdr tree)
(self (cdr tree)))))))
#'self))
\caption{ツリーに対する再帰関数．}
\label{fig:RecurOnTree}
原型そのものを掴むため，それらの関数をよく見て何が定型でないのかに注目しよう．
our-copy-treeは本質的には2個の事実を表す：
consを適用する．
そのため，これは2個の引数を取る関数生成関数の呼び出しとして表現できる：
(ttrav #'cons #'identity)
ttrav ("tree traverser")の定義は第\ref{fig:RecurOnTree}図に示した．
再帰呼び出しのときは渡す値は1個でなく2個で，
それぞれ左の部分ツリーと右の部分ツリーに対して再帰を行う．
再帰の基底が関数のときは，
その関数はその時点での葉に対して呼ばれる．
平坦リストに対する再帰では基底の値は必ずnilだが，
ツリーに対する再帰では基底の値は有用であることがあり，
それを使いたくなることもあるかもしれない．
; our-copy-tree (ttrav #'cons) ; count-leaves (ttrav #'(lambda (l r) (+ l (or r 1))) 1) ; flatten (ttrav #'nconc #'mklist)\caption{
ttravで表現された関数．}
\label{fig:Byttrav}
ttravを使うと，これまで説明した関数はrfind-if以外みな表現できる．
（第\ref{fig:Byttrav}図に示した．）
rfind-ifを定義するには，
いつ，どの場合に再帰呼び出しが行われるかを制御させてくれるような，
さらに一般的なツリー用再帰関数生成関数が要る．
ttravの第1引数には，再帰呼び出しの結果を取る関数を与えた．
一般的な状況においては，代わりに，
再帰呼び出しそのものを代表する2個のクロージャを取る関数を使う．
するとツリーの任意の深さまでのみを探索する再帰関数が書ける．
ttravによって生成された関数は必ずツリー全体を探索する．
count-leavesやflattenは
とにかくツリー全体を探索せざるを得ないのでそれでいいが，
rfind-ifには探す対象が見つかった時点で探索を止めて欲しい．
それにはさらに一般的なtrec（第\ref{fig:RecurOnTree}図）を使わなければならない．
trecの第2引数は関数で，
再帰途中の時点でのオブジェクトと2個の再帰関数という3個の引数を取る．
それらの再帰関数はそれぞれ左右の部分ツリーに対する再帰を代表するクロージャだ．
trecを使うとflattenはこのように定義できる：
(trec #'(lambda (o l r) (nconc (funcall l) (funcall r)))
#'mklist)
以上よりrfind-ifはoddpによって以下のように表現できる：
(trec #'(lambda (o l r) (or (funcall l) (funcall r)))
#'(lambda (tree) (and (oddp tree) tree)))
(defun trec (rec &optional (base #'identity))
(labels
((self (tree)
(if (atom tree)
(if (functionp base)
(funcall base tree)
base)
(funcall rec tree
#'(lambda ()
(self (car tree)))
#'(lambda ()
(if (cdr tree)
(self (cdr tree))))))))
#'self))
\caption{ツリーに対して再帰を行うための関数．}
\label{fig:RecurOnTree2}
残念なことに関数を表現するのに関数生成関数を呼ぶのは，
シャープクォート付きのλ式を呼ぶのに比べ，実行時に不必要な負荷がかかる．
シャープクォートの付いたλ式は固定されたデータだが，
生成関数の呼び出しは実行時に評価される．
本当に実行時に生成関数を呼ばなければならないなら，
それを使ってもよいことはない．
しかし，少なくともある場合には生成関数を予め呼ぶことができる．
リードマクロ#.（シャープ・ドット，シャープ点）を使うと，
ソース読み込み時に新しい関数を生成できる．
その式が読み込まれたときにcomposeとその引数が定義されている限り，例えば
(find-if #.(compose #'oddp #'truncate) lst)
とすることができる．
これならcomposeの呼び出しはLispリーダによって評価され，
生成された関数は固定的データとしてコード内に挿入される．
oddpとtruncateは共に組み込み関数なので，
composeの定義が既に読み込まれている限り，
composeの呼び出しは読み込み時に評価されると思っていいだろう．
一般的に言って， 関数の合成と組み合わせはマクロを使えば一層簡単かつ効率的に実現できる． 関数の名前空間が分離しているCommon Lispでは特に効果が顕著だ． マクロの導入後，第15章で，ここでの話題の大半をもっと豪華な器を使って扱う．