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]