Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Scoping problems with recursive function

by morrin (Acolyte)
on Mar 19, 2010 at 18:00 UTC ( [id://829666]=perlquestion: print w/replies, xml ) Need Help??

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

Hi,

I basically have a function that I would like to call recursively to delete certain values from a hash. These values are interdependent, so if I need to delete a certain value, I also want to delete all other values that depend on that one.

For example, I have something like

my %hash = ( 'one' => 1, 'two' => 2, 'three' => 3, 'four' => 4, 'five' + => 5); my %dependencies =( 'one' => [], 'two' => [], 'three' => ['four'], 'fo +ur' => ['one','two'], 'five' => ['three']);

so if I need to delete 'one' from the list, I must also then also delete the keys 'three' and 'four' from the hash.

So my function looks something like

sub my_del($){ while (my $key = each (%hash)){ print "KEY = $key\n"; foreach (@{ $dependencies{$key} }){ if( $_ eq $_[0]){ print"Going to call sub for $key\n"; my_del($key); } } print"\n"; } delete $hash{$_[0]}; print "Deleting $_[0]\n"; } my_del('one');

The resulting output is

KEY = three KEY = five KEY = one KEY = two KEY = four Going to call sub for four Deleting four KEY = three KEY = five KEY = one KEY = two Deleting one

It is as if the "each" somehow is like a "global" in that when I call the function recursively, it remembers at which value it was at and continues from there.

Note that sometimes it will work depending of the ordering if the hash. eg, it works fine when I used

my %dependencies =( 'one' => [], 'two' => [], 'three' => ['one'], 'fou +r' => ['three','two'], 'five' => ['three']);

I got

KEY = three Going to call sub for three KEY = five Going to call sub for five KEY = one KEY = two KEY = four Deleting five KEY = three KEY = one KEY = two KEY = four Going to call sub for four Deleting four KEY = three KEY = one KEY = two Deleting three KEY = one KEY = two Deleting one

Any help would be gratefully appreciated. I am from a "C" background and I had thought it would work like I'd have expected to in "C". i.e. when each recursive call is made, local variables are created and everything starts again for that function. Thanks

Replies are listed 'Best First'.
Re: Scoping problems with recursive function
by fullermd (Priest) on Mar 19, 2010 at 18:14 UTC
    It is as if the "each" somehow is like a "global" in that when I call the function recursively, it remembers at which value it was at and continues from there.

    It is. Or rather, it's tied to the hash, so that it will always pick up where it left off anywhere. See each:

    There is a single iterator for each hash, shared by all "each", "keys", and "values" function calls in the program; it can be reset by reading all the elements from the hash, or by evaluating "keys HASH" or "values HASH".

    You probably want to use keys instead to iterate over it:

    for my $key (keys %hash) {
Re: Scoping problems with recursive function
by kennethk (Abbot) on Mar 19, 2010 at 18:15 UTC
    It's because the each is global in scope, or at least equivalent in scope to your hash. each creates an iterator that returns the next set of values on subsequent calls. You are calling each on the same hash (I'm assuming you are using a closure here), so naturally the iterator is just continuing on its merry way. I think it would make more sense here to use keys and Foreach Loops to iterate over the hash:

    #!/usr/bin/perl use strict; use warnings; my %hash = ( 'one' => 1, 'two' => 2, 'three' => 3, 'four' => 4, 'five' + => 5); my %dependencies =( 'one' => [], 'two' => [], 'three' => ['four'], 'fo +ur' => ['one','two'], 'five' => ['three']); #sub my_del($){ sub my_del{ #while (my $key = each (%hash)){ foreach my $key (keys %hash){ print "KEY = $key\n"; foreach (@{ $dependencies{$key} }){ if( $_ eq $_[0]){ print"Going to call sub for $key\n"; my_del($key); } } print"\n"; } delete $hash{$_[0]}; print "Deleting $_[0]\n"; } my_del('one');

    Note that I also removed the prototyping from your function declaration as well. It's unnecessary in Perl unless you are doing particular tricks and probably doesn't mean what you think it means. Note that it can't check the prototype until the function is defined, and hence you need cleverness to protoype a function you are calling recursively.

      [Prototyping is] unnecessary in Perl unless you are doing particular tricks and probably doesn't mean what you think it means.

      I strongly agree. However...

      ... you need cleverness to protoype a function you are calling recursively.

      But not very much cleverness. All that's needed is to declare (or define) the function before it's invoked:

      >perl -wMstrict -le "sub fact ($); # function declaration print qq{$_! == }, fact($_) for 0 .. 5; sub fact ($) { # function definition my $n = shift; return $n > 1 ? $n * fact($n - 1) : 1; } " 0! == 1 1! == 1 2! == 2 3! == 6 4! == 24 5! == 120

      Note: If you want to run the example above in Windose, first remove the # comments!

Re: Scoping problems with recursive function
by fullermd (Priest) on Mar 19, 2010 at 18:49 UTC

    Now, on a broader note.

    Your %dependencies hash is a list, by key, of the keys that key depends on. This is inconvenient for what you're trying to do, which is why you're jumping through some hoops.

    To put the function in english:

    foreach key foreach dependency of that key if this dependency is the one I want to delete, delete this key continue looping continue looping

    Now, note that in the middle, if you decide to delete this key, you're still continuing to loop over its dependencies. So you'd really want to break out of there.

    But better, you can avoid that loop completely, and just ask the question "am I ($key) one of the elements in this array?" with grep:

    if( grep { $_ eq $key } @{$dependencies{$key}} ) { print "Going to call sub for $key\n"; mydel($key); }

    That saves you writing the loop.

    But, let's step back. The key you're deleting probably isn't a dependency for most of the keys in the hash. If you're going to be calling this a lot, it can be a little annoying spending all that time searching over lists you're not in. You're having to do that because your list shows the dependencies of each key.

    But it would be even more convenient if instead it showed the keys that depend on each key. Then you could just loop over that list, deleting stuff. And it's pretty each to build that list from the one you have. Something like:

    my %requiredby; for my $key (keys $dependencies) { for my $dep (@{$dependencies{$key}}) { push @{$requiredby{$dep}}, $key; } } # Or alternately, using a statement modifier to be shorter my %requiredby; for my $key (keys %dependencies) { push @{$requiredby{$_}}, $key for @{$dependencies{$key}}; }

    Now you've got a lookup you can just loop directly over, and you can get even shorter. Obviously it costs some time and memory to build that %requiredby list, but if you're going to call the delete often, it's worth it. New version (tested):

    #!/usr/bin/env perl5 use strict; use warnings; my %hash = ( 'one' => 1, 'two' => 2, 'three' => 3, 'four' => 4, 'five' + => 5); my %dependencies = ( 'one' => [], 'two' => [], 'three' => ['four'], 'four' => ['one','two'], 'five' => ['three'] ); my %requiredby; for my $key (keys %dependencies) { push @{$requiredby{$_}}, $key for @{$dependencies{$key}}; } sub my_del { my $thiskey = shift; # Find all the keys that depend on us, and so have to go for my $del ( @{$requiredby{$thiskey}} ) { # Recurse and delete one key that requires us print "Going to call sub for $del\n"; my_del($del); } # And finally get rid of us delete $hash{$thiskey}; print "Deleting $thiskey\n"; } my_del('one');
    % ./tst.pl Going to call sub for four Going to call sub for three Going to call sub for five Deleting five Deleting three Deleting four Deleting one

    Of course, won't catch infinite loops, like if we set four to depend on three as well. That's left as an exercise for the reader :)

      I have no comment on the substantive issue but I would like to note that fullermd's reply goes much deeper than the others. I'd like to see more upvotes for it.

      The OP is a classic example of "How do I do this clumsy thing?" (I mean no disrespect to morrin by saying this. I often attempt clumsy things.) "Here's how to do that clumsy thing" is a good reply; "Here's a less clumsy approach" is much better.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://829666]
Approved by toolic
Front-paged by toolic
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others about the Monastery: (7)
As of 2024-03-28 21:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found