It appears, as it turns out, a less general and more specific Perl structure, a HashOfArray would have been better.

Sorry that I have no specific name in your application for this structure or knowledge of a standard module to convert between various structure types. But as seen in this thread, such a conversion is "not hard".

This is getting a little esoteric but then if esoterica is disallowed among monks where would it be allowed, pray tell? The only cases where I can imagine the keys "key" and "value" being nonpathological are in schema descriptions. Could you expand my imagination with some counter-examples?

If it's pathalogical, what would be nonpathological?

$param->{'key'}          # { key => $key, value => $value }
[download]

is slightly clearer than

$param->[0]              # [ $key, $value ]
[download]

and much more clearer than

(keys(%$param))[0]       # { $key => $value }
[download]

Update: I missed this:

The non-pathological representation would have: $hash{$key}=[$value1, $value2, $value3,...]

But it's not true. That doesn't maintain order, so the question remains. What would be nonpathological?

This is not esoteric. Let me show some data structure access examples. In the below, imagine "key" being X and "value" being Y coordinates.

'C':
#define X_coord  0
#define Y_coord  1
#define MAX_ROWS 3

/* graph is a 2-d array of ints
   each row has an X and a Y coordinate
   Normally graph would be built dynamically as an
   array of pointer to array. The same [x][y]
   syntax can be used like in a predefined array.  

   The same [x][y] syntax works in Perl's array of
   references to arrays also. Although in most cases,
   I would consider this a "not good thing". 
*/   
 
for (int row =0; row <MAX_ROWS; row++)
{
   int this_pointX = graph[row][X_coord];
   int this_pointY = graph[row][Y_coord];
   ....
)   
##########
Perl: using Array of Array, about the same as 'C'
      this UGLY...

my $X_coord = 0;
my $Y_coord = 1;
foreach my $i (0..@graph-1) # forget 0..$#graph
                            # needless use of special variable 
{
   my $this_pointX = $graph[$i][$X_coord];
   my $this_pointY = $graph[$i][$Y_coord];
}
##########
Perl: Better than above using Array of Array:
foreach my $row (@graph)
{
   my ($this_pointX, $this_pointY) = @$row;
   ....
}
##########
Perl:
using Array of Hash:
foreach my $point (@graph) # graph is Array of Hash
                           # meaning an array of pointers
                           # to hash tables
{
   my $this_pointX = $point->{'X_coord'};
   my $this_pointY = $point->{'Y_coord'};
   ....
}
# there can be big advantages to avoiding this
# position dependent [$index] stuff as well as the
# need to pre-declare those indicies, The Perl AoH
# works very well to represent some types of C 2-D arrays.
# It is very easy to imagine how an implementer would
# go in that direction.
[download]

Using Array of Hash for a C 2-D array is a very reasonable thing. The C code to implement a hash table is not huge, but it is non-trivial. If the underlying data could be better represented as a Hash of Array in Perl, then fine. It is very easy to imagine how an implementer would go in the direction of Array of Hash and miss the better Perl implementation of Hash of Array.

I don't understand what you want or mean, sorry.

Could you give me an example of a non trivial XML with a reversable mapping to a nested perl data structure?

For my amateur understanding each XML-tag is from a perl perspective a hash with attributes as keys additionally to tag name and an ordered list of children tags. And the list part can only be represented as an array or a scalar if it's just one element (like a text-string).

The example you gave in the OP is only a special case of a simple schema, where "key" was the tag-name and "value" was a (one element) string.

For sure many DTDs might be much easier - or in your word "non-pathologically" - represented, but thats the general case we are talking about.