Unwinding

TorgoX on 2005-02-07T01:35:49

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.