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

[ghenry]

Hi Monks,

As pointed out to me in Re^3: Turning foreach into map?, I should really be trying to learn refs instead of map just now.

I have been reading perlreftut, and started to get an idea for the first program I want to write to learn refs.

The program will simply ask for some food types and tell you if you can eat them together, according to a combination chart (This is taken from the, "You Are What You Eat Cookbook").

Following the example, I have a data format as follows (HoAs?) and I just want to check this is correct before moving on to the code:

%food_combining
----------------
        
proteins                  ---->| Cheese  | Eggs | Fish | Game | Rabbit
+ | Meat | Milk | Nuts | Poultry | Shellfish | Soybeans | tofu | soya 
+| Yogurt
       
carbohydrates             ---->| oats | pasta | rice | rye | maize | m
+illet | biscuits | bread | cakes | crackers | pastry | honey | maple 
+syrup | potatoes | yams | sweetcorn | sugar | sweets 
        
nonstarchy_veg_and_fats   ---->| Butter | Cream | Herbs | Spices | Sea
+sonings | Olive Oils | Oils | Salads | Seeds

Fruit                     ---->| All Fruit

The rules, once someone enters something via <STDIN>, are:

Yes:
Groups 1 and 3
Groups 2 and 3
Group 4 alone

No:
Groups 1 and 2
Groups 1 and 4
Groups 2 and 4
Groups 3 and 4

If so, I'll start writing.

Thanks.

[Roy Johnson]

I think you're going to want %food_combining to have specific food type as keys, and groups as values, so you can look up the group name (or number, however you decide to store it) for whatever foods you are given. Unfortunately for your intent, that's just a single-level hash.

Then you've got the rules for combining groups. You could do that with an AoA or HoH (depending on whether you did group numbers or names). Your indexes would be two groups, and the value would be Yes or No (or you could just index the Yes values, and if there's no value, it's No). Be sure to index things in both orders: [1][3] == [3][1].

[Random_Walk]

I am guessing you want to get something like this.

User enters a list of food items
Program looks up group for food items
Program looks up rules to see if those groups can be combined or not.
Program reports to user

The best aproach for this would be to make a hash with the food item as the key and its group number as the value stored under this key. No playing with refs there :(

Perhaps you want the user to enter a food item and the program will suggest possibly combinations to go with this, in this case the best approach is probably functional programing ! I think Haskell is the popular one round here. But that is not why we're here is it, to do it in perl you may well want to build an array or hash of arrays. As your food groups are numeric in your rules I'd be inclined to use array of arrays.

@food=(
        ['eggs', 'fish'],
        ['cheese', 'lard'],
        ['breed', 'rice'],
        ['beer', 'wine'],
);

print $food[3][0]; # prints beer

If you want to do the hash of arrays you can build it up like this

%food=( 'carbs' => ['breed', 'rice'],
        'tasty' => ['chocolate', 'pistacio'],
);
print $food{tasty}[1]; # prints pistacio

Cheers,
R.

[tlm]

I'm not sure I follow. Do you want to create a two-dimensional look-up table, so that you could look up, say, 1 and 4 (or 'proteins' and 'Fruit') and read off 'No'? If this is the case, then I don't see why you would need to specify the members of each group ('protein', 'Fruit', etc.).

[tlm]

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.

[tlm]

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.

[ghenry]

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!