I was about to post a very similar algorithm, when I saw you had beat me to it. Nicely done! :)

One minor issue I'd like to highlight, though. You wrote:

  # Verify $prev is NON-empty
  if ($prev) { ... }
[download]

What if the first value is 0? Without knowing the range of values in @array, we can't assume there are no valid-but-false values. We can usually use undef, but there are situations where even that is considered valid.

The most straightforward approach is to use a third variable to track whether this is the first element:

  # straightforward approach: track whether this
  # is the first iteration or not explicitly.
  my $is_first = 1;
  my $prev;
  foreach my $elem ( @array )
  {
      if ( $is_first )
      {
          $is_first = 0;
      }
      else
      {
          push @result, compute( $elem, $prev );
      }
      $prev = $elem;
  }
[download]

If we can alter the contents of @array (which might be the case pretty often; consider the common situation of wanting to look through @_), we could initialize $prev with the first element and only iterate over the second and later elements:

  # note that this alters @array
  my $prev = shift @array;
  foreach my $elem ( @array )
  {
      push @result, compute( $elem, $prev );
      $prev = $elem;
  }
[download]

If we can't alter it, but the array is short enough to copy:

  my ( $prev, @rest ) = @array;
  foreach my $elem ( @rest )
  {
      push @result, compute( $elem, $prev );
      $prev = $elem;
  }
[download]

Finally, if we can't alter it, and it is a long list, we can use slices to iterate through second and later elements. (I don't know if this is particularly efficient, as I can't recall whether array slices are lazily evaluated or not):

  my $prev = $array[0];
  foreach my $elem ( @array[ 1 .. $#array ] )
  {
      push @result, compute( $elem, $prev );
      $prev = $elem;
  }
[download]

Although at this point I'd likely just switch back to using indexes directly:

  # note that we want $i to stop one short of $#array,
  # since we access $array[$i+1].
  for ( my $i = 0; $i < $#array; ++$i )
  {
      push @result, compute( $array[$i+1], $array[$i] );
  }
[download]

Update (at 2004-05-01 18:55 -0700): Rewrote some comments, split the alternate versions out into distinct <code> chunks.