Re: flattening a list-of-lists

Anonymous Monk,
Here is a non-recursive approach that may be more flexible. It will not follow the same array ref twice, which will prevent circular references causing infinite loops.

#!/usr/bin/perl -w
use strict;

my @array1 = ( 1 .. 10 );
my @array2 = ( qw(a b c) , [ 28, 42, 84 ] , 'foo bar' );

push @array1 , \@array2;
push @array2 , \@array1;

print join ' , ' , flatten(\@array1 , \@array2);

sub flatten {
   my @stack = @_;
   my @flat;
   my %seen;

   $seen{$_} = 1 for @stack;

   while ( @stack ) {
       my $array = shift @stack;
       for my $element ( @$array ) {
           if ( ref $element eq 'ARRAY') {
               if ( ! $seen{$element} ) {
                   $seen{$element} = 1;
                   unshift @stack , $element;
               }
           }
           else {
               push @flat , $element;
           }
       }
   }

   return wantarray ? @flat : \@flat;
}
[download]

Cheers - L~R

Update: I asked for comments in the CB since this is the first time I have tried doing this:

demerphq - ref can be fooled by blessed arrays, better to use Scalar::Util::reftype()
demerphq - Even that is prone to problems when overloaded stringification is present
tye - It is assumed that @stack will only contain array refs. Code to handle for mistakes should be added

Comment on Re: flattening a list-of-lists Download Code

Replies are listed 'Best First'.
Re: Re: flattening a list-of-lists by demerphq (Chancellor) on Nov 19, 2003 at 19:24 UTC
Hi Limbic~Region, in response to your question in the CB I wrote the following code. It handles the issues you mention in your update as well as the fact that you are doing the wrong kind of traversal. Read more... (2 kB) The output I get for the two variants is below. `flatten:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, a, b, c, 28, 42, 84, foo bar lr_flatten:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, a, b, c, foo bar, 28, 42, 84 * flatten:bar, baz, 2, foo, 1, baz, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, a, + b, c, 28, 42, 84, foo bar` [download] The star result is from dumping a hash, something I added in just for the hell of it. :-) Cheers, --- demerphq _{First they ignore you, then they laugh at you, then they fight you, then you win. -- Gandhi}	[reply] [d/l] [select]
Re^3: flattening a list-of-lists (simpler) by tye (Sage) on Nov 19, 2003 at 20:14 UTC
Updated: It now includes checking for cycles. That seems way complicated. I went with: *isa = \&UNIVERSAL::isa; sub flatten { my @stack= reverse @_; my %seen; my @out; while( @stack ) { my $value= pop(@stack); if( !ref($value) \|\| !isa($value,"ARRAY") ) { push @out, $value; } elsif( ! $seen{0+$value}++ ) { push @stack, reverse @$value; } } return @out; } sub flatten2 { my @out; my %seen; while( @_ ) { my $value= shift(@_); if( !ref($value) \|\| !isa($value,"ARRAY") ) { push @out, $value; } elsif( ! $seen{0+$value}++ ) { unshift @_, @$value; } } return @out; } my @list = ( 1, [ 2, 3 ], 4, [ [ 5, 6 ], 7, [ 8 ] ] ); print join " ", flatten( @list, @list ); print $/; print join " ", flatten2( @list, @list ); print $/; [download] which outputs: `1 2 3 4 5 6 7 8 1 4 1 2 3 4 5 6 7 8 1 4` [download] - tye	[reply] [d/l] [select]
Re: Re^3: flattening a list-of-lists (simpler) by demerphq (Chancellor) on Nov 19, 2003 at 22:39 UTC
I think its arguable that mine is closer to what (I see) is the spirit of L~R's original intention. That being to minimize the amount overhead especially that associated with the stack. I thought of using this approach, but decided against on the grounds that it involved an unreasonable amount of copying and stack manipulation. Heh. Whatever. In real life I would just use recursion on this most likely. :-) Caveats about using is() and 0+$ref in the algorithm of course. Better to use Scalar::Util or parse overload::StrVal(). But you knew that, and its beside the point here isnt it. :-) --- demerphq _{First they ignore you, then they laugh at you, then they fight you, then you win. -- Gandhi}	[reply] [d/l]