Re^2: Recursive traversal of a HoH... and paths

Yes, the tree can be arbitrarily deep and each leaf terminates with an empty hash ref, so recursion is needed.

Thanks for the example - it's a great starting point. If I understand it correctly, though, I'll need to change it slightly. Specifically, it looks like foo() is the criteria test, but it appears that only the keys pointing to the terminal leaves will be tested. I need to test all keys in between, too, so I'll pull that out of the else. That also means that the for loop need not be buried in the 'if' block, so I can remove the 'if' conditional. Finally, I need to track the matching paths, so I could use foo() (or similar) to do that.

Thanks again.

Comment on Re^2: Recursive traversal of a HoH... and paths Select or Download Code

Replies are listed 'Best First'.
Re^3: Recursive traversal of a HoH... and paths by jdporter (Paladin) on Oct 09, 2006 at 22:10 UTC
Well I don't know what you mean by 'test', but if you want to do something on every node - internal as well as leaf - then something like this: `sub walk { my( $v, @path ) = @_; foo( @path ); if ( keys %$v ) { for my $k ( sort keys %$v ) { walk( $v->{$k}, @path, $k ); } } }` [download] If that something might prevent recursion below the current node, then you could have it return a "prune" boolean: `sub walk { my( $v, @path ) = @_; foo( @path ) or return; # true means recurse if ( keys %$v ) { for my $k ( sort keys %$v ) { walk( $v->{$k}, @path, $k ); } } }` [download] Of course, for an even more general solution, you'd want to be able to pass in the "callback": `sub walk { my( $cb, $v, @path ) = @_; $cb->( @path ) or return; # true means recurse if ( keys %$v ) { for my $k ( sort keys %$v ) { walk( $cb, $v->{$k}, @path, $k ); } } }` [download] No doubt someone else will propose an iterator-based solution... We're building the house of the future together.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^3: Recursive traversal of a HoH... and paths
by jdporter (Paladin) on Oct 09, 2006 at 22:10 UTC

Well I don't know what you mean by 'test', but if you want to do something on every node - internal as well as leaf - then something like this:

sub walk
{
    my( $v, @path ) = @_;
    foo( @path );
    if ( keys %$v )
    {
        for my $k ( sort keys %$v )
        {
            walk( $v->{$k}, @path, $k );
        }
    }
}
[download]

If that something might prevent recursion below the current node, then you could have it return a "prune" boolean:

sub walk
{
    my( $v, @path ) = @_;
    foo( @path ) or return; # true means recurse
    if ( keys %$v )
    {
        for my $k ( sort keys %$v )
        {
            walk( $v->{$k}, @path, $k );
        }
    }
}
[download]

Of course, for an even more general solution, you'd want to be able to pass in the "callback":

sub walk
{
    my( $cb, $v, @path ) = @_;
    $cb->( @path ) or return; # true means recurse
    if ( keys %$v )
    {
        for my $k ( sort keys %$v )
        {
            walk( $cb, $v->{$k}, @path, $k );
        }
    }
}
[download]

No doubt someone else will propose an iterator-based solution...

We're building the house of the future together.

[reply]
[d/l]
[select]