何度か言ってるけど再帰は難しくない。
ハッキリ言うけど、「再帰が如何にも難しい」って書いてる本の著者がいたり、あるいは学校の先生がいたとしたら、こう考えて良い。
「奴らはバカなんだ」
と。
何度か書いたが、再帰の正体は高校数学で習う漸化式だ。
わざわざ大学入試で数学を受験させておいて、プログラミングを学ぶ際に再帰と漸化式の関係性を言わない、なんつーのはバカの所業としか思えない。
一体何のために学生を数学で選別してるのか。
無意味な行為、にしてる以上、やっぱバカなんだよ。
だから例えばC言語の宿題なんかで
・漸化式 b[n+1] = b[n] + 5 (整数 n ≥ 1), b[1] = −5.5 で表わされる数列がある。初項から第 10 項までを表示するプログラムを作れ。
なんつーアホな宿題が出たら、forとかwhileを使ったりする解は避けるべきなんだ。堂々と先生に嫌がらせしよう。そのままプログラムして提出しちまえばいい。
#include <stdio.h>
#include <stdlib.h>
double b(int n) {
if (n == 1) {
return -5.5;
} else {
return b(n - 1) + 5;
}
}
int main(void) {
for (int n = 1; n < 11; n++) {
printf("%lf\n", b(n));
}
return EXIT_SUCCESS;
}
forやwhileを書いて人間コンパイラになるな。この程度の問題(※1)を繰り返し構文で書け、なんて言われるのは人間の尊厳を脅かされているのである。
教えて!gooなんかでこのテの質問を見る度に「学生も可哀想に」って同情を禁じ得ないのだ。そのまま書けば済む話なのに、わざわざ遠回りさせよう、とかアホちゃうか、とか毎回思うんだ。
このテの益のない悪問は撲滅すべきなのである。マジで毎度毎度、まずは出題者の知性を疑っている。ヘンな教師に付いた生徒は大変だよな。
何度も言うけど再帰は別に難しくない。単に脅されてるだけ、なのである。
大学入って、プログラミングを学び始めて、再帰を学ぶ際に押入れに眠ってる、高校時代に使った数研出版の問題集なり、パターン問題集なり引っ張り出してきて、漸化式の問題を10問もプログラムで書き下せば嫌でも再帰の形式には慣れる。
プログラミングに論理性は関係ない。パターンを多く知る、事がより大切で、再帰が出来ないとしたら単に圧倒的に練習量が足りないだけ、なんだよ。
と言う辺りでここまでが基礎。
Lispの話に入ろう。
数値を扱う計算に於いては上のやり方で良い。
が、再帰プログラミングは、特にLispに於いてはそっちはあまり出てこない。
どっちかっつーとリスト操作で再帰が多いわけだ。
こういう場合はどうすんのか。
いや、これも問題がない。Lispには再帰の最高傑作と思われる関数がビルトインだったりする。その「内情」を暗記すれば殆どのケースには対応出来るんだ。
そしてその「最高傑作」はたかだか4つ程しかない。ここに50年以上のプログラミングの叡智の結晶がある。だからその内情を詳しく分析する事だ。そんだけ。
実の事を言えば、僕は最初にLispを学んだ時、異様に「ビルトイン関数の再実装」ばっかやらされて面食らったクチだ。
「え?プログラミングをやりたいのになんでこんなに"ビルトイン関数"のソースコードの説明ばっかやってんの?」
とか思った。
うん、通常こういう「学習法」はねぇよな。Pythonを勉強する時Pythonの標準モジュールの関数をソースコードで説明されたり、再実装ばっかさせられたら困るだろ。
Pythonに限らない。フツーは確かにそんな事はやらんのだが、Lispの学習に於いてはその手法が顕著に現れる。
しかし、それはLispがコンピュータ・サイエンスの歴史上、ある意味究極の「作品」だからだ。Lispで再帰で定義されて提供されてる関数は「ユーティリティとして使い回しが効く最高傑作」であり、そしてそれら以上の傑作は今のところ無い。つまり、「再帰定義関数の最高峰」がLispのビルトインになってるんだな。
もちろん見つかってないだけで他にも「傑作」って呼べるだろうものが未開の分野にはあるかもしんない。しかし今んトコ、Lispの「ビルトイン関数」のメッセージってのは極端に言うと、
「貴方(ユーザー)にコンピュータサイエンス史上の最高傑作を与えます。あとはこれらを駆使して新たな領域を開拓してください。」
なのだ。
だから取り敢えず、リスト再帰に於いてはLispのビルトイン関数の4種類くらいを「徹底して学べ」ば道は開ける、ってこった。
そしてこれは初めから答えはもう用意されてる、ってのと同義だ。これら基礎的な4つの再帰関数を自分で書ければ御の字、免許皆伝、であり、これ以上難しい再帰はあるかもしれないが、殆どのケースではそれらは単なるパズルであり、実用性を保証するのは極めて難しくなると言う事だ。
(define (member v lst)
(cond ((null? lst) #f)
((equal? v (car lst)) lst)
(else (member v (cdr lst)))))
旧い言い方だと「cdr再帰」と言われる手法を用いた関数の基本であり最高傑作である。調べる対象は常にリストのcarであり、条件を満たさなければcdr再帰する。そしてもう一つの終了条件、「リストが空リストだったら停止せよ」と言うのも忘れちゃいけない。
なお、この関数もハックが施されている。「リストに要素が見つからなかったら偽を返すのに」、一方、見つかった際には先頭がその要素である部分リストを返す、のだ。
これは昔のLisperが「真を返すより、連なったデータを返したら何かに使い回しが効くんじゃね?」と言う予想をしたので、こういう形式になっている。なおかつ、Scheme/Racketでは#fじゃなければ全部真(#t)だ。だからこういうテキトーっつーかデタラメな返し方をして構わんわけだ。
2つ目は2つのリストを結合するappend。ホンモノのappendはリストを可変長引数として取るが、その辺は忘れて構わない。あくまでリスト再帰を学ぶには2つのリストを引数に取れば充分、だからだ。
(define (append lst0 lst1)
(if (null? lst0)
lst1
(cons (car lst0) (append (cdr lst0) lst1))))
これは初見だとかなり不可思議な定義に見えるだろう。
その原因は「どこにも結合の為の何かが書かれてない」ように見えるからだ。再帰部分が明らかに黒魔術っぽく見えるのがその不可思議さを醸し出している。
しかしそれでも上手く動く。これを「理解」出来るか否か、がリスト再帰の最初の、かつ最大の障壁となる。
ただ、眺めてだけいてもイマイチピンと来ないだろう。必要なのはデバッガ、あるいはtraceで、変数であるリストがどうやって操作されて結合されていくのか、一つ一つ追ってみれば良い。そうすれば「なるほど確かに」となるだろう。
3つ目はmapだ。汎用的な高階関数の代表例で、再帰を抽象化する為に本体は再帰で書かれている。つまり、「再帰を使わなくて済むように再帰で書かれている」わけだな。
これは引数として関数とリストを一つづつ取る事にする。ホンモノのmapはリストを可変長引数として取るが、それは忘れる。シンプルな実装でリスト再帰を学ぶのだ。
(define (map proc lst)
(if (null? lst)
lst
(cons (proc (car lst)) (map proc (cdr lst)))))
驚くべきことに、実は構造的にはmemberの変種に見えるだろう。その通りだ。両者ともcdr再帰してるだけ、である。違うのは常にlstのcarをとってprocを適用してるだけ、である。
この恐ろしく単純な定義で八面六臂の大活躍を見せるのだから、確かにmapは再帰関数の最高傑作の一つなのである。
最期はreduceと言われるものだ。Schemeを含め、一部の関数型言語界隈ではfoldと言った方が良いかもしれない。「畳込み関数」とも言われる。
このブログでも何度か取り上げているが、非常に高機能かつ強力な高階関数で、これもmapと同様、再帰的に定義された関数である。
しかし、その定義はまたもや恐ろしくシンプルなのだ。定義がシンプルな癖にとんでもない破壊力を持ってるので、これもまさしく再帰関数の最高傑作の名に恥じない作品だ。
引数は関数、初期値、リストの3つを取るが、これもホンモノは、リスト引数は可変長となっている。
(define (reduce proc init lst)
(if (null? lst)
init
(reduce proc (proc (car lst) init) (cdr lst))))
他の再帰の例題としてはリストの要素の和を全部取れ、と言うPythonのsum関数みたいなヤツを作れ、とか、あるいはリストを反転させるreverse(Pythonで言うとreversed関数) を作れ、と言ったような問題が考えられる。
しかし、いつか言ったが、reduceはそのテの問題を全部消し去る程超強力だ。sumもreverseもreduceを使えば次のように簡単に書くことが出来る。
(define (sum lst)
(reduce + 0 lst))
(define (reverse lst)
(reduce cons '() lst))
一体何が起きればこんな風になるのか、一発では分からないだろう。
reduceの定義を良く読み、その結果を想像するんだ。ウンウンと悩め。時間をかけて悩むだけの価値がreduceにはある。
reduceは最強の再帰定義による関数であり、最強の高階関数でもある。
なお、2014年にJavaでもこのLispのmapとreduceにあたる機能が導入された。
が、恐らく殆どのJavaユーザーはmapやreduceが一体「どんな原理」で仕事をしてるのか知らないだろう。そもそも再帰が不得手な言語だし。
Lispなら全部「そこにある」。ここで見たように実は貴方が充分書ける範疇のユーティリティだし、調べてみれば動作原理はかなり簡単だ、って事が分かると思う。
Lispは比較的「言語設計者」と「ユーザー」の垣根が無いに等しい言語なのだ。
それが分かるだけでも儲けもんだろう。
この、コンピュータサイエンス史上の再帰関数の最高傑作の4つ、さえ自前で・・・暗記でも何でもイイが、実装出来ればリスト再帰畏るるに足らず、である。これら4つさえ理解出来ればその時点でリスト再帰はかなり自在に扱えるようになってるだろう。それくらい教育上重要な価値があり、他のプログラミング言語では学べないくらいのテクニカルな意味がある。
と、実はここまで前フリなのだ。
多分ここまで読んでくれた人の中では、
「たった4つでイイの?他に重要なリスト再帰って無いの?」
と不安に感じる人がいるかもしんない。
う〜ん、と考えてみる。
いや、この4つで基本充分なんだよ。それは「使用頻度の問題」があるからだ。
これら4つは基本的には(実はreduceを除くが・※2)適用範囲がメチャ広い。プログラミングする際に毎回、って言って良い程お世話になる、極めて「使用する頻度が高い」関数なんだ。じゃないとユーティリティにはならない。
「使用する頻度が高い組み込み関数だからこそ」その内情を学ぶのがより良いプログラミングを行う際の手助けになる、っつーかセンスを磨くワケだな。
でも不安に感じるのも良く分かる。
一方、こう言う判断に沿うと厄介なのは、「使用頻度が低い癖に必要になった時、自作するにはちとメンドい」再帰関数である。そういうのが無いか?って問われればある、としか言いようがない。
使用頻度が低い癖に、必要になった時、自作するのがメンド臭い再帰関数の代表例がflattenである。
flattenは平坦化関数、等とも呼ばれる。
例えば、
'((a) b (c (d) . e) ())
みたいな「リストのリスト」、つまり入れ子のリストを
'(a b c d e)
みたいに直しちゃうのを「リストの平坦化」、つまりflattenと呼ぶのである。
これはなかなか悩ましい問題だ。と言うのも実の事言うと、リストと言うデータ型はネスト(入れ子)を簡単に作れて、そのカタチを保持出来るのが強みなわけだ。
逆に言うと、入れ子のリストを平坦化「せねばならない」ような状況ってのは・・・実の事言うとそんなに無いと思う。
仮にあっても、いつぞや見せた通り、問題に合わせたカタチでの対応手段が存在する。
従って、特定の関数として「いつ必要になるか分からん」けど、プログラミング言語のライブラリとしては有ってくれたら嬉しいと言えば嬉しいかもしんない・・・・・・と言える程ビミョーな存在意義にしか感じられないのだ・・・・・・実際、この時までRacketでユーティリティとして提供されてる、なんて夢にも思わんかったし(笑・※3)。
実は僕もこのflattenを書く練習問題、とか過去やった事はあるんだ。でも実際のプログラミングで出番が来る、ってのはまぁ、無かったなぁ・・・・・・。うん。微妙。なんつーの、個人的な感覚ではLispでは珍しい「宿題の為の問題」的なニュアンスになってる。知らんけど。
flattenの基本的な定義は以下のようなモノだ。
(define (flatten v)
(cond ((null? v) v)
((pair? v) (append (flatten (car v)) (flatten (cdr v))))
(else `(, v))))
基本的なアイディアはリストの先頭をまずは調べ、そこがペア(cons)だったら再帰的にそこにflattenを適用する、って事だ。そして当然cdrにもflattenを再帰的に適用する。
言われりゃ簡単なんだけど、通常こういったcarにもcdrにも再帰を適用する、ってスタイルは出てこない(※4)。こういうのを旧い言い方でcar+cdr再帰、と呼ぶ。
そう、リスト平坦化関数flattenはcar+cdr再帰の基礎的かつ代表的な例なんだ。
そしてこのテの再帰は末尾再帰最適化が出来ない。実装上非常に厄介な性質をも併せ持っている。
なお、ポール・グレアムのOn Lispにもflattenの実装例が載っている(※5)。Schemeの標準的な書き方で見れば次のようになるだろう(※6)。
(define (flatten x)
(define (rec x acc)
(cond ((null? x) acc)
((pair? x) (rec (car x) (rec (cdr x) acc)))
(else (cons x acc))))
(rec x '()))
あるいは、もっと標準的な名前付きletを使った書き方だと次のようになる。
(define (flatten x)
(let loop ((x x) (acc '()))
(cond ((null? x) acc)
((pair? x) (loop (car x) (loop (cdr x) acc)))
(else (cons x acc)))))
再帰時点でloopが繰り込みながらloopされている。
一見しただけで「ややこしい実装」であり、「末尾再帰最適化が不可能な」関数だ、と言うのが分かるだろう。
取り敢えず、かなり宿題臭く、パズルの域にかかってるような関数flattenだが、どっちにしてもcar+cdr再帰の実例としては悪くはない。
これを含めて詳細を学習すれば、実用的な意味ではリスト再帰は畏るるに足らず＋α、の地点へと到達はするだろう。
※1: この解は当然効率的ではない。そして仕様上、C言語では末尾再帰最適化は要求されてはいないので、末尾再帰で書いても効率化はしない。
もっとも教育現場であるとか、ソースコードのポータビリティを重要視するのなら、特定のコンパイラの「独自拡張」をアテにすべきではない。
が、もしgccやclangなんかのユーザーであるなら、その機能を徹底的に知って使う事は悪い事ではない。
※2: reduceはANSI Common Lispでは組み込み関数である。
一方、reduceあるいはfoldは今現在の標準Schemeでは、不思議な事に組み込みとしては定義されてはいない。
※3: Battery IncludedのPythonでさえ標準モジュールに入ってない、ってトコを見ても必要になる頻度が極めて低い、と言うのは事実と思われる。従ってPythonでもflattenを実現するにはかなりややこしいハックが要り用になる模様だ。
※4: 厳密に言うと出てくる場合がある。特に木構造を弄る時、だ。
ただ、この辺はまさしくコンピュータ・サイエンス的にかなり深みにはまり込んだ話題で、表層的なプログラミング、と言う範疇ではそうそうお目にはかからない、だろう。要するに、貴方がデータ構造として連想リストもハッシュテーブルもすっ飛ばして「木構造」を選択せねばならない、と言うのはよっぽどのケースだ、と言う事だ。
ただし、プログラミングのエキスパートは常時木構造を相手にはしてる。
※5: あるいは実用Common Lisp(PAIP)の310ページ辺りにも定義が載っている。ポール・グレアムの版と寸分違わない定義が見れる筈だ。
※6: 関数atomはLispの基礎的関数に数えられるが、何故か標準Schemeには含まれていないし、用語的にもatomと言うのはSchemeではあまり聞かない。
定義的には標準Schemeだと
(define (atom? x)
(not (pair? x)))
あるいは、Racketだと
(define atom? (compose not pair?))
として作成出来る。
なお、composeは合成関数を生成する関数で、これも関数を返す高階関数の傑作であるが、詳細はポール・グレアムのOn Lispに譲る。
