map & arrays & recursion

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

why aren't these two equivalent?

sub traversal {
  my $self = shift;
    my @nodes;
    # self is FIRST
    @nodes = ( $self );
    push @nodes, map { $_->traversal( ) } @{ $self->{children} };
    return @nodes;
[download]

sub traversal {
  my $self = shift;
    my @nodes;
    # self is FIRST
    @nodes = ( $self );
    foreach my $node ( @{ $self->{children} } ) {
        push @nodes, $node;
        $node->traversal();
    }
    return @nodes;
[download]

the second one correctly handles "width", but fails "height". (width is multiple nodes in the children array and no child node has any children) (height is a single node in the children array and each node has one child)

it visits every node; but it pushes just the first two nodes into the array. what am i missing?

Comment on map & arrays & recursion Select or Download Code

Replies are listed 'Best First'.
Re: map & arrays & recursion by Corion (Patriarch) on Sep 30, 2010 at 21:39 UTC
Because map is not a `for` loop? map returns the results of its block. You push onto `@nodes` whatever `$_->traversal()` returns. What it returns you hide from us, but I guess it is not what you expect it to return. So, make your `map` block return what you want to push onto `@nodes`, then things should work as you might want them.	[reply] [d/l] [select]
Re: map & arrays & recursion by kennethk (Abbot) on Sep 30, 2010 at 22:07 UTC
The literal equivalent of your mapped case would be: `sub traversal { my $self = shift; my @nodes; # self is FIRST @nodes = ( $self ); for (@{ $self->{children} }) { push @nodes, $_->traversal( ); } return @nodes; }` [download] Note how you are pushing on the result of `$_->traversal( );`. Your second code could equivalently be written as `sub traversal { my $self = shift; my @nodes; # self is FIRST @nodes = ( $self ); push @nodes, @{ $self->{children} }; $_->traversal() for @{ $self->{children} }; return @nodes; }` [download] Without knowing the contents of `$self->{children}` or the side-effects/return values of `$node->traversal()`, I cannot provide any additional insight.	[reply] [d/l] [select]
Re^2: map & arrays & recursion by ikegami (Patriarch) on Oct 01, 2010 at 03:13 UTC
Without knowing the contents of $self->{children} or the side-effects/return values of $node->traversal() Presumably, `traversal` traverses a tree. The children of a node are likely of the same type as that node, which makes `traversal` a recursive function. I cannot provide any additional insight. The OP's first snippet returns the nodes of the tree in pre-order. The OP's second snippet is obviously broken, traversing the entire tree to get only the nodes of depth one and two.	[reply] [d/l] [select]
Re^3: map & arrays & recursion by Anonymous Monk on Oct 02, 2010 at 00:06 UTC
thanks to both kennethk and ikegami. the first code from kennethk does indeed work. so i guess i don't understand what routines that return an array really do...... given this snippet : `foreach my $node ( @{ $self->{_children} } ) { push @list, $node->traverse(); } return @list;` [download] is the following a correct description ? `foreach node in the children ARRAY recursively call this routine if the node has children recursively call this routine if the node has NO children the returned list is just that node each time the routine returns it's array is pushed onto the array of the callee when the routine reaches the end of the top children ARRAY the visited nodes haved all been pushed into the top list` [download] for some reason, i had the impression that if you push an ARRAY into an ARRAY, the ARRAYS are preserved (not merged). thanks for your patience and support	[reply] [d/l] [select]
Re^4: map & arrays & recursion by ikegami (Patriarch) on Oct 02, 2010 at 04:21 UTC