in reply to How to flatten an x-dimensional array?

Hmm. So far, far too many recursive solutions, when a simple iterative solution works fine: 
sub flatten {
  my @result;
  while (@_) {
    my $first = shift;
    if (UNIVERSAL::isa($first, "ARRAY")) { # fixed, thanks particle
      unshift @_, @$first;
    } else {
      push @result, $first;
    }
  }
  @result;
}

[download]

-- Randal L. Schwartz, Perl hacker

Replies are listed 'Best First'.
Re: •Re: How to flatten an x-dimensional array?
by particle (Vicar) on Mar 12, 2002 at 16:30 UTC
    that is, it works fine if you call UNIVERSAL::isa properly ;)

    it should be: 

    if (UNIVERSAL::isa($first, "ARRAY")) {

    [download]

    ~Particle ;̃

[reply]
[d/l]
[reply]
Re (tilly) 2: How to flatten an x-dimensional array?
by tilly (Archbishop) on Mar 12, 2002 at 17:30 UTC
    Note that your iterative solution can be slow with a long output list on any current Perl because iteratively building an array with unshift scales quadratically. (Fixed in the current development cycle.)

    Given the pattern of unshift's and shift's in your code, you might or might not hit this problem. But still for a single reverse you can use the guaranteed efficient pop/push pair instead of shift/unshift: 

    sub flatten {
  my @flattened; # Will be in reverse order
  while (@_) {
    my $last = pop;
    if (UNIVERSAL::isa($last, "ARRAY")) {
      push @_, @$last;
    }
    else {
      push @flattened, $last;
    }
  }
  return reverse @flattened;
}

    [download]
[reply]
[d/l]
      I think you missed a reverse there: 
      push @_, @$last;

      [download]
      needs to be 
      push @_, reverse @$last;

      [download]
      since you are reversing the result. Trivial example: $last = [1,2,3,4,5] must flatten as 5, 4, 3, 2, 1 so it can be reversed in the final result to 1, 2, 3, 4, 5 again.

      -- Randal L. Schwartz, Perl hacker

[reply]
[d/l]
[select]
        Try running it. :-)
[reply]

In Section Seekers of Perl Wisdom