Blog

Perl6 のフィボナッチ数列生成についての解説

mattn ブログで紹介されている Perl6 のフィボナッチ数列が奇妙に見える人が多いようなので、まともな解説。

ref. http://mattn.kaoriya.net/software/lang/perl6/20151026144119.htm

フィボナッチ数列とは以下のような数列です。

1, 1, 2, 3, 5, 8, 13, 21, 34, 55

最初の2つの数字が 1, 1 でして、その後のものは直前2つの数字を足したものです。

よって、Perl5 で記述した場合、先頭10個のフィボナッチ数列を求めるには以下のようになります。

use v5.16.0;

sub fib {
    state %memo; # 一応 memoize ぐらいはしておく

    my $n = shift;
    $memo{$n} //= do {
        if ($n == 0 || $n == 1) {
            1
        } else {
            fib($n-1) + fib($n-2);
        }
    };
}

sub fibs {
    my $n = shift;
    map { fib($_) } 0..$n;
}

say join(', ', fibs(10));

ですが、Perl6 では無限数列を扱う機能が充実しているため、こういったものは非常に単純に記述できます。

Perl6 での書き方を解説しましょう。

まず、先頭の数列を用意します。

1, 1

次に、続きは一つ前の項目と2つ前の項目の和であることを示します。

1, 1, -> $a, $b { $a + $b } ...*

ここで、-> $a, $b { $a + $b } はラムダ式です。これは ES6 などのものと同じですね。 ...* というのは、数列が続くことを示し、* は無限大を表します。こうすることで無限に続く数列を表すことができるのです。

Perl6 では、2項のラムダは * + * のように省略できるのでこれは

1, 1, *+* ...*

と表記することができます。

ここから、先頭10個を取り出すには

my @a = (1, 1, *+* ...*);
say @a[0..9];

また、レンジの右辺は ^10 のようにすれば「10は含まない」つまり「0~9」のレンジを作ることができるので、以下のように表記できます。

my @a = (1, 1, *+* ...*);
say @a[^10];

これをまとめると以下のようになります。

say (1, 1, *+* ...*)[^10];

ま、そんな感じです。