Your skill will accomplishwhat the force of many cannot PerlMonks

### Arbitrarily Nested HoH

by Limbic~Region (Chancellor)
 on Oct 15, 2010 at 00:49 UTC Need Help??
Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

All,
Earlier today, I was faced with a problem that amounted to:
```for my \$let (keys %hash) {
for my \$num (keys %{\$hash{\$let}}) {
for my \$name (keys %{\$hash{\$let}{\$num}}) {
print join(',', \$let, \$num, \$name, \$hash{\$let}{\$num}{\$name
+}), "\n";
}
}
}

The trouble was, the data structure was going to be an arbitrary number of levels deep. My first inclination was to reach for Algorithm::Loops but it didn't seem like a good fit. My second idea was to write an iterator (see Arbitrarily Nested Loops) but I wanted a coworker who is just learning perl (former C++ developer) to be able to maintain it. In a few minutes, I came up with a recursive solution which surprised me.

On my way home, I thought of several other ways of doing it and I was wondering how others might solve the problem. That is my question - how would you do it? I have provided my recursive solution below to get the ball rolling.

Cheers - L~R

Replies are listed 'Best First'.
Re: Arbitrarily Nested HoH
by BrowserUk (Pope) on Oct 15, 2010 at 04:44 UTC

Probably overkill for what you want, but it handles a mix of nested hashes and arrays, and a few other refs as well.

```sub traverse(&\$) {
my( \$code, \$ref ) = @_;
my \$d;
\$d = {
SCALAR => sub{
my \$code = shift; my \$ref = shift;
return \$code->( @_, \$\$ref );
},
ARRAY  => sub {
my \$code = shift; my \$ref = shift;
map \$d->{ ref \$ref->[ \$_ ] }->( \$code, \$ref->[ \$_ ], @_, \$
+_ ),
0 .. \$#\$ref;
},
HASH  => sub {
my \$code = shift; my \$ref  = shift;
map \$d->{ ref \$ref->{ \$_ } }->( \$code, \$ref->{ \$_ }, @_, \$
+_ ),
keys %\$ref;
},
REF  => sub{
my \$code = shift; my \$ref = shift;
return \$d->{ ref \$\$ref }->( \$code, \$\$ref, @_ );
},
CODE => sub{
my \$code = shift; my \$ref = shift;
return \$d->{ '' }->( \$code, "\$ref", @_ );
},
''  => sub{
my \$code = shift; my \$ref = shift;
return \$code->( @_, \$ref );
},
};
return \$d->{ ref \$ref }->( \$code, \$ref );
}

traverse { print join ',', @_ } \%hash;

You can also use it like this to build an array:

```my @strings = traverse{ join',', @_ } \%HorAofHorA;

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Arbitrarily Nested HoH
by bduggan (Pilgrim) on Oct 15, 2010 at 03:40 UTC
I think I'd do it like this :
```sub traverse {
my (\$b, \$h) = @_;
return ref \$h
? map traverse([ @\$b, \$_ ], \$h->{\$_}), keys %\$h
: ( join ',', (@\$b, \$h) ) . "\n";
}

print traverse([], \%hash);
Re: Arbitrarily Nested HoH
by muba (Priest) on Oct 15, 2010 at 01:58 UTC
Re: Arbitrarily Nested HoH
by ig (Vicar) on Oct 15, 2010 at 04:30 UTC

I would probably do something like:

```output(\%hash);

sub output {
my (\$hash, @keys) = @_;

die 'Not a hashref' unless(ref(\$hash) eq 'HASH');

foreach my \$key (sort keys %\$hash) {
if(ref(\$hash->{\$key}) eq 'HASH') {
output(\$hash->{\$key}, @keys, \$key);
} else {
print join(', ', @keys, \$key, \$hash->{\$key}), "\n";
}
}
}

Re: Arbitrarily Nested HoH
by llancet (Friar) on Oct 15, 2010 at 05:53 UTC
```use strict;
use Scalar::Util qw/reftype/;

my %hash_to_do

sub do_hash {
my \$hash_ref = shift;

foreach my \$key (keys %\$hash_ref) {
my \$value_type = reftype \$hash_ref->{\$key};

if (\$value_type eq 'HASH') {
do_hash(\$hash_ref->{\$key});
}
else {
# do something else
}
}
}
Re: Arbitrarily Nested HoH
by juster (Friar) on Oct 15, 2010 at 07:35 UTC
Another solution using map. Does not pass an extra state variable around. More like a DFS approach. Handles array refs too. Uses brackets and curly brackets to differentiate between arrays and hashes.
```sub flatten
{
my (\$value) = @_;

my \$rtype = ref \$value or return "=\$value\n"; # ends recursion

if ( \$rtype eq 'ARRAY' ) {
return map {
my \$i = \$_; map { "[\$i]\$_" } flatten( \$value->[ \$_ ] );
} ( 0 .. \$#\$value );
}
elsif ( \$rtype eq 'HASH' ) {
return map {
my \$k = \$_; map { "{\$k}\$_" } flatten( \$value->{ \$_ } );
} sort keys %\$value;
}

die 'flatten only handles scalars, arefs, or hrefs';
}

print for flatten( \%hohoh );
Re: Arbitrarily Nested HoH
by sundialsvc4 (Abbot) on Oct 15, 2010 at 13:32 UTC

Recursion is a very powerful technique, and fairly cheap to do.   Lately, I have also found useful the notion of a “work-to-do stack,” in which we push the first item(s) onto the stack initially, and then repeat a process in a simple loop until the stack becomes empty.   As more work is discovered, it is pushed onto the stack (or stacks, as the case may be).

This is, of course, very similar to recursion in the simple case, but it can come in handy when “the case” becomes “not quite so simple,” e.g. when there might need to be a choice concerning “what to do next.”   (Priorities, prerequisites, and so forth ...)   A recursion is always FIFO (“first-in first-out”), but this does not have to be.   All the work will eventually get done, no matter how much work there is, but it is not strictly obliged to be FIFO.

Perhaps I am misunderstanding your comment, but if your recursion uses a stack (which, I would say, at least the calls do), the solution has to be LIFO. A queue would be FIFO.

This could just be a difference between understanding your comment differently than the way you meant to say it.

--MidLifeXis

Stack.   Queue.   Whatever.   :-D

“Verily, verily, I code unto thee:   he who seeks to be first, shall be last...”   :-;

You store the items, in some method and according to some suitable discipline, and then you “work through the list(s).”   That’s the gist of it.

Re: Arbitrarily Nested HoH
by apomatix (Novice) on Oct 15, 2010 at 02:31 UTC
I like your solution. I wonder how else you thought of doing it. However, I don't think your solution would be easy for someone "just learning Perl".
apomatix,
I wonder how else you thought of doing it.

As I indicated, I considered an iterator. Here is a very unpolished working version:

As you can see, it is far more complex than the recursive solution. Also, the iterator could result in bizarre behavior if the hash isn't walked all at once. This is because each itself is an iterator that is reset any time there is a call to keys or values. In the recursive version, the hash is traversed all at once so there isn't an opportunity to reset the iterator mid-traversal.

Here is the stack based iterative version I was thinking of. I think it is the nicest because it is how my brain works:

However, I don't think your solution would be easy for someone "just learning Perl".

Why? That's an honest question. Provided you understand references (which he does), it should be straight forward. That is unless you are like me and have a hard time thinking recursively but the whole point of writing it recursively was that most programmers I know think that way naturally. What about it do you think a seasoned C++ programmer would find hard to understand?

Cheers - L~R

Create A New User
Node Status?
node history
Node Type: perlquestion [id://865376]
Approved by muba
Front-paged by muba
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (5)
As of 2017-12-15 00:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What programming language do you hate the most?

Results (415 votes). Check out past polls.

Notices?