Ungolfed:

sub foo {
    my $a = shift @_;
    return [] unless $a;
    map { my $b = $_; map { [$_,@$b] } @$a } foo(@_);
}
[download]

                - Ant
                - Some of my best work - (1 2 3)

I was playing with something very similar to this but it wasn't coming out right. I gave up after an hour or so to go tackle another problem that didn't get solved (bike repair).

sub foo{
  my $F= shift;
  @G = @_ ? @{foo(@_)} : [] x scalar @$F;
  foreach my $e (@$F){
    push @H, map {[unshift @{$_}, "$e($i)"]} @G;
  }
  \@H;
}
[download]

That was of course just trying to get it to work, a proper golf would have been shorter.

--
perl -pe "s/\b;([mnst])/'\1/mg"