Debolaz asked in #moose about the best way to create:

a list of numbers like 10,25,50,100,250,500,1000,etc without tracking any other
state than the number itself

Nope, this isn’t
A020179
but the much more prosaic
A112024.
Debolaz wanted this sequence, or something similar to it, for the same reason
the US used it for currency – the numbers are human meaningful, and are useful
as the numbers get exponentially bigger: in his case, for the labels for a
chart.

This may not be the most interesting of sequences, but, as autarch
pointed out, there are many algorithms that work, and exploring some of them
is fun and/or instructive.

First steps

My first idea was as follows:

• if the number is a power of 10, multiply by 2.5
• otherwise multiply by 2

Of course, knowing whether the number is a power of 10 is the only problem here.
The most trivial way is to treat it as a string, and check if it begins with “1″.

sub seq_1 {
    my $n = shift;
    my $val = 10;
    my @ret;
    for (1..$n) {
        push @ret, $val;
        $val *= $val =~ /^1/ ?
                2.5
              : 2;
    }
    return @ret;
}

say for seq_1(10);

autarch suggested dividing by 10 until you get to 1 (or not) as an alternative.

So we were back to a state variable like the position of the element in the sequence.

Mappy

Rather than doing it recursively, you can calculate the value from each position trivially:

    map { 10 * 10**(int $_/3) * [1,2.5,5]->[$_ % 3] } 0..10

That is to say

    10    10    10    100    100    100
*    1   2.5     5      1    2.5      5
=   10    25    50    100    250    500

i.e
10 * 10 ^
     0     0     0      1      1      1
*
     1   2.5     5      1    2.5      5

Not much else to say really, though I think indexing into [1,2.5,5] with the modded value
is cute.

awwaid suggested an improvement:

    map { 10**(int $_ / 3 +2) * 2**($_ % 3 -2) } -1..9

Which hurt my head for a while: it comes from the realization that the sequence is actually

    10   100   100   100   1000   1000
/    1     4     2     1      4      2

Recursive

frodwith suggested a recursive solution with an explicit parameter:

 sub your_seq {
  my $n = shift;
  return 10 unless $n;
  my @prev = your_seq($n-1);
  return (@prev, $prev[-1] * ($n % 3 == 1 ? 2.5 : 2));
}

That has a rather odd recursion style: turning it into tail-recursive style, and then
eliminating the recursion using the techniques from
Higher Order Perl
are left as an exercise to the reader.

Is Perl an acceptable Haskell?

Finally though, it is possible to do this without any additional state, by
turning the function into a little state machine. On the first iteration, the value
is multiplied by 2.5 and sets the next iteration to be one that multiplies by 2, leaving
the next iteration to multiply by 2 but queue up the original (x2.5) function next.

Instead of actually writing a state machine, I decided I’d rather have an infinite cycle
of the 3 functions, and iterate through them. Haskell has this as a builtin, but we
have to define it in Perl

sub cycle {
    my @list = @_;
    my @curr = @list;
    return sub {
        @curr = @list unless @curr;
        return shift @curr;
        };
}

Now we can create a list of functions that multiply by 2.5, 2, 2:

cycle([ map { times($_) } @multipliers ])

Where “times” is a function that given one multiplier, returns a function that
multiplies by that number. That is to say, it’s the * operator “curried”.
And by great coincidence, I just uploaded
Sub::Curried to CPAN, so we’ll
use that:

curry times ($x,$y) { $x * $y }

We’ll use the “curry” declarator for the rest of this example, largely because of the
automatic argument unpacking magic (I love Matt Trout’s
Devel::Declare).
Now that we have a sequence, we need to write something similar to Haskell’s scanr,
that repeatedly applies a transformation, returning a list of the intermediate values.

curry scan_iterator ($it, $start) {
    my $next = $start;
    return sub {
        my $ret = $next;
        $next = $it->()->($next); # prepare next value;
        return $ret;
        };
};

And as Perl doesn’t like infinite calculations, we may as well transform a slice of this
sequences into an array:

curry iterator_to_array ($it, $count) {
    return map { $it->() } 1..$count;
};

At which point we can put the whole thing together like so:

say for iterator_to_array(
        scan_iterator(
            mk_seq( [2.5, 2, 2] )
        )->(10) # start value
    )->(12); # number of iterations

I’ve uploaded the final source code as

an example for Sub::Curried.

Elegant? Overcomplicated? You decide!

Update:

• Joeri Samson pointed out a thinko (multiple/power)
• augustuss suggests the haskell version: scanl (*) 10 $ cycle [2.5,2,2]

  Much neater than my faffy version. But we can do the same in Perl (we just need to define scanl and rename iterator_to_array to “take”. Link to complete source code is updated.

  say for take 12 => scanl(times)->(10 => cycle [2.5, 2, 2] );

  Notice how (times) with no arguments is equivalent to a function reference, due to the autocurrying!