Here's how I might have done it if I were using iterators (which uses an explicit stack that the solutions in the referenced document in the OP avoid):

sub samefringe {
  my ( $x, $y ) = map { fringe_iter($_) } @_;
  my ( $next_x, $next_y );
  while ( 1 ) {
    ( $next_x, $next_y ) = ( $x->(), $y->() );
    last unless $next_x and $next_y;
    return unless $next_x eq $next_y;
  }
  return ( $next_y || $next_y ) ? 0 : 1;
}

sub fringe_iter {
  my $list = shift;
  my @arr = @$list;
  sub {
    while (1) {
      my $reftype = ref($arr[0]);
      return shift @arr unless $reftype;
      unshift @arr, fringe_iter(shift @arr) if $reftype eq 'ARRAY';
      my $next = $arr[0]->();
      if ( $next ) {
        unshift @arr, $next;
      } else {
        shift @arr;
      }
    }
  }
}
[download]