星田さんの記事に対するコメント。
なるほど、もしかしてReduce（減らす）って冗長な関数の適応を減らすからって理由でのネーミングなのか！
そうそう、reduction、つまり縮小とか縮図とか、そう言った意味でしょうね。
英語的にもfoldingと意味的には近い、と言うか。
うまく説明出来ないんだけど、Foldの使用上の仕組みとしては「そーゆーもんだ」と理解できるんですが、内部の仕組みとしての動きがスッキリしてなくて
うん。
ちなみに、原理的にはfoldlは末尾再帰でfoldrはそうじゃない。つまり計算コスト自体はfoldrの方が「かかる」ってのをまずは押さえておく(末尾再帰でfoldrを書いてもリストを反転させるにはやっぱコストがかかる)。
Scheme/Racketだと末尾再帰は最適化出来る。要するにPythonみたいなフツーの言語だとwhile文で書いても効果は同じだ、ってことですよね。
敢えてPythonでfoldlを見ると、結果、
def foldl(f, base, lst):
while True:
if lst == []:
return base
base = f(lst[0], base)
lst = lst[1:]
って書いてるのと同じです。
末尾再帰を見た時、分かりづらければwhile文に置き換えてみる、ってのは良い訓練だと思います。これは練習の為の練習、ではなく、末尾再帰最適化を可能とするインタプリタ/コンパイラが「事実上やってる」ことです。
それは「ソースコードレベルの変換」ってことを意味してないんだけど、バイナリレベルでインタプリタやコンパイラがやってることで(※1)、これが出来るからこそ「末尾再帰最適化」と言う機構が保証されている、ってことです。
一方、foldrは原理的には末尾再帰じゃない(これは「書けない」って言ってるわけじゃない)。
foldrの基本的な書き方は
(define (my-foldr f base lst)
(if (null? lst)
base
(f (car lst) (my-foldr f base (cdr lst)))))
なんだけど、基本的な構造は実は基礎的なmapの定義に近いです。
(define (my-map f lst)
(if (null? lst)
lst
(cons (f (car lst)) (my-map f (cdr lst)))))
ほっとんどそっくりさんだ!
んで、こういう場合、trace辺り使ってまずは実際に動きを追ってみればいいのよね(※2)。
>(my-foldr #<procedure:+> 0 '(1 2 3 4 5))
> (my-foldr #<procedure:+> 0 '(2 3 4 5))
> >(my-foldr #<procedure:+> 0 '(3 4 5))
> > (my-foldr #<procedure:+> 0 '(4 5))
> > >(my-foldr #<procedure:+> 0 '(5))
> > > (my-foldr #<procedure:+> 0 '())
< < < 0
< < <5
< < 9
< <12
< 14
<15
15
>(my-foldr #<procedure:cons> '() '(1 2 3 4 5))
> (my-foldr #<procedure:cons> '() '(2 3 4 5))
> >(my-foldr #<procedure:cons> '() '(3 4 5))
> > (my-foldr #<procedure:cons> '() '(4 5))
> > >(my-foldr #<procedure:cons> '() '(5))
> > > (my-foldr #<procedure:cons> '() '())
< < < '()
< < <'(5)
< < '(4 5)
< <'(3 4 5)
< '(2 3 4 5)
<'(1 2 3 4 5)
'(1 2 3 4 5)
>
ちなみに、>、ってのが「増えてる」ってのは、そのレベルでの関数呼び出しが「待機状態になってる」って意味です(「再帰レベル」とか呼んだりする・※3)。
要するに引数状態で再帰関数呼び出しがかかった時に、外側の関数は「処理を終了することが出来ない」。だから再帰が最奥まで展開し終わるまで「待ち」の状態に入ってることを指しています。
んで、じゃあ、foldrがどうなっていってるのか、と言うのは、
(my-foldr + 0 '(1 2 3 4 5)) => (my-foldr + 0 (my-foldr + 0 '(2 3 4 5))) => (my-foldr + 0 (my-foldr + 0 (my-foldr + 0 '(3 4 5)))) => (my-foldr + 0 (my-foldr + 0 (my-foldr + 0 (my-foldr + 0 '(4 5))))) => (my-foldr + 0 (my-foldr + 0 (my-foldr + 0 (my-foldr + 0 (my-foldr + 0 '(5)))))) => (my-foldr + 0 (my-foldr + 0 (my-foldr + 0 (my-foldr + 0 (my-foldr + 0 (my-foldr + 0 '())))))) => とここでやっと最奥に到達 -> 定義によりlstが空リストなのでやっと最奥が0(base)を返せる => (f x y) 実行スタート! => (+ 5 0) => (+ 4 5) => (+ 3 9) => (+ 2 12) => (+ 1 14) => 15、とやっとトップレベルに戻れた!
(my-foldr cons '() '(1 2 3 4 5)) => (my-foldr cons '() (my-foldr cons '() '(2 3 4 5))) => (my-foldr cons '() (my-foldr cons '() (my-foldr cons '() '(3 4 5)))) => (my-foldr cons '() (my-foldr cons '() (my-foldr cons '() (my-foldr cons '() '(4 5))))) => (my-foldr cons '() (my-foldr cons '() (my-foldr cons '() (my-foldr cons '() (my-foldr cons '() '(5)))))) => (my-foldr cons '() (my-foldr cons '() (my-foldr cons '() (my-foldr cons '() (my-foldr cons '() (my-foldr cons '() '())))))) => とここでやっと最奥に到達 -> 定義によりlstが空リストなのでやっと最奥が'()(base)を返せる => (f x y) 実行スタート! => (cons 5 '()) => (cons 4 '(5)) => (cons 3 '(4 5)) => (cons 2 '(3 4 5)) => (cons 1 '(2 3 4 5)) => '(1 2 3 4 5)、とやっとトップレベルに戻れた!
と高階層ダンジョンに潜っていってひぃひぃしながら帰ってくるような状態になってるわけです。
なお、foldlにもtraceかけてみて動作を見てみて下さい。こっちは、再帰レベルは全く深くならず、引数同士でやりとりしてるだけ、なんで計算負荷がかかってないことがひと目で分かります。
これも「末尾再帰最適化」が成せることで、事実上「while文を書いてる」事と全く同じだ、って事がわかるでしょう。
ハンバーガーの作り方が。これはハンバーガーショップを作る時に画像表示の関数で使えそうかな、とか。
使えるでしょうね!
※1: 実際は、下部レベル、例えば仮にアセンブリ言語レベルだと「ジャンプ命令」と言われるモノに変換されている。そしてwhile文も元々はジャンプ命令を「人間に分かりやすく」高級言語で記述する為に作られた。
つまり、末尾再帰がジャンプ命令に変換可能(これが「末尾再帰最適化」)なら、末尾再帰 = whileとなるわけだ。
なお、だからこそ、gccやclang等のC言語コンパイラ実装では、言語仕様が要求しなくても、最適化オプションを施せば「末尾再帰」を最適化(つまり、「ジャンプ命令を使用した」アセンブリコード)出来るわけだ。
※2: 要(require racket/trace)。
※3: Racketのtraceでは再帰レベル2つまでは単一の > や < で表してるようで、表示されてる再帰レベルは実際の再帰レベルより浅く見える。
しかし、例えばこの例の場合、舐める対象のリストの長さが5なので、3再帰レベルしか深くなってないように見えても、実際は5再帰レベルの深さがあり、これが示す意味は、舐める対象のリストが長くなれば長くなるほど再帰レベルが深くなる、と言う事だ。
なお、ANSI Common Lispで同様の関数を書いてtraceでテストすると、非常に再帰レベルが深くなり、トップレベルの関数に近くなればなるほど「待ち」が入り、結果、実行効率が悪くなる事が視覚的によくわかる。
