Recursion?

[ericse]

Hi guys-

I'm trying to test whether nested hash refrences exist, like so:

my %ref = (
  'app' => {
    'next' => {
      'further' => 10
    }
  }
);

if (nested_exists(\%ref, 'app', 'next', 'further')) {
  do whatever.....
}

sub nested_exists {
  my ($ref, @keys) = @_;


  .....i just don't get it :(

}

Can anyone help me out here? The main thing is that it doesn't auto-create the keys if they don't exist. I need to make sure it's not auto-vivifying the data. In order to do this I was told I need to use recursion, which is great because I really want to understand how recursion works... I get the concept, but then to apply it in practice is so hard for me. Thanks

~Eric

 

[ericse]

I've come up with this, but I know it won't work... But this is similar to what I want done:

sub nested_exists {
    my ($ref, @keys) = @_;

    if (exists $ref->{$keys[0]}) { nested_exists(\$ref, shift(@keys)); }
    else { return 0; };

    return 1;
}

Thanks

 

[MillerH]

Greetings,

Obviously this is homework of some kind, so let me simply show you two things that will get you on your way.

[gray][i]# The each function[/i][/gray]
[gray][i]# - Also of note are  the keys, values, and foreach functions[/i][/gray]
[url=http://perldoc.perl.org/functions/my.html][black][b]my[/b][/black][/url] [blue]$hash[/blue] = [red]{[/red][purple]a[/purple] => [fuchsia]1[/fuchsia], [purple]b[/purple] => [fuchsia]2[/fuchsia], [purple]c[/purple] => [fuchsia]3[/fuchsia][red]}[/red][red];[/red]

[url=http://perldoc.perl.org/functions/print.html][black][b]print[/b][/black][/url] [red]"[/red][purple]Testing each:[purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
[olive][b]while[/b][/olive] [red]([/red][black][b]my[/b][/black] [red]([/red][blue]$key[/blue], [blue]$val[/blue][red])[/red] = [url=http://perldoc.perl.org/functions/each.html][black][b]each[/b][/black][/url] [blue]%$hash[/blue][red])[/red] [red]{[/red]
	[black][b]print[/b][/black] [red]"[/red][purple]    [blue]$key[/blue] => [blue]$val[/blue][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
[red]}[/red]

[gray][i]# The ref function[/i][/gray]
[black][b]my[/b][/black] [blue]$scalar[/blue] = [fuchsia]1234[/fuchsia][red];[/red]
[black][b]my[/b][/black] [blue]$scalarref[/blue] = \[blue]$scalar[/blue][red];[/red]
[black][b]my[/b][/black] [blue]$hashref[/blue] = [red]{[/red][fuchsia]1..6[/fuchsia][red]}[/red][red];[/red]
[black][b]my[/b][/black] [blue]$arrayref[/blue] = [red][[/red][fuchsia]1..6[/fuchsia][red]][/red][red];[/red]

[black][b]print[/b][/black] [red]"[/red][purple]Testing ref:[purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
[olive][b]foreach[/b][/olive] [black][b]my[/b][/black] [blue]$var[/blue] [red]([/red][blue]$scalar[/blue], [blue]$scalarref[/blue], [blue]$hashref[/blue], [blue]$arrayref[/blue][red])[/red] [red]{[/red]
	[olive][b]if[/b][/olive] [red]([/red][red]'[/red][purple]SCALAR[/purple][red]'[/red] eq [url=http://perldoc.perl.org/functions/ref.html][black][b]ref[/b][/black][/url] [blue]$var[/blue][red])[/red] [red]{[/red]
		[black][b]print[/b][/black] [red]"[/red][purple]   It's a scalar reference: [blue]$$var[/blue][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
	[red]}[/red] [olive][b]elsif[/b][/olive] [red]([/red][red]'[/red][purple]ARRAY[/purple][red]'[/red] eq [black][b]ref[/b][/black] [blue]$var[/blue][red])[/red] [red]{[/red]
		[black][b]print[/b][/black] [red]"[/red][purple]   It's an array reference: [/purple][red]"[/red] . [url=http://perldoc.perl.org/functions/join.html][black][b]join[/b][/black][/url][red]([/red][red]'[/red][purple],[/purple][red]'[/red], [blue]@$var[/blue][red])[/red] . [red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
	[red]}[/red] [olive][b]elsif[/b][/olive] [red]([/red][red]'[/red][purple]HASH[/purple][red]'[/red] eq [black][b]ref[/b][/black] [blue]$var[/blue][red])[/red] [red]{[/red]
		[black][b]print[/b][/black] [red]"[/red][purple]   It's a hash reference: [/purple][red]"[/red] . [black][b]join[/b][/black][red]([/red][red]'[/red][purple],[/purple][red]'[/red], [url=http://perldoc.perl.org/functions/map.html][black][b]map[/b][/black][/url] [red]{[/red][red]"[/red][purple][blue]$_[/blue]=>[blue]$var[/blue]->{[blue]$_[/blue]}[/purple][red]"[/red][red]}[/red] [url=http://perldoc.perl.org/functions/keys.html][black][b]keys[/b][/black][/url] [blue]%$var[/blue][red])[/red] . [red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
	[red]}[/red] [olive][b]elsif[/b][/olive] [red]([/red]! [black][b]ref[/b][/black] [blue]$var[/blue][red])[/red] [red]{[/red]
		[black][b]print[/b][/black] [red]"[/red][purple]   It's not a reference, it's a scalar: [blue]$var[/blue][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
	[red]}[/red]
[red]}[/red]

Output:

>perl scratch.pl
Testing each:
    c => 3
    a => 1
    b => 2
Testing ref:
   It's not a reference, it's a scalar: 1234
   It's a scalar reference: 1234
   It's a hash reference: 1=>2,3=>4,5=>6
   It's an array reference: 1,2,3,4,5,6

- Miller

 

[ericse]

Ok, so that second post won't work for beacuse it isn't incrementing the hash ref:

sub nested_exists {
    my ($ref, @keys) = @_;

    if (exists $ref->{$keys[0]}) {
        my $new_ref = $ref->{$keys[0]};
        nested_exists(\$new_ref, shift(@keys));
    }
    else { return 0; };

    return 1;
}

That I think, *should* work without auto-vivifying the original ref. But.....what happens when the array gets "shifted" down to nothing? How do I deal with this?

Thanks again,
~Eric

 

[ericse]

Hi Miller-

Actually, it's not for homework. I was recently hired into the technology department at my company. Having no formal experience in programming (it was a hobby of mine for a long time) the lead developer assigns me tasks that he thinks will be beneficial for me to learn in order to improve my "skills."

In any event, as you can probably tell from my previous posts, this tasks are somewhat strange.

I'm supposed to be using recursion (at least that's what my lead told me to do) for this function.

My previous reply prior to this one shows what I have done thus far.. and I think my logic is *mostly* correct, except for the shifting of the array down to 0.

I understand most of what you wrote, but I guess I'm not really sure how any of that applies to what I'm doing. :/

Maybe it's just me though?

Thanks as always,
~Eric

 

[MillerH]

Hi Eric,

Either way, obviously you are on the task to learning, so that makes helping a little trickier. I don't want to just give away the answer. You actually right though, in that one of the things that I showed you did not actually apply, as I misunderstood your original problem. Let me try to guide you where you need to go.

Question: What's the very first thing that you should be testing in your function?

Hint:

[COLOR=white]What assumptions are you making about your data?[/color]

- Miller

 

[MillerH]

BTW, I'm going to be leaving soon, so here is the full spoiler psuedo code. Don't look at this until .... well, you be the judge. Also, I've formatted it in a way so that you can only reveal just one line at a time if you want.

SPOILER Contained:

[COLOR=white]
1) False unless $ref is a Hash reference


2) False unless @keys has values


3) False unless next key exists


4) True if there are no more keys left


5) Recurse (note this is the tricky part. What do you pass during recursion?)
[/color]

- Miller

 

[ericse]

Miller,

Hmmm. I guess I'm assuming that @keys will be defined, and I'm also assuming the $ref is a hash ref (although that seems a little less important).

Then, if I believe what I just wrote to be true, my first test should deal with whether or not @keys holds any data.

At that point, I know what to do if it does: shift the array and *increment* the ref. But if @keys does not contain any data, I'm at a loss for. Because, I simply can't return 0 if @keys is undefined after a given number of iterations....

I'm confused. :/ Am I on the right track at all? With my sample:

sub nested_exists {
    my ($ref, @keys) = @_;

    if (exists $ref->{$keys[0]}) {
        my $new_ref = $ref->{$keys[0]};
        shift(@keys);
        if (defined @keys) {
            nested_exists(\$new_ref, @keys);
        }
    }
    else { return 0; }

    return 1;
}

I know I didn't check at the begging if the @keys is actually valid because I wrote that before I read your response. I just hope I'm on the right track.

Thanks,
~Eric

 

[ericse]

Miller-

Looks like I was on the right track I posted that seconds after you posted your response. Which is good--at least my thinking is on the right track.

Thanks for the notes. Also, thanks for not just telling me how to do it This is far more helpful then I could express to you.

Again, thanks so much,
~Eric

 

[MillerH]

Hi Eric,

You're starting to get on the right track yes. But you still have some things to test and some bugs to fix.

1) defined does not test what you think it does:

@array = ();
print "I am defined" if defined @array;
print "But I contain no values" if ! @array;

2) You sure you want to do this?

\$new_ref

Anyway, the biggest thing that I want you to learn about recursion is that you should test for all the small things first. Don't assume anything to be true. This works out to your advantage later, because it gives you the freedom to make a recursive call on untested data, because you know the function will handle it on the subsequent call.

I am gone now for an hour.

Good luck,
- Miller

 

[MillerH]

1) defined does not test what you think it does:

My statement here was accurate, but my example was flawed:

[url=http://perldoc.perl.org/functions/my.html][black][b]my[/b][/black][/url] [blue]@a[/blue] = [red]([/red][red])[/red][red];[/red]

[url=http://perldoc.perl.org/functions/print.html][black][b]print[/b][/black][/url] [red]'[/red][purple][/purple][red]'[/red] . [red]([/red][url=http://perldoc.perl.org/functions/defined.html][black][b]defined[/b][/black][/url] [blue]@a[/blue] ? [red]"[/red][purple]is defined[/purple][red]"[/red] : [red]"[/red][purple]is not defined[/purple][red]"[/red][red])[/red] .[red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
[black][b]print[/b][/black] [red]'[/red][purple][/purple][red]'[/red] . [red]([/red][blue]@a[/blue] ? [red]"[/red][purple]has data[/purple][red]"[/red] : [red]"[/red][purple]has no data[/purple][red]"[/red][red])[/red] . [red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
[black][b]print[/b][/black] [red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]

[blue]@a[/blue] = [red]([/red][fuchsia]10[/fuchsia][red])[/red][red];[/red]

[black][b]print[/b][/black] [red]'[/red][purple][/purple][red]'[/red] . [red]([/red][black][b]defined[/b][/black] [blue]@a[/blue] ? [red]"[/red][purple]is defined[/purple][red]"[/red] : [red]"[/red][purple]is not defined[/purple][red]"[/red][red])[/red] .[red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
[black][b]print[/b][/black] [red]'[/red][purple][/purple][red]'[/red] . [red]([/red][blue]@a[/blue] ? [red]"[/red][purple]has data[/purple][red]"[/red] : [red]"[/red][purple]has no data[/purple][red]"[/red][red])[/red] . [red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
[black][b]print[/b][/black] [red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]

[url=http://perldoc.perl.org/functions/shift.html][black][b]shift[/b][/black][/url] [blue]@a[/blue][red];[/red]

[black][b]print[/b][/black] [red]'[/red][purple][/purple][red]'[/red] . [red]([/red][black][b]defined[/b][/black] [blue]@a[/blue] ? [red]"[/red][purple]is defined[/purple][red]"[/red] : [red]"[/red][purple]is not defined[/purple][red]"[/red][red])[/red] .[red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
[black][b]print[/b][/black] [red]'[/red][purple][/purple][red]'[/red] . [red]([/red][blue]@a[/blue] ? [red]"[/red][purple]has data[/purple][red]"[/red] : [red]"[/red][purple]has no data[/purple][red]"[/red][red])[/red] . [red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]
[black][b]print[/b][/black] [red]"[/red][purple][purple][b]\n[/b][/purple][/purple][red]"[/red][red];[/red]

Output:

>perl scratch.pl
is not defined
has no data

is defined
has data

is defined
has no data

As you can see in the last example, @a is defined even though it contains no data. The point therefore is stay away from defined unless there is a specific reason why you want it. Most often you are actually testing if something simply has data. This is especially true of @arrays. So just take advantage of the fact that an @array returns the number of elements when used in a scalar context. If you're really paranoid you could even do if (scalar(@array)) or if (@array != 0).

- Miller

- Miller