Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

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

by ikegami (Pope)
on Jun 01, 2009 at 18:12 UTC ( #767344=note: print w/replies, xml ) Need Help??


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

So hashes aren't ordered because the following doesn't work?

$h{foo} = 'a'; $h{bar} = 'b'; $h{baz} = 'c'; is(join(' ', values(%h)), "a b c");

I guess arrays aren't ordered either, then.

$a[2] = 'a'; $a[0] = 'b'; $a[1] = 'c'; is("@a", "a b c");

Order has to be imposed externally on the data in the case of arrays too. It's just there's a convenient way of doing that when the keyspace isn't sparse (namely, the range operator).

Replies are listed 'Best First'.
Re^7: What makes an array sorted and a hash unsorted?
by Roy Johnson (Monsignor) on Jun 01, 2009 at 18:45 UTC
    You're trying too hard. You're now saying that there must be exactly one kind of ordering that constitutes ordering, and nothing else can be considered ordered. Or that every ordering must be implemented for a thing to be considered ordered. I'm not sure which you're contending; they're both pretty stupid notions, which is why it surprises me to see you pushing it as a serious argument.

    Order has to be imposed externally on the data in the case of arrays too.
    No, order is intrinsic to arrays. Not every possible order, but the one that is intrinsic. Any other ordering would have to be imposed. Arrays have one intrinsic ordering. Hashes have zero intrinsic orderings.


    Caution: Contents may have been coded under pressure.

      I'm not sure which you're contending

      I'm saying there's no difference between hash and arrays expect in the order they choose to return their values. A hash could return its values in the same order as an array. And if it did, people would still ask how to sort hashes.

      With which of these premises do you disagree?

      Arrays have one intrinsic ordering. Hashes have zero intrinsic orderings.

      So? Even if hashes had an intrinsic ordering, the same problems faced today would still exist. There's more to it than that, or the answer to the posts we see isn't "hashes aren't ordered".

        I'm saying there's no difference between hash and arrays except in the order they choose to return their values.
        I don't think you're really contending that. It's obviously not true as stated. They are syntactically, functionally, and internally quite different. At a very abstract level, they're notionally about the same: collections of scalars that are indexable. If, by "return their values" you include the notion of having a "first (etc.) element", so that stacks and queues can be implemented, then I suppose that's the major difference (apart from being able to index a hash by string). So I'm still a bit unclear on your point. I kind of get it, but not really.

        I agree that people would still ask how to sort hashes, just as they currently ask how to sort arrays or lists. When they ask how to sort something, they indicate that they know they need to sort it.

        When people say (or hint that they think) that they have a hash whose elements are in some particular order, the answer is "hashes aren't ordered". It is a misconception people have about hashes. Once that misconception has been addressed, the question of how to solve their problem can be addressed. I don't think anyone has suggested that "hashes aren't ordered" is all anybody needs to know about them.

        If hashes had an intrinsic order, but people operated as if they had a different intrinsic order, we'd be telling them "hashes aren't ordered that way, they're ordered this way." Then we'd still have the issue of whatever particular thing the user is trying to accomplish. So the response wouldn't be all that different.


        Caution: Contents may have been coded under pressure.
        Howdy!

        When you obtain the list of keys or values from a hash, you no longer have a hash. You have a list, which has an intrinsic order. The mechanism for extracting that list from the hash must traverse the internal data structures in some order to produce the list, but that sequence is explicitly undefined. That is the essence of being unordered.

        It makes no sense to say "A hash could return its values in the same order as an array." The statement presupposes that you can predict the order of the list of keys. You can't do that.

        If your collection imposes a predictable ordering on the indexes/keys, you can iterate over it directly. Iteration relies on order. That's why iterating over the contents of a hash requires helper functions to manage it. Something has to convert the set of key-value pairs into a list. The resulting list may be invisible to the user (as in each()), or explicitly returned (keys(), values()), but it's there. Saying (%foo) also converts the hash into a list. It's no longer a hash at that point.

        Operations over collections, whether ordered or not, may wish to impose an externally defined ordering on a list of the data. That is independent of whether the collection itself is intrinsically ordered. If you want your collection to maintain the data in a specific order, you are stuck with an array, if you intend to use basic Perl data structures. Linked lists and the like are outside the scope of this discourse. Alternately, you impose the desired order on a list each time you generate the list.

        To an extent, it really is that simple.

        yours,
        Michael

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://767344]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (2)
As of 2021-10-28 00:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My first memorable Perl project was:







    Results (95 votes). Check out past polls.

    Notices?