Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

Re^4: What makes an array sorted and a hash unsorted?

by herveus (Parson)
on Jun 05, 2009 at 13:43 UTC ( #768798=note: print w/replies, xml ) Need Help??

in reply to Re^3: What makes an array sorted and a hash unsorted?
in thread What makes an array sorted and a hash unsorted?


I posted some sample code that demonstrates that inserting a key into a hash can change the order of the keys that were present before that insertion. That shows that the keys are inherently unordered. If you us one of the modules out there to hack the inner workings of a hash to control the order of keys you get when calling keys(), it's not a plain hash anymore.

Through the magic of tie and overload and XS, you can subvert and pervert the behavior of things, but that doesn't change the fundamental data types of scalar, hash, and array. Claiming that a hash is ordered is silly, on a par with claiming that pi is actually equal to 3. Being ordered implies a level of stability. If key X comes "before" key Y now, then orderedness implies that no sequence of insertions and deletions that do not invove X or Y will change that. It turned out to be trivial to demonstrate that that condition does not hold.

  • Comment on Re^4: What makes an array sorted and a hash unsorted?

Replies are listed 'Best First'.
Re^5: What makes an array sorted and a hash unsorted?
by jethro (Monsignor) on Jun 05, 2009 at 16:54 UTC

    It's not as easy as that (I'm playing Ikegamis adovate now ;-). One could make the argument that a hash %h=(0,'a',1,'b',2,'c'); and an array @a=('a','b','c'); are both ordered in the same way. No sequence of equivalent insertions and deletions will change that both will look the same when you print them with

    print $h{$_},$a[$_] for (0..@a-1);

    In older languages that would have been the only way to access arrays and print them.

    That orderedness of the hash only breaks when you use print @a for which there is no direct substitute on the hash side (but could be built in a way that it comes out ordered). If you access them with a foreach (keys ...) loop, then you might as well use a foreach (sort keys ...) loop.

    Of course you get a random list when you call keys(). But what if perl had a built-in function arraykeys() which gave back the numbers of the array in a random ordering. Would arrays then be both ordered and unordered or partially ordered or not ordered at all?. What if you had no keys() and each() functions in perl? Would a hash then be ordered or undefined in its orderedness?

    As I said before, I am of the opinion that perl hashes are unordered and arrays are ordered, but proving it is not as simple as one might think.

      That orderedness of the hash only breaks when you use print @a for which there is no direct substitute on the hash side

      values %h is the direct equivalent of @a. (And 0..$#a is a close equivalent to keys %h, but this equivalence isn't as close as the equivalence between values %h and @a.)

      The order of the values returned is (indirectly) intentionally rather hard to predict, quite the opposite of many meanings of "sorted". But I'm not particularly interested in discussing how to split hairs in the definition of "sorted" or even "ordered" nor to split hairs in discussing whether the resulting definition(s) apply to Perl hashes. :)

      - tye        


      You're moving the goalposts.

      When you print $h{$_}, you are imposing an order by the sequence of values you assign to $_. The output sequence you are generating is not intrinsic to the hash, but extrinsic.

      Your definition of %h is also flawed. You can construct a hash from a list in the manner you do, but there is no assurance that the list you get by saying (%h) will be the same as the list you used to construct the hash.

      You don't get a random list when you call keys(). The ordering of the keys is unpredictable at that level. It is deterministic, in that calling keys() repeatedly will give the same list until you add or delete an element from the hash. Then it may come back with a reordered list. The hypothetical "what if perl had" or "what if perl didn't have" questions look like attempts to redefine the question to make it complicated again.


        You're moving the goalposts

        Yes, and I'm offering flawed arguments, because ultimately we know that hashes are not ordered. Very much a senseless discussion by now. Still hoping to get the last word ;-).

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://768798]
[LanX]: every path must have l left and r right edges and l and r are fixed and l+r is the height
[LanX]: simple recursive function which goes left and right till l or r are exhausted
LanX #solved
[oiskuu]: I must watch Police Academy again sometime.
[Discipulus]: thanks all
[LanX]: ?

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (7)
As of 2018-03-19 11:26 GMT
Find Nodes?
    Voting Booth?
    When I think of a mole I think of:

    Results (239 votes). Check out past polls.