Perl6: Van Eck 數列產生器

幾周前的 Perl Weekly Challenge #14.1 裡的一題，是寫個能產生出 Van Eck 數列的程式。果不其然，這也是個有在 Numberphile 裡有介紹到的數列。Numberphile -- Don't Know (the Van Eck Sequence) 、 OEIS/A181391。

這個數列的第一項為 0，之後的每一項的計算公式，是將目前項數減去前一項數字在前一次出現時的項數。

a[1] = 0
a[n+1] = 0, 若 a[n] 不存在於 a[0..n] 之中
a[n+1] = n - m, 其中 a[m] = a[n] 且為最大者

也就是說，要求 a[n+1]，必需向前回溯，找出 a[n] 前一次出現的地方。

~laurent_r 在其部落格上提供了迴圈解：

use v6;

my @a = 0,;
for ^20 -> $n {
    my $result = 0;
    for reverse ^$n -> $m {
        $result = $n - $m and last if @a[$m] == @a[$n];
            # Note: $m is always smaller than $n, so $n - $m > 0
    }
    push @a, $result;
}
say @a;

我則想試著做出可惰性求值、無限產生下去的物件。最後的成果如下：

my $vaneck = Seq.new(
    class :: does Iterator {
        has %!seen is default(-1);
        has Int $!term = -1;
        has Int $!pos  = 0;

        method pull-one {
            my $next = %!seen{$!term} == -1 ?? 0 !! $!pos - %!seen{$!term};
            %!seen{$!term} = $!pos++;
            return $!term = $next;
        }
    }.new()
);

其中 Seq 與 Iterator 都是 perl6 中原有的型別。我以 %!seen 這個私有變數去記錄「前一次」見到每一項數字是在何時。

如此做則能印出前 200 項：

$vaneck[^200].map({ .say });