メモ化(memoization), 再帰関数定義関数, 最小不動点

language

inabaさんによる。ふむふむ。ではPerlでも書いてみましょう。

# http://www.kmonos.net/wlog/52.php#_0308050827 を参考に。
use strict;
sub fib_maker {
    my $f = shift;
    return sub {
        my $x = shift;
        return $x <= 1 ? 1 : $f->($x - 1) + $f->($x - 2);
    }
}
sub fix {
    my $G = shift;
    return $G->(
        sub {
            my $x = shift;
            return fix($G)->($x);
        }
    );
}
my $fib = &fix(\&fib_maker);
for my $x (1..5) {
    print $fib->($x), " ";
}
# -> 1 2 3 5 8

眠い。「メモ化」は誰かやって。
追記(2005-08-31):Hiroto Inabaさんが作ってくださいました。

追記(2005-09-01):Hiroto Inabaさんは、kMonos.NETのK.Inabaさんとは別の方でした。おわびして訂正します。
追記(2006-04-16):Danさんの「TuringとChurchの狭間で」で「hyukiさんも知らぬ間に一つ「反則」を犯している」とご指摘を受けました。大感謝！