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

[herveus]

Howdy!

In practice perls data structures are as shifty as the language itself and you can implement hashes in arrays as well as arrays in hashes. So the sentence "arrays are ordered and hashes are not" (I hope we all concur by now that 'sorted' was the wrong word) is merely a short form for "arrays provide built-in infrastructure to manipulate ordered values in an efficient manner, while hashes do not"

Hashes and arrays are reasonably well defined fundamental data types in Perl. I'd say "clearly defined", but this thread casts doubt on that assertion. Only at a conceptual level can you really assert that equivalency in the second sentence. Arrays and hashes are very strong data types in Perl. You cannot cast one into the other. You can use certain operations on each to produce instances of the other (conflating lists with arrays here). Those operators are not type casters, however.

In your code example, you first put a value in to the array at index 4. This causes indexes 0 through 3 to spring into existence, but, naturally, they have no defined value. When you then shift off the first value to print it, you get index 0 (the "first" value) and, being undefined, triggers the warning that you asked to have happen. It is unclear what that was meant to demonstrate.

Later you speak of push/pop and how they are not defined for hashes. Of course. Push and pop (and shift and unshift) are all curried versions of splice, which is the general purpose function for mucking about with arrays. Since a hash isn't (and can't be coerced into) an array, splice can't do anything with one. Likewise, keys() and values() and each() are not defined for arrays. The two data types are very distinct. I'm not sure what you are trying to say there. It makes no sense.

[jethro]

Your second-to-last sentence is part of what I am trying to say. Ikegami (as I understand his post) proposes that the ordering of keys intrinsic to an array isn't a difference to a hash because a hash can simulate that (and because internally there is an ordering in a hash anyway). My argument is that
a) what perl does internally is beside the point and
b) if we argue that a hash is as ordered as an array because we can make it so, then all arguments about differences of data types become meaningless because every data type can simulate every other data type.

[herveus]

Howdy!

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.

[jethro]

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.