The value of the S::T is that you do all your potentially expensive functions calls once per value, rather than many times.

Normally when you sort one list into another, the normal perl idioms go like this

my @output = sort @input; # default sort using eq to compare values
my @output = sort {$a <=> $b} @input; # numeric sort
my @output = sort some_func @input; # custom algorithm
[download]

Now lets have look at that last one - how often does some_func get called? Heres some code to show a potential worst case scenario

#!/usr/bin/perl -w

use strict;

my @input = (1..6);

my $calls;
my $fibcalls;

my @output = sort reorder @input; # how many calls to fib() ?

sub reorder {
  $calls++;
  return fib($a) <=> fib($b);
}

sub fib {
    my $val = shift;
    $fibcalls++;
    $val == 0 ? return $val:
      $val == 1 ? return $val :
    return fib($val - 1) + fib($val - 2);
}
print "called $calls times - fib calls $fibcalls\n";
[download]

Output is

cd /home/le6303/src/perl/
/usr/bin/perl -w "/home/le6303/src/perl/lister.pl" 
called 9 times - fib calls 150
[download]

OK, so a fibonacci sequence is exagerating the impact, but even so, what if some_func was doing some DBI-based lookup, using LWP or something else potential slow or expensive ?

Wouldn't it be better that we call some_func once for each unique value ?

Well we can. Looking at what we have so far, sort takes an input list (and potentially a function to operate on elements of that list) and returns a list. Wouldn't it be better if, instead of sort calling some_func repeated, often for a value it has already seen, we gave sort a list of values with some_func already applied ?

What we need is a function that takes a list, applies a function to each element once and once only, and returns a list of those function applications.

That function is map

We can write a trivial implementation of map thus

code>sub my_map { my ($function, @values) = @_; my @results; foreach my $value (@values) { push @results, $function->($value); } return @results; } </code>

Putting that together, we can show my_map applied to a list thus

#!/usr/bin/perl -w

use strict;

my @input = (1..6);

my @output = my_map(\&double, @input);

sub double {
    return 2 * shift;
}

sub my_map {
  my ($function, @values) = @_;

  my @results;
  foreach my $value (@values) {
     push @results, $function->($value);
  }

  return @results;
}

use Data::Dumper;
print Dumper \@output;;
[download]

Results are

cd /home/le6303/src/perl/
/usr/bin/perl -w "/home/le6303/src/perl/subber.pl" 
$VAR1 = [
          2,
          4,
          6,
          8,
          10,
          12
        ];
[download]

So to proceed, we want to pass the list of values that map has already processed to sort, and have sort compare those.

Like this

my @output = sort {$a <=> $b} map {fib($_)} @input;
[download]

But we have a problem now - @output is the sorted list of values that have had fib() applied to them, not the original list. If we put this together with our original example, we can see it more clearly

#!/usr/bin/perl -w

use strict;

my @input = (1..6);

my $calls;
my $fib_calls;

my @output = sort {$calls++; $a <=> $b} map {fib($_)} @input;

sub fib {
    my $val = shift;
    $fib_calls++;
    $val == 0 ? return $val:
      $val == 1 ? return $val :
    return fib($val - 1) + fib($val - 2);
}

print "called $calls times - fib $fib_calls\n";
use Data::Dumper;
print Dumper(\@output);
[download]

cd /home/le6303/src/perl/
/usr/bin/perl -w "/home/le6303/src/perl/lister.pl" 
called 9 times - fib 58
$VAR1 = [
          1,
          1,
          2,
          3,
          5,
          8
        ];
[download]

We only made 58 fib calls this time, but the output is wrong - it is the sorted fibonacci sequence, not the original list. How can we fix this ?

Map to the rescue. What we do is have the first map return a list of tuple's - in other word, pairs of values. The tuples are made up of the original value and the value with some_func (fib) applied e.g.

my @output =  map {[$_, fib($_)]} @input;
[download]

cd /home/le6303/src/perl/
/usr/bin/perl -w "/home/le6303/src/perl/lister.pl" 
$VAR1 = [
          [
            1,
            1
          ],
          [
            2,
            1
          ],
          [
            3,
            2
          ],

          [
            4,
            3
          ],
          [
            5,
            5
          ],
          [
            6,
            8
          ]
        ];
[download]

See how we have the pairs (value, some_func(value)) ?

So what we want now is for sort to use the second value in the pair to compare, but use the first value in generating the output list. Well sort wont do that, but we can use map again - it takes a list, does a manipulation to each element and returns a list of those manipulations. Code for that is

my @output = map {$_->[0]}              # extract just the original
                                        # value from the tuple
             sort {$a->[1] <=> $b->[1]} # sort based on the
                                        # computed value
             map {[$_, some_func($_)]}  # create (value, computed)
                                        # tuples
             @input;
[download]

Output is as required

HTH...