教えて!gooで興味深い質問が投稿された。
参照透過な関数型言語で余再帰と遅延評価を使う
どゆいみですかぜんぜんわかんない
質問者の日本語は拙い、と言うかかなり不自由だ。
そもそもこれらの単語は「パソコン用語」ではない。
まぁでもその辺はいいだろう。
このブログの読者には、参照透過も関数型言語も遅延評価も既にお馴染みの単語だと思う。
参照透過(Referential Transparency)とはデータを非破壊的に扱う事だ。ある関数を定義しても引数として受け取ったデータを内部で書き換えない。そうすれば、常に同じ引数に対して常に同じ返り値が保証される。これを参照透過、とカッコ付けて言うが、このブログで紹介してる「プログラミング法」の殆どは参照透過で書いてるんで、あまりにも当たり前って言えば当たり前の作法だろう。
関数型言語はこの「参照透過」でプログラミングするのを前提として開発されてるプログラミング言語だ。参照透過を「強制する」プログラミング言語は純粋関数型言語と言って、あまり数は多くない。代表的、そして殆ど唯一と言って良い程の知名度があるのがHaskellだ。一方、必要に応じて参照透過性を破る、つまり「データの破壊的変更を許す」関数型言語もあって、それを「不純な」関数型言語と言う。OCaml、MicrosoftのF#が代表格だ。Lisp語族もここに含まれる、と言っていいけど、Schemeは「返り値を持たない」関数が存在し、関数型言語とは言えない仕様になっている。また、ANSI Common Lispは「必ず返り値がある」関数型言語に必須のデザインを採用してるが、一方、あまりユーザーは参照透過性にはこだわっていない。また、マクロを多用するANSI Common Lispではマクロ記述時にはこの「参照透過」を無視してプログラムを組むケースの方が多いだろう(※1)。
いずれにせよ、Lispは不純な関数型言語ではあるが、Terminology的にはもうちょっと弱く、「原始的な関数型言語」と言った方が実態に近いだろう。また、ANSI Common Lispは関数型言語の側面はあるが、総体的にはマルチパラダイム言語で、そういう意味では結果、C++やPythonと共有されるコンセプトを持っていると思われる。
なお、Pythonもマルチパラダイム言語だが、このブログでは関数型言語として扱っている。つまり「データを破壊的変更するのを避け」、参照透過性を維持するようなコードをなるたけ書くようにはしてる。
遅延評価も改めて説明しよう。通常のプログラミング言語では、関数は「引数を評価してから」関数をそれらに適用する。こういうのを先行評価や正格評価、と呼ぶ。遅延評価は真逆で、「先に関数を評価してから」必要に応じて与えられた引数を評価する。
上に挙げた関数型言語では唯一Haskell「だけ」が遅延評価を基礎として採用してるプログラミング言語だ。と言うか、知名度で言うとHaskellくらいしかないんじゃないか。
Lisp語族ではSchemeは一部遅延評価を採用してるが、厳密に言うとやっぱ遅延評価の言語ではない。データ構造を「遅延評価的に組み立てる」能力があるだけ、だ。しかしながら、Lisp語族特有の「マクロ」の正体は遅延評価方式の関数だ、と見なすことも不可能ではない。マクロも引数の評価は後回し、だからだ。しかし、ここでは特に「マクロは遅延評価方式の関数だ」とは特に強調しない事としよう(※2)。
とまぁ、質問文に登場する単語の3/4は難なく答える事が出来る。ところが、恥ずかしながら、「余再帰」っつー表現は聞いた事がない。「なんじゃそりゃ?」ってぇんで調べてはみたんだけど、これが大変だったんだ。そして結論は出ていない。
まず再帰(recursion)に対して英語では余再帰はcorecursionと表記する。日本語でも何らかの表現に対して「余」が付いた単語があるし、英語のco-と言う接頭辞もあるんだけど、良く考えてみると「余」が具体的に何を指してるのか、っつーのが良く分からん。余は之を知らぬ(謎
再帰に対して余再帰の「理論的な意味」を知る為には、まずは「余」が何を示してるのか調べなアカンのだけど、まずこれが難しい。英米のサイトも合わせて色々検索してみたんだけど、結果得られたのはまずはDualingと言う表現。日本語では双対と表現するらしい。日本語では何でも難しくなるね。
ところが、Wikipediaの説明では説明になってない。いや、「言葉の意味」は解説してんだけど、列挙されてるのは単なる「双対と考えられる」例なだけだ。言わば、国語辞典的な説明であって、数学的な定義でも何でもないわけだ。
また、次のような記述もある。
双対の双対はある意味で "元に戻る"
いやそうか?と(笑)。
ここで思いつくのが三角関数だ。語源的にはsin(正弦)に対してcosine(余弦)なわけだが。
当然ながらθ = cos(sin(θ))なんつー素っ頓狂な計算は成り立たない。cosineはsinの双対か否か。いや、双対じゃないのかもしんない。じゃあ、余弦の「余」(英語ではcosineのco)は一体何なんだ、ってな話になる。
もうこの辺で混乱してた。「双対」の定義が数学的な意味では曖昧で、「恣意的に選んだ組を双対と見做す」のなら一般論は出来ない。つまり「再帰」に対して「余再帰」がこれ、たぁ言えない。なら理論的な話は出来ないわけだ。
この「余再帰とは何か」と言う理論的な説明、っつーのは海外のサイトも探したんだけど、「全く見当たらない」んだよな、困った事に。とある説明では再帰は帰納法だけど余再帰は演繹法だ、とか書いてたんだけど、なんのこっちゃ、だ。それって単に「逆」だろ、ってなだけの話じゃないか?
いや、事象的に結論は分かったんだけど、「何故にこれをそう呼んでるんだか」と言う理由がサッパリ分からんのだ。
関数プログラミング言語では、分かった範囲で言うと、「余再帰」は直接unfold関数を指す、って事になってるらしい。
しかし、これがまた厄介なんだ。
もう、このブログを読んでる人にはfold関数自体はお馴染みだろう。単純なカタチではコールバック関数、シード、リストの3つを引数に取り、リストを処理しながらシードをコールバック関数で延々と加工していく。「畳み込み関数」と呼ばれるfoldだが、別名reduceとも言い、Pythonでも最重要関数だ、と言う話は何度もした。
繰り返すが、reduceを使えなければPython初心者を脱却した、とは言えない。
それほど重要な関数だ。
しかし、ここが問題だ。
英語のサイトを含め、unfoldはテーゼ的には、
- fold に unfold を適用すると元に戻り、ある意味、unfold は fold の逆演算だ。
なんつー事が書いてある・・・しかし「元に戻る」ってのが意味不明だ。
上で見たように、fold/reduceは最低でも機能的には三引数関数だ。じゃあ、何らかのデータを受け取った場合、「元に戻る」っつーのは、この三引数を「すべて復元する」事にならんのか。そんな事は可能ではないだろう(そして技術的にはunfoldは多値関数である必要性が生じる)。
つまり、ここでも余再帰の「余」、英語だとco-が一体何を指してるのかサッパリ分からんのだ(ついでに言うと、unfoldのun-が何を指してるのかさえハッキリしない)。言い換えるとunfoldの実装を読んでそれ自体を理解するこたぁ全然可能なんだけど、それをもってしても「余」の意味を明示してる理論的根拠が全く無い、って事だ。
ホント曖昧だ。海外のサイトも色々と調べまくったんだけど、「foldとunfoldは云々」と能書きは垂れてるんだけど、「unfoldが何故に余再帰なのか」と言う理論的根拠は書かれてない。また、これも考えてみれば当然なんだが、foldそのものが再帰を表してるわけでもない。foldは単に再帰を使った関数に過ぎない。
結果、調べたすべてのサイトでunfoldの実装法の紹介だけ、で落ち着いている。それが結論だと言わんばかりに。
しかしそれでもまだ問題があるんだ。例えばfold/reduceに関して言うとこれに関するフォーマットは、これを実装可能なプログラミング言語で形式はほぼ全て同じだ。ところが、unfoldに関して言うと得られる結果は同じなんだけど、「関数のフォーマット」が言語によってマチマチだ。大きく分けると2つ存在し、一意に決まってるわけではない。っつー事は一般論がやっぱり展開しづらい。
加えると、foldとunfoldの関係が云々、って言ってるが、原則この2つの関数が扱う引数が違う。あるいは、引数の形式が違うんだ。と言う事はなんだかんだ言って対称性が崩れてる。これはかなりキモいんだよ。そして「そうなるべきだ」と言う理論的な根拠が結果得られなかった、と言うわけだ。
とまぁ、確かに実装だけ注目すれば「こんな風にunfoldを実装すればいい」とか言うのは簡単だ。が。
ここまで余再帰関数unfoldってどんな機能の関数なんだ?ってのに付いては全く触れてこなかった。「余再帰」と言う言い回しにこだわってきたから、だけど、実は余再帰、と言う単語さえ忘れちまえばこいつが持ってる「効果」自体は簡単に説明可能だ。
平たく言うと、unfoldと言う関数はPythonのrange、あるいはSchemeのSRFI-1のiotaの高階関数版だ。要は豪華版range、とか豪華版iotaだ、って言っちゃえば説明はオシマイ、になる。
そう、数学/合理的根拠を排すれば大した事がない関数なんだ。
ここで遅延評価方式の参照透過な関数型言語、と言うフレーズに敬意を払って、Haskellでの定義を見てみよう。
unfoldr :: (b -> Maybe (a, b)) -> (b -> [a])
unfoldr f b = case f b of
Just (a, b') -> a : unfoldr f b'
Nothing -> []
これはPythonに直訳すると次のような定義になる(Haskellのコードの一行目は、静的型付け言語であるHaskellに於いての型変換の説明だ)。
def unfoldr(f, b):
match f(b):
case a, b:
return [a] + unfoldr(f, b)
case None:
return []
見りゃ分かるが、unfoldrも再帰関数だ。またもや「余再帰」が何を具体的に表してるかはサッパリ分からんが、一方、「余再帰」と言う単語さえ忘れれば何が行われてるか、は一発で分かる関数だ。
この実装では、関数unfoldrはコールバック関数fとシードと呼ばれるb(データ型自体は何でも良い)の2つを取る関数だ。そしてbにfを適用した結果に対して条件分岐する。
f(b)の結果が2つの数値のペア(タプル)だった場合には、再帰計算を行い、Noneだった場合は空リストを返す・・・って事はコールバック関数fは条件によってタプルを返すかNoneを返す関数だ、って事になる。
ちと例を見てみよう。
>>> unfoldr(lambda b: None if b == 0 else (b, b - 1), 10)
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
この例の場合、コールバック関数はラムダ式で与えてるが、意味は引数bが0の時はNoneを返し、そうじゃなければタプル(b, b - 1)を返せ、と言ってる。
このタプルの意味だけど、第0要素はbに関する演算(この例の場合は「何もしない」)、そして第1要素はbを順次「何で置き換えるか」指定してる。このケースはbから1づつ引いていけ、って言ってるんで、結果シードである10は9 -> 8 -> 7 -> 6 ...と更新され、結果上のようなリストが結果として返されるわけだ。
このコールバック関数の返却値であるタプルをどう書くのか、ってのがこのヴァージョンのunfoldrを使うポイントとなる。
### 2 乗のリスト 1^2 ... 10^2>>> unfoldr(lambda x: None if x > 10 else (x ** 2, x + 1), 1)
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
このunfoldrがあれば、rangeは次のように書ける。
def xrange(*args):if len(args) < 4:
match args:case start, stop, step:
return unfoldr(lambda x: None if x >= stop else (x, x + step), start)
case start, stop:
return xrange(start, stop, 1)
case stop,:
return xrange(0, stop, 1)
match文で引数が一つ、を想定する場合、stop,と「コンマ付き」で記述しないと可変長引数であるタプルそのもの、と解釈されてバグるが、そこさえ気をつければrangeを書く事自体はさほど難しくない。
いずれにせよ、range、あるいはiotaの類は高階関数unfoldの下位互換だ、って事が分かるだろう。
ちなみに何度か言ってるが、Pythonは再帰が苦手だ。よって実用的には、unfoldrを次のように書くべきだろう。
def unfoldr(f, seed):
acc = []
while True:
match f(seed):
case a, b:
acc.append(a)
seed = b
case None:
return acc
この定義だと、リストaccに対し、初心者に「使うな」と提言したappendメソッドを使っている。破壊的変更だ。
ただし、リストaccは関数unfoldrの内部にのみ存在し、外部から、例えば引数として与えられたモノではない。と言う事は外部の存在に対して破壊的変更を行ってるわけじゃない。
ある関数内部「だけ」に変数(リスト)が存在し、外部に何の影響もない場合、こういう破壊的変更を行っても良いケースとなり、少なくともこのunfoldrを「使う」事自体は関数型プログラミングを逸脱しない。
言い換えると「外部にバレなければ」内部でオチが付く以上、破壊的変更をしても構わない、と言ったレアケースとなる。結果ガベージコレクタが走らないんで、効率が良くなる、って寸法だ。
こういうカンジで「データの破壊的変更」には使いどころがある。無闇矢鱈に使っちゃダメなだけだ。
なお、もっとPythonらしく、unfoldrをイテレータとして実装する事も可能だろう。
class unfoldr:
def __init__(self, f, seed):
self.f = f
self.seed = seed
def __iter__(self):
return self
def __next__(self):
match self.f(self.seed):
case a, b:
self.seed = b
return a
case None:
raise StopIteration
イテレータとして実装するのは大仰しく見えるが、実際は、__next__メソッド実装の内情自体はwhile採用版のロジックとほぼ変わらない。違うのはコールバック関数がNoneを送り込んで来た時、StopIteration例外を投げる辺りだ。これはunfoldrがどーの、と言うより、Pythonでイテレータを書く際の決まりごとと言って良い。
>>> for i in unfoldr(lambda b: None if b == 0 else (b, b - 1), 10):
print(i)
10
9
8
7
6
5
4
3
2
1
これでPythonでもrangeと言うイテレータの上位互換としてunfoldrを使う事が出来る。
上のunfoldrの定義がHaskell及びOCamlなんかでの定義となる。
ところが。
Schemeなんかの、正確にはSRFI-1のunfoldの定義は見た目がかなり異質だ(※3)。
こんな風な定義になっている。
なんじゃこりゃ?ってなカンジだ。
高階関数は高階関数だけど、コールバック関数が3つもある、なんつーのはかなり異質に見える定義だ。
要はHaskell/OCaml版で与えるラムダ式の停止条件と返り値のタプルをバラバラにして与えるような記述になっている。
キモい(笑)。
Pythonで書くと次のような定義になってる、って事だ。
def unfold(p, f, g, seed, tail_gen = lambda x: []):
if p(seed):
return tail_gen(seed)
else:
return [f(seed)] + unfold(p, f, g, g(seed))
コールバック関数を3つも取る(オプショナル引数tail_genも含めると4つも取ってる!)、って事は使う時には次のようにして使う、って事になる。
### 2 乗のリスト 1^2 ... 10^2>>> unfold(lambda x: x > 10, lambda x: x ** 2, lambda x: x + 1, 1)
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
これはマジで相当キショい(苦笑)。
もう一つ不思議なのは、今まで名称的にはunfoldrを使ってきた。この末尾のrと言うのは「リスト生成は右から」を意図してる筈で、Schemeで初めてunfold、つまり「生成は左から(つまりそれが標準)」なんだけど、実はHaskell/OCamlのunfoldrとSchemeのunfoldの計算結果は全く一緒、つまり(Scheme/SRFI-1の)unfold = (Haskell/OCamlの)unfoldr、と言うワケの分からん事になってんだ。
事実、SRFI-1には別にunfold-rightなる関数が定義されてるが、内情を見てみるとHaskell/OCamlなんかのunfoldrとは違う。実際、計算させてみるとHaskell/OCamlのfoldrとSRFI-1のunfoldは同じ結果を返すが、SRFI-1のunfold-rightは返すリストが逆順になっている。
Haskellのunfoldr
Haskellと同じ計算結果を返すのはSRFI-1のunfoldであって、unfold-rightではない。
どっちが実装として「正しい」のかは知らない。上に書いてきたけど、そもそもこのテの関数じゃなければならない「理論的根拠」が全く見つからないからだ。よって「左」と「右」が何を指してるのか、それを裏付けする根拠がどうなのか、がサッパリ分からん。
いずれにせよ、Scheme/SRFI-1版unfoldを、例によってPythonは再帰が苦手なんで、Pythonっぽく書き直すと次のようになるんじゃないか。
def unfold(p, f, g, seed, tail_gen = lambda x: []):
acc = []
while True:
if p(seed):
return acc + tail_gen(seed)
acc.append(f(seed))
seed = g(seed)
個人的にはHaskellやOCamlで扱われてる定義の方が好きだ。また、こういう風に「関数の形式のコンセンサスが得られてない」辺りが、fold/reduceに比べて、unfoldがイマイチマイナーの原因な気がしてる。
さて、ではunfoldの使いどころは一体いつなんだろうか。
例えば、とある英語のサイトではfoldとunfoldの組み合わせで階乗を計算する例が挙げられてはいるが・・・・・・。
# Pythonでの例def fact(n):
return reduce(lambda x, y: x * y, unfoldr(lambda x: None if x == 0 else (x, x - 1), n), 1);;; Schemeでの例
「再帰と余再帰の組み合わせ」と言うテーゼらしいが・・・・・・。理論的にはともかく、正直「嬉しいか?」とか思ってしまう。
実際、僕を含めた殆どの人だと、「同じfold/reduceを使う」なら直接range関数(はunfoldから形成可能だとしても)を埋める事を思いつくだろうし、そっちの方が自然だと思える。
# Pythonでの例def fact(n):
return reduce(lambda x, y: x * y, range(1, n + 1), 1);;; Schemeでの例(define (fact n)
(fold (lambda (y x) (* x y)) 1 (iota n 1)))
上の方に、「unfoldは高階関数版range」とか「unfoldはrangeの上位互換」とか書いたんで、rangeがunfoldを置き換える能力がある、ってのは薄々分かると思う。
もっと言っちゃうと、プラクティカルな意味では、「unfoldはrangeにラムダ式をmapしたもの」と捉えられる事が出来る。与えるラムダ式の形式は違っても、ほぼ次のような意味になるんだ。
unfold ≒ map(lambda x: ..., range(n))
実際問題、関数型言語でさえunfoldがそんなに有名じゃないトコを見ても、要は代替手段がポピュラーかつ豊富で誰も困らん・・・そんなトコがunfoldがメジャーになりきれない一要因なのかもしれん。
しかし、もっと困るのが、「使いどころが分からん」って事は練習するチャンスがなかなか無い、って事だ。
元々、「プログラミングの教科書」を名乗る書籍はクソ本の方が多く、と言う事は「良い練習問題」に会うこと自体が少ない。
「良い練習問題が元々少ない」クセに「マイナーな関数言語の機能」を練習出来るようなネタがそもそもあるんか・・・・・・?
とか考えていたら思いついた。だいぶ前にPythonのリスト内包表記で無理矢理C言語の反復の練習問題を解く、ってネタを書いたが。
あの実験で、range関数を使わざるを得ないリスト内包表記の使用法、ってのが平たく言えばunfold向けのネタだろう。
なお、Pythonコードで使うunfoldrは、イテレータ版、とする。
問題自体はここにあるんで、挑戦してみて欲しい。23問も解こうとすれば自ずから「形式」には慣れるだろう。詰まったとしても、詰まった問題をスルーして最後まで挑戦してみて欲しい。別に後の問題程難しいと言うわけじゃない。そして「詰まった」場合、それはunfold向けの問題じゃない、ってのが背景となる。つまり「いつunfoldが使えていつそうじゃないのか」を見抜く目が養えるだろう。
回答例は以下に挙げておく。
さて、驚くべき事に気づくんじゃないか。元々C言語の「反復」をテーマとした問題を関数型言語形式で解こう、と言うネタになるんだが、このケースで言うとunfoldの適用範囲は幅広いんだ。リスト内包表記で解くには苦しい問題もunfoldだとさほどでもない。
ただし、それでも上記23問中、unfoldで解くには適さない問題もある。回答例で言うと、中で破壊的変更を目論まないと解けない問題は本質的にはunfold向けじゃない。これは「関数型プログラミング」の観点から見れば当然だろう。
しかし、この23問を、リスト内包表記/map、fold/reduce、unfoldの3つを使い分けて解けるようになれば相当プログラミングの実力が付いた、って事だ。また「使い分け」を見極める目も育つと思う。
逆に言うと、その「使い分け」を知る為にギリギリを攻めよう。「なんとでもやりようがある」と言うのは、選択肢が増えた、と言う事だ。「このケースだとこれは使わずにあっちを使おう」と思えるのは「ギリギリを攻めた」経験があるから、なんだ。
個人的に上の問題を解いてみたら、やっぱりSchemeのSRFI-1のunfoldは使いづらいと言う感想だ。「コールバック引数を3つ取る」と言う形式は、お互いに連携が取れない、と言う事を意味する。何故なら、それぞれのコールバック関数がそれぞれのスコープを持つので、内部的に変数を持たせたい、なんて言った場合、お互いの「通信」が出来ないんだ。
一方、Haskellスタイルならスコープが一つなんで、ちょっとしたトリックを仕込む事も容易い。
いずれにせよ、ちとSRFI-1のunfoldは設計ミスなんとちゃうんか、ってのが正直な感想だった。
また、unfoldの弱み、は、「リスト生成機能」ってのが目的なんでしゃーないが、フィルタリング機能がない、ってのが弱点だな、とも思った。特にコード的に難解になるのが素数絡みで、特に因数分解、なんつーのは「リスト生成機能」があっても記述がメンド臭い。結果的にコールバック関数にC言語的発想で反復を組み合わせないと処理が不可能なんで、末尾再帰だろうと何だろうと、あまり美しくない結果となる。
そもそもこのテの高階関数は「反復を書きたくない」から使うわけで、反復を仕込まないと解けない、ってのは本末転倒と成りかねない。多分上記の23問の中では最高の難易度となるだろう。
尤も、SchemeやPythonは無限長の素数列を実装可能なんで、やりようによってはもっと簡単に書けるかもしれないが、あんま期待できそうもない(そもそも、与えられた数をどんどん割っていく、と言うネタな以上、原理的に破壊的変更が避けられないんじゃないか、多分)。
どのみち、「素因数分解」と言うネタはストレートな「反復」以外だと上手く書くのが難しいテーマのような気がしてる。
さて、残りは余談と言えば余談だ。談に対しての双対だからco-talkだ(違
高階関数fold/reduceやunfoldはリスト絡みの関数だ。
一方、理論屋(笑)はこれの「二分木対応ヴァージョン」の素晴らしさを力説する。
SchemeもPythonも二分木をビルトインで扱う機能を持ってないんで、ピンと来ないんだけど、「関数型言語」の理論屋連中はその素晴らしさを強調する(笑)。
一方、例によって「これ」と言った決定的な、一般化出来る「実装」は存在しない。結果は同じもの、を意図してても、実装が違う。
ここではHaskellで木を扱うData.Treeモジュールで定義されている関数の実装を基として話を展開してみよう。また、木は構造体やオブジェクトで実装する例も多いが、簡易性と関数自体に注力する為にリストで二分木を作る前提とする。
関数unfoldTreeはunfoldrと同様に、コールバック関数とシード、と呼ばれる値の2つの引数を取り、二分木を生成する。Pythonで書くと次のような関数となる。
def unfoldTree(f, b):
match f(b):
case a, bs:
return [a, [unfoldTree(f, b) for b in bs]]
これはもっと「フツーの」再帰関数で書かれる例として紹介される事が多いが、Haskellのビルトイン関数として定義されてる関数は、「再帰関数を使ってリストをマッピングする」と言う離れ業で定義されている。ハッキリ言って「非常に非効率な」関数だ(笑)。
これがHaskellで問題にならんのは、Haskellは「遅延評価ベースの」プログラミング言語だから、だ。Pythonのようなフツーの「先行評価」の言語と違って、「必要に応じて引数を評価する」システムを採用してる為、フツーに再帰してもHaskellでは問題にならない。
与えるコールバック関数は「どういう二分木を生成するのか」そのルールを与える事となる。
例えば、
def buildNode(x):
return (x, []) if 2 * x + 1 > 7 else (x, [2*x, 2*x + 1])
と言う関数でルールを与える。xが与えられた時、2 * x + 1が7より大きければ(x, [])になり(つまりここが終了条件)、そうじゃなければ(x, [2*x, 2*x + 1])と言うノードになる、とする。
シードとしてunfoldTreeに作ったコールバック関数と共に1を与えると、次のような二分木を生成する。
>>> unfoldTree(buildNode, 1)
[1, [[2, [[4, []], [5, []]]], [3, [[6, []], [7, []]]]]]
これは次のような二分木を表している。
気をつけて欲しいのは、unfoldTreeが生成する二分木は単なる二分木であって、いつぞや見せたような平衡二分探索木を生成するわけではない、と言う点だ。コールバック関数で与えられた「木の生成ルールに従って」粛々とシードから二分木を生成してるだけ、だ。
ここでも、実装はさておき、機能的にはunfoldTreeはrangeの亜種だ、と見る事が出来る。rangeと違うのは、シードに対して常に2つの値を生成している辺りだ。
1を与えるとコールバック関数に従って、2 * 1 + 1は7以下なんで、1に対して2 * 1 = 2と2 * 1 + 1 = 3 の2つの値を生成し、なおかつ[1, [2, 3]]と言うリストを生成する。
次は、2を対象にして2 * 2 + 1をチェック。7以下なんで2を対象にして2 * 2 = 4 と 2 * 2 + 1 = 5を生成して[1, [[2, [4, 5]] , 3]]になる。次は3を対象にするわけだが、ここでの「二分木生成」の順番はいつぞや見た通り「幅優先探索」の順序となる。2 * 3 + 1 は7以下なんで3を対象にして2 * 3 = 6 と 2 * 3 + 1 = 7の2つを数値を生成し、[1, [[2, [4, 5]] , [3, [6, 7]]]] が出来上がる。次は2 * 4 + 1 > 7で4で、打ち止め、2 * 5 + 1 > 7 でこれも打ち止め、 2 * 6 + 1 > 7 でこれまた打ち止め、 2 * 7 + 1 > 7 も打ち止め、結果、4、 5、 6、 7の4つの数値はこの二分木の「葉」(子供がない)となる。
最終的には [x, []] と言う葉の表現に従って、 [1, [[2, [[4, []], [5, []]]], [3, [[6, []], [7, []]]]]] と言う(リストによる)二分木表現になるわけだ。
なお、Schemeは、いつぞやも書いたが、SRFIをひっくり返しても「木」に関してのライブラリが見つからなかった。Schemerは木が嫌いなのか(笑)。もちろん、Racketのユーザー側から木に関するRacket用のライブラリが提供されてはいるが、本体では木に付いては何も提供されていない。と言う事はSRFI-1のリスト用のunfoldと違い、自作する必要性が出てくる。
(define (unfoldTree f b)
(match-let ((`(,a ,bs) (f b)))
`(,a ,(map (lambda (b)
(unfoldTree f b)) bs))))
もう一度言うが、unfoldTreeはシードから設計図としての「コールバック関数」に従って二分木を生成する。
そして、理論がハッキリせんので、「対になってる」って言って良いのかどうか知らんが、実はunfoldTreeに対して「二分木を畳み込む」foldTreeと言う関数もある。
しかし、このfoldTreeもまたもや、「一般的にどんな形式を持ってるのか」サッパリ分からんのだ。
良くあるパターンとしては次のような形式を持ってるモノが想定されてるらしい。
foldTree(コールバック関数1, コールバック関数2, 二分木)
コールバック関数が2つある、って事はちとSchemeのSRFI-1のunfoldに近い。
1つ目のコールバック関数は「どう畳み込むのか」を指定する。一方、通常のリスト用foldと違って、第二引数は「初期値」ではなく、コールバック関数で、これは二分木の葉に到達した時にその葉に対してどういう演算をするのか指定するモノだ。そして第三引数にデータとしての二分木を取る。
ただし、これがポピュラーとは言え、Haskell組み込みのfoldTreeはコールバック関数と二分木の2つしか引数を取らない。Haskellの場合、「葉に到達した時何をするか」もコールバック関数一個で指定する方針のようだ。
Pythonでは次のような定義になる。
def foldTree(f, tree):
def go(node):
match node:
case x, ts:
return f(x, [go(child) for child in ts])
return go(tree)
Racketだと次のような定義だ。
(define (foldTree f tree)
(define (go node)
(match-let ((`(,x ,ts) node))
(f x (map go ts))))
(go tree))
ローカル関数goを設定し、そのgoを再帰呼び出しで二分木の子部分にマッピングしていく、と。
これも通常の高階関数の使い方に比べると極めて仰々しい。
foldTreeの使用例は以下のサイトに貼っておこうと思う。
- unfoldTreeとfoldTree(Python版)
- unfoldTreeとfoldTree(Racket版)
しかし、ちょっとだけfoldTreeとunfoldTreeの組み合わせ例を解説してみよう。
繰り返すが、unfoldTreeはコールバック関数の指示に従ってシードから二分木を生成する。
ここで次のようなコールバック関数を想定する。
# Pythondef g(n):
match n:
case 0:
return (0, [])
case 1:
return (1, [])
case n:
return (n, [n - 1, n - 2]);;; Racket(define (g n)
(case n
((0) '(0 ()))
((1) '(1 ()))
(else `(,n (,(sub1 n) ,(- n 2))))))
「何かどっかで見た定義やな・・・」
と既視感を覚える人もいるだろう。それは恐らく正しい。あなたの考えてる通りだ。
いや、オチを言うと間違いなくこれはフィボナッチ数列の定義に近い。返り値が違うだけ、なんだよな。
これを「二分木生成の設計図」として、例えばシードを5としてunfoldTreeに渡すと次のようになるんだ。
# Python>>> unfoldTree(g, 5)
[5, [[4, [[3, [[2, [[1, []], [0, []]]], [1, []]]], [2, [[1, []], [0, []]]]]], [3, [[2, [[1, []], [0, []]]], [1, []]]]]];;; Racket> (unfoldTree g 5)
'(5
((4 ((3 ((2 ((1 ()) (0 ()))) (1 ()))) (2 ((1 ()) (0 ())))))
(3 ((2 ((1 ()) (0 ()))) (1 ())))))
これは次のような二分木を表している。
「だから何だ?」って思うだろう。二分木として見ると単に「データの重複ばっかの」役立たない二分木に見える。全くそうだ。
しかし、これが意味してるのは、実はフィボナッチ数列、と言うのは二分木的な数式だ、って事なんだ。
SICPで言うトコの木構造再帰ってヤツだ。
しかし、unfoldTreeで得られた二分木は「項」がどんな二分木を形成するのか、を指してるだけであって「計算結果」ではない。
つまり、項と項の関係に付いて述べてるだけで、実際的な意味がない。
ところが、この「unfoldTreeで作り出した二分木」にfoldTreeを使って新たにコールバック関数を適用すると、見事フィボナッチ数を計算するわけだ。
# Python>>> foldTree(lambda x, xs: x if xs == [] else sum(xs), unfoldTree(g, 5))
5;;; Racket
> (foldTree (lambda (x xs)
(if (null? xs)
x
(apply + xs))) (unfoldTree g 5))
5
確かに 0, 1, 1, 2, 3, 5, ... と言うフィボナッチ数列に対して5項目は5になっている(0から数える、事に留意する事)。
しかし一体、上の計算は何をやってるのか。
実はこのfoldTreeとunfoldTreeの組み合わせは、unfoldTreeが形成したフィボナッチ数列の項の二分木の葉の数を合計してるんだ。
具体的に見てみよう。fib(5)の二分木の葉の個数は8個だ。内訳は左からピックアップして加算していくと、
1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5
となって、結果fib(5)の答えが5になるわけ。
もうちょっと具体的に見てみよう。
まず、foldTreeに与えるコールバック関数に着目する。
# Pythonlambda x, xs: x if xs == [] else sum(xs)#Racket:(lambda (x xs)
(if (null? xs)
x
(apply + xs)))
ノード(節)は [x, xs] あるいは '(x xs) と言うリストで与えられ、xは親、xsは子と解釈される。
上のコールバック関数はノードが(子を持たない)葉の時に親を返し、そうじゃなければ子の総和を求めろ、と言っている。言い換えると、計算上重要なのは「子の総和」であり、親自身は葉以外では使われない・・・具体的に、上のフィボナッチの二分木で言うと、ノード上の値である2、3、4、5は事実上捨てられてて、0と1しか計算には使われないんだ。
次に、unfoldTreeが幅優先探索的に二分木を生成するのに対して、foldTreeは深さ優先探索的に二分木を畳み込む。
その経路は大雑把には次のようになる。
もちろん、各ノードを訪れてはいるが、「葉の数を拾う経路」はこのようになってる、って事だ。
そして、各ノード上でノードの値(親の値)を使わず「子の合計」を計算する。
例えば出発点のルートでは[5, [[4 ...], [3 ...]]]あるいは(5 ((4 ...) (3 ...)))と言う状態で子ノードは空じゃない。よって親の値5を捨てて子の総計を得ようとするが、子も二分木の状態だ。
ここで [4 ...] あるいは (4 ...) に対しても同様な事を行おうとする。そうだな、再帰だ。そして子に対しても同様に・・・とやっていく。
この時点で、最初の葉を見つけるまでには一番左のルート、
5 -> 4 -> 3 -> 2 -> 1
と手繰って行って葉の値1を得る。次に2に戻ってもう一つの子である葉の値0を得る。
5 -> 4 -> 3 -> 2 -> 1
| -> 0
得られたリストは [1, 0] あるいは (1 0) で、ここで和を求めて1となる。
次には3へと戻ってもう一つの子、1へ入っていって、これが葉なんで1を得る。
5 -> 4 -> 3 -> 2 -> 1
| | -> 0
| -> 1
そして3に戻った時点で先ほどの計算結果を合わせるとリスト [1, 1] あるいは (1 1) を得て和は2となる・・・と言うような計算を全てのノード上で行っていくわけだ。これがリストに於いての「畳み込み」と非常に良く似てるわけだ。
それで理論屋が、
「どうだ、凄いだろ?」
ってドヤ顔になるわけだな(笑)。
・・・・・・うん、まぁ、「理屈として」面白いっちゃあ面白いんだけど、実用考えたらフツーに末尾再帰書いて計算させた方が速いし良くないか?とか僕なら思っちゃうよな(笑)。
まぁ、この辺の理論って好きな人は好きなんだろうなぁ、っつー・・・(苦笑)。
おまけだよ、おまけ(笑)。
でも「データをリアルタイムで生成していく」って観点自体は面白いたあ思うよ。ちょっと使いどころに悩みそうだけどね。
いずれにせよ、これらが実装的な意味での「余再帰」だ。
今回はこれで「余再帰」の紹介は終了、とする。気になった人は役立てるとか自分で勉強してみる、とかしてくれ。
以上。
※1 と言うのも、ANSI Common Lispのマクロは「コンパイラへの指示」と言ってよく、事実上、通常で言う「プログラミング」ではなく、通常のプログラミング言語が提供する「レイヤー」より下のレイヤーを弄ってるのに等しい。つまり、フツーのソースコードを「変換」して「最適化」する必要が生じるから、だ。
言い換えると、ANSI Common Lispのマクロはその性質上、例えばC言語で書いたソースコードを「コンパイル」した時点でのコード上の「冗長な表現」を高速化するコンパイラの「作業」を「直書き」するに等しい。
ちなみに、高級言語として「関数型言語」があったとしても、それがコンパイルして生成したアセンブリやバイトコード自体が「参照透過性」で書かれてるわけではない。
※2: 以前書いたが、過去のLispではユーザーが先行評価の関数と遅延評価の関数の2つを自在に使えるモノもあった(Lisp-81とか)。そういうLispでは例えばsetqは遅延評価で定義された関数だった。
※3: SRFI-1は個人的にも良く使うライブラリだし、unfoldの存在は知ってはいたんだが、実はこれまで一回も使った事がなかった。
