なつたん

Higher-order Perlから

Chapter4は延々とイテレータについて。
自作イテレータをちょこちょこと改造していく。
イテレータを使った、mapとgrepの実装は面白い。無限ストリームにも使えそう。

Chapter5は、再帰からループの変換について。
再帰で美しく書かれているアルゴリズムを、自作スタックとGOTOでループに変えていく。それってどうよ？と思うんだが、Perlの場合は再帰よりもループの方が効率的らしい。

面白いと思ったのが2つ

・他の書籍に突っ込む
Mastering Algorithms With Perlに出てくる再帰を書き直す話。

最初：http://perl.codefetch.com/example/ht/Examples/Chap5/powerset-0?qy=%25s
最後：http://perl.codefetch.com/example/ht/Examples/Chap5/powerset-4?qy=null

再帰が無くなっただけでなく、プロタイプがすっきしりたり、for(;;)の構文が無くなってローカル変数が減ったりしている。ムックとか雑誌ならありそうだけど、普通の技術書でこういう他の書籍に出典付きで突っ込むって珍しと思った。

・再帰からループへ

sub fib {
　my $n = shift;
　if ($n < 2) { return $n }
　fib($n-2) + fib($n-1);
}

のような綺麗だけど効率の悪い再帰も、この本にかかるとこんな感じ。

sub fib {
　my $n = shift;
　my ($s1, $return);
　my $BRANCH = 0;
　my @STACK;
　while (1) {
　　if ($n < 2) {
　　　$return = $n;
　　} else {
　　　if ($BRANCH == 0) {
　　　　push (@STACK, [ 1, 0, $n ]), $n -= 1 while $n >= 2;
　　　　$return = $n;
　　　} elsif ($BRANCH == 1) {
　　　　push @STACK, [ 2, $return, $n ];
　　　　$n -= 2;
　　　　$BRANCH = 0;
　　　　next;
　　　} elsif ($BRANCH == 2) {
　　　　$return += $s1;
　　　}
　　}

　　return $return unless @STACK;
　　($BRANCH, $s1, $n) = @{pop @STACK};
　}
}

10ページ近く書けて、ゆっくりと再帰を剥がして最適化していく。わかりにくくなったよ。ママン。
興味がある人は、ここのfib-0からfib-12まで順に見てみよう。
http://hop.perl.plover.com/Examples/Chap5/

250ページを読んでまだまだ絶賛ベタ褒め中。