comment on

Background

Perl 6 introduces the series operator, infix:<...>. Its normal behavior is to acccept a closure on the right side, and executes that closure to get next value, so you could write

my @even   = 0, 2, 4 ... { $_ + 2};
my @powers = 1, 2, 4 ... { $_ * 2 };
my @fib    = 1, 1, 2 ... { $^a + $^b};
[download]

Now there's a special, "magic" behavior if the right side isn't a closure but rather the Whatever star *:

my @ints   = 1, 2, 3, 4 ... *;
my @even   = 0, 2, 4, 6 ... *;
my @powers = 1, 2, 4, 8 ... *;
[download]

The spec says about that operator

If the right operand is * (Whatever) and the sequence is obviously arithmetic or geometric, the appropriate function is deduced:
1, 3, 5 ... *        # odd numbers
1, 2, 4 ... *        # powers of 2
[download]
Conjecture: other such patterns may be recognized in the future, depending on which unrealistic benchmarks we want to run faster. :)

The Challenge

It's not hard to detect arithmetic or geometric sequences and to continue them. My interest is more in an elegant, general algorithm for continuing such series. If you can provide such an algorithm, it might even make its way into the Perl 6 specs.

The criteria are

Principle of least surprise: If there's no obvious solution, bail out (or return undef) rather than making up a solution.
Simplicity: You should neither need a degree in computer science nor in mathematics to understand what's going on.
Generality: The more sequences it can detect and continue, the better. When a sequence is detected, it should be able to return arbitrary many items of that sequence.
Speed: Before you spend too much time in that operator rather give up (that implies no support for the sequence of prime numbers, since you can't easily find the next prime number).
Integers only, for now. Don't care about floating points and rounding errors for now.

(Using a dump of the OEIS database doesn't meet these criteria).

My thoughts

My thoughts in spoiler tags below. Please try to find your solution prior to reading that, I don't want to bias you into a particular direction.

I've also written a small test script, but that should more serve as a starting point than as an authorotative test.

#!/usr/bin/perl
use strict;
use warnings;

use Test::More qw(no_plan);

sub series {
    # your code here.
}

my @tests = (
    [[1],                   undef],
    [[1, 1],                1],
    [[0, 0],                0],
    [[1, 2],                undef],
    [[0, 1, 2],             3],
    [[1, 0, -1],            -2],
    [[1, 2, 3],             4],
    [[1, 2, 4],             8],     # powers
    [[2, 4, 8],             16],
    [[1, 3, 9],             27],
    [[1, -1, 1, -1],        1],     # alternations
    [[-1, 1, -1, 1],        -1],
    [[1, 0, 1, 0],          1],
    [[0, 1, 0, 1],          0],
    [[1, 1, 2, 3, 5],       8],     # fibonacci
    [[0, 1, 1, 2, 3],       8],
    [[1, 2, 3, 5, 8],       13],
    [[1, 2, 6, 24, 120],    720],   # factorials
    [[1, 0, 0, 1],          undef],
    [[1, 2, 3, 1],          undef],
);

for my $t (@tests) {
    my $expected = defined $t->[1] ? $t->[1] : 'undef';
    my $result   = series(@{$t->[0]});
    $result = 'undef' unless defined $result;
    is $result, $expected, "seq " . join(', ', @{$t->[0]});
}
[download]

Update: Thanks for all the replies. I have to mull it over in my head, there are certainly good ideas and valid concern in the replies.

In reply to Challenge: Simple algorithm for continuing series of integers by moritz

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		`&`
	<		`<`
	>		`>`
	[		`[`
	]		`]`

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.