Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

TorgoX (1933)

TorgoX
  sburkeNO@SPAMcpan.org
http://search.cpan.org/~sburke/

"Il est beau comme la retractilité des serres des oiseaux rapaces [...] et surtout, comme la rencontre fortuite sur une table de dissection d'une machine à coudre et d'un parapluie !" -- Lautréamont

Journal of TorgoX (1933)

Sunday February 06, 2005
08:35 PM

Unwinding

[ #23056 ]
Dear Log,

At the clicky whirry heart of the Clock of the Long Now chimes browser, there is this recursive function:

sub MakePerm ($$);
sub MakePerm ($$) { # recursive
  my($f,$e) = @_;  # both arrayrefs
  return $f if @$f == 0;

  my $f_first = shift @$f;
  my $e_first = shift @$e;

  my $permy = MakePerm($f, $e);

  splice @$permy, $f_first,  0,  $e_first;

  return $permy;
}

In an effort for making it more amenable to reimplementation in languages that might not support recursion, I tried unwinding the recursion. I expected that it'd be a horror, with while(1)'s and state machines and a big festering @Callstack. I stared at the routine and thought about what data went where. After my brain stopped hemorrhaging, I realized that the code could be as simple as this:

sub MakePerm ($$) {
  my($f,$e) = @_;  # both arrayrefs
  my @out;
  for( my $i = @$f - 1; $i >= 0; $i-- ) { # backwards
    splice @out, $f->[$i],  0, $e->[$i] ;
  }
  return \@out;
}

I'm surprised that it would end up this simple.

In retrospect, it looks obvious. But then in retrospect, most things do.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.