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!