Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked

References workout

by tlm (Prior)
on Apr 07, 2005 at 02:19 UTC ( #445513=note: print w/replies, xml ) Need Help??

in reply to Continuing from "Turning foreach into map?" - perlreftut and References

As was already pointed out, this case is simple enough that you could do a lot with simple hashes, without the need for references. For example, if you wanted a way to determine what group a particular food belonged to, you could set up a hash whose key => value pairs would be food names and their corresponding food groups. What makes this particular problem simple is that each food can belong to only one group.

To make the problem a bit more difficult, suppose that you had additional food groups and that they overlapped, so that any one food could belong to more than one group. For example, one additional group could be "Vegetarian", so that a food like "tofu" would belong both in "proteins" and "Vegetarian". In such a situation it would be useful to have a way to answer the question such as "does food X belong in group Y". For this you could use a hash of hashes. In this HoH, lets call it groups_to_foods the primary keys would be the food group names, and the secondary key would be the food names. You would assign to all of these ordered pairs a value of 1. The value is not important, since all you want to do is check (with defined) that some value has been entered for a particular combination of food group and food name (thereby answering the question of whether a the food of that name belongs to the group).

Here are a few more simple follow-up exercises. Given the HoH food_to_groups described above, what would be the Perl code to answer the question "does 'Cream' belong to group 'proteins'"? How about for the question "how many foods are in the group 'carbohydrates'"?

If you got the last question, you may wonder how one would code the solution to the opposite type of question, e.g. how many groups does 'tofu' belong to? One way to answer this question would be to count the number of groups Y for which the question "does 'tofu' belong in group Y" comes out true. But if your program had to deal with this type of question a lot, you may want to set up the inverse look up table. This would another HoH, but for this one the primary keys would be foods, and the secondary keys would be the food groups each food belonged to. Suppose that you had the first look up hash groups_to_foods, how would you populate the inverse lookup foods_to_groups HoH?

OK, here's is the next level. Suppose that, after setting up the first HoH above, groups_2_foods, you wanted to change all the primary keys (the group names) to all uppercase. Of course, you could just do the whole thing over with the new uppercased group names, but this would not be very interesting or instructive. There is a way to solve this problem that requires only moving around references. To use this approach the functions delete and uc would come in handy.

A third follow-up exercise: You are so pleased with the solution to the last exercise that you decide to write a sub that will uppercase the keys of any input hash. How would you do it? There is a gotcha in this problem: what if the original hash has both keys 'foo' and 'FOO'? Or, worse yet, keys 'foo', 'Foo', and 'FOO'? To begin with, however, solve the problem under the assumption that the keys of the original hash are all-lowercase, so no collisions can occur when you uppercase them. Once you get that to work you can think of how to handle the more general case.

Last exercise, maybe a bit more advanced, but if you have read perlreftut you should have all the background you need to solve it. You are very impressed with the usefulness of the function that you coded for the third exercise, but you notice that you could do something more general. What if instead of having the sub uppercase the keys of a hash, it modified these keys in some other arbitrary way, which you could specify by passing a second subroutine to the first subroutine? As with the previous exercise, there is the risk of collisions when you modify the keys, but if you figured out a way to deal with this problem in that exercise, then you may be able to use the same approach here. This last subroutine would be similar in spirit to my_map from Re: Turning foreach into map?, and it would serve as a nice segue back that post.

I'll post my solutions in a follow-up node. If you get stuck, just study the solution.

the lowliest monk

Replies are listed 'Best First'.
Re: References workout
by tlm (Prior) on Apr 07, 2005 at 02:21 UTC

    OK, to save myself some typing, I'm going to simplify the foods database significantly. Here we go:

    my %groups_to_foods = ( proteins => { eggs => 1, beef => 1, tofu => 1 }, carbs => { bread => 1, pizza => 1, twinkies => 1 }, vegetarian => { tofu => 1, bread => 1, twinkies => 1 } ); # it's just an example! # Is 'tofu' in 'carbs'? my $is_tofu_in_carbs = defined $groups_to_foods{ carbs }{ tofu }; # How many foods in the 'vegetarian' group? my $n_foods_in_vegetarian = scalar keys %{ $groups_to_foods{ vegetarian } }; # don't need "scalar" above; the assignment is already in # scalar context. # Next: invert the lookup table my %foods_to_groups; for my $group ( keys %groups_to_foods ) { my $hash_ref = $groups_to_foods{ $group }; for my $food ( keys %$hash_ref ) { $foods_to_groups{ $food }{ $group } = 1; } } # How many groups does 'twinkies' belong to? my $n_groups_for_twinkies = keys %{ $foods_to_groups{ twinkies } }; # How to change all the keys in %groups_to_foods to uppercase? # We assume that all the keys start out being in lowercase for my $group ( keys %groups_to_foods ) { $groups_to_foods{ uc $group } = $groups_to_foods{ $group }; delete $groups_to_foods{ $group }; } # Note that the values of the new hash are *identical* to # the values of the old hash; they refer to the same # locations in memory. This is because these hash values # are hash refs, and we just move them from one place to # another, just like transferring the title of a home from # one owner to the next owner leaves the home in place. # Actually, the last solution can be made a little slicker, # because the delete function returns the value # corresponding to the deleted key: for my $group ( keys %groups_to_foods ) { $groups_to_foods{ uc $group } = delete $groups_to_foods{ $group }; } # Write a sub to do the same thing for any hash # First we ignore the possibility of collisions; we # assume, for instance, that the keys are guaranteed # to be all in lowercase. sub uc_keys { my $hash_ref = shift; $hash_ref->{ uc $_ } = delete $hash_ref->{ $_ } for keys %$hash_ref; } # We could have omitted $_ in the call to uc, but let's # not. # With this definition, we can accomplish the uppercasing # of the groups like this: uc_keys( \ %groups_to_foods ); # OK, let's deal with the possibility of collisions. # Here's one simple (perhaps too simple) approach sub uc_keys { my $hash_ref = shift; { my %seen; for my $key ( keys %$hash_ref ) { my $uc_key = uc $key; die "Key collision! ($uc_key)\n" if defined $seen{ $uc_key }++; } } # if we made it this far, everything's ok # rest of code is exactly as before for my $key ( keys %$hash_ref ) { $hash_ref->{ uc $key } = delete $hash_ref->{ $key }; } } # One objection to the above solution is that uc is called # twice for every key in the original hash, which, for # sufficiently strained code, or sufficiently slow values # of uc, could be a problem. An alternative solution that # avoids this problem is this: sub uc_keys_2 { my $hash_ref = shift; my %new_hash; for my $key ( keys %$hash_ref ) { my $uc_key = uc $key; die "Key collision! ($uc_key)\n" if exists $new_hash{ $uc_key }; $new_hash{ $uc_key } = $hash_ref->{ $key }; } return \ %new_hash; } # In contrast to the first version, which returned nothing, # doing all its changes "in place", this one returns a # hash_ref. So, whereas uc_key would be used as already # shown above, uc_keys_2 would be used like this: %groups_to_foods = %{ uc_keys_2( \ %groups_to_foods ) }; # CAUTION: if instead of the last line one had used my %new_g2f = %{ uc_keys_2( \ %groups_to_foods ) }; # followed by $new_g2f{ CARBS }{ pasta } = 1; # this would result in changing the data in # %groups_to_foods, so that now the expression # $groups_to_foods{ carbs }{ pasta } equals 1. # This is because now the contents of $new_g2f{ CARBS } # and $groups_to_foods{ carbs } are *the same # hash ref*! This is leading into the topic of # deep copying. I give a link to an article on # deep copying below. # Last one: generalize the last sub so that it can take both # a sub and a hash and modifies the keys of the hash with # the input sub. We'll take the same tack as with the # last version of the last solution. The code is almost # identical. sub modify_keys { my $sub = shift; my $hash_ref = shift; my %new_hash; for my $key ( keys %$hash_ref ) { my $new_key = $sub->( $key ); die "Key collision! ($new_key)\n" if exists $new_hash{ $new_key }; $new_hash{ $new_key } = $hash_ref->{ $key }; } return \ %new_hash; }

    The promised ref to the article on deep-copying (by merlyn) is here.

    the lowliest monk

      tlm, I am so impressed with your answer and the time you have put in for me. This place is fantastic and such a community!

      I find myself here for most of my day now, and bookmarking loads of stuff in my home - ghenry.

      When I magic up some more time, I will try your exercises and get back to you.

      Again, thank you!

      Walking the road to enlightenment... I found a penguin and a camel on the way.....
      Fancy a Just ask!!!

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://445513]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (5)
As of 2017-10-23 22:51 GMT
Find Nodes?
    Voting Booth?
    My fridge is mostly full of:

    Results (285 votes). Check out past polls.