Why Does Hash Apparently Reorder Its Internal Representation And Other Associated Ponderings

I doubt it would have helped very much with respect to those responses which are bordering(?) on abusive

(You know the ones that go like: "You're such a dickhead!", which is meant by imputation to be understood as "I'm so smart.", which when given this exposition of what is really being said, I merely ask "Who is the dickhead?" Besides, aren't we supposed to be nice?)

if I had entitled the email slightly more correctly as:

"Why Does Hash Apparently Reorder By Its Internal Representation And Other Associated Ponderings"

That little "By" is important! As the ensuing discussion illustrates, the internal representation could be augmented in such a way so as to allow for it. Gee whiz, even Matz weighed in! Still, there was nowhere given an explicit statement as to the necessity of hashes being ordered, and to claim as much would require that what was written about internal representatons and optimisations (a crap reference to the hash table) be ignored. Even so, my understanding of hashes, well, it isn't very good, not unlike many of my skills; although I have written a few hashing functions some time ago.

Nevertheless, it would appear as if this is something which has been brought up before and appears to have sufficient value to be raised again. I assumed as much. And if it weren't so, then there wouldn't be what I and others appear also to have found to be useful discussion. Furthermore, not everyone has been on the list since the Nineties.

And while I do know how to search the mailing list, I went on to ask about whether it was at all useful to have ordered hashes in spite of lack of explicit support in Ruby. I wasn't asking for support for it, just as to whether I was wanting for something that I might write myself which might be useful and not ugly, or evil as I put it.

I do want it for something. Even so, after having read the differing opinions I don't know whether it should be there in Ruby by default or not. I think a subclass of OrderedHash would be a good compromise. (I'm yet take a look at the supplied code. Thanks for that, I will do...)

What I wanted it for was for honoring the order in which properties/attributes are attached at runtime to an object. I want to access properties by both order and key.

To that end I've subsequently written almost 200 additional lines of code to the following which supports the following:

module Enumerable

   def all_but_first
     d = self.dup
     d.first!
     d
   end

   def all_but_last
     d = self.dup
     d.last!
     d
   end

   def each_but_first
     all_but_first.each do |e|
       yield e
     end
   end

   def each_but_last
     all_but_last.each do |e|
       yield e
     end
   end

end

I liked the idea of having these as methods of Enumerable. Getting this to work for Array was trivial. Hashes were a nightmare and occupied about 80-90% of the additional stuff as it would appear to be consistent with others' experiences. Here's a snippet of that almost 200 lines to give you an idea of the complexity of it:

class Array

   ...

   def sort_by_element_invariant(i)
     self.sort {|x, y| by_element_invariant(x, y, i)}
   end

   def by_element_invariant(x, y, i)
     if x.is_a?(Array) || y.is_a?(Array) && !(x.is_a?(Hash) || y.is_a?(Hash))
       by_array_invariant(x, y, i)
     elsif x.is_a?(Hash) || y.is_a?(Hash) && !(x.is_a?(Array) || y.is_a?(Array))
       by_hash_invariant(x, y, i)
     elsif (x.is_a?(Array) && y.is_a?(Hash)) || (x.is_a?(Hash) && y.is_a?(Array))
       by_array_and_hash_invariant(x, y, i)
     else
       x.to_s <=> y.to_s
     end
   end

   alias_method :sort_by, :sort_by_element_invariant
   alias_method :sort_by_element, :sort_by_element_invariant

   def by_array_invariant(x, y, i)
     if x.is_a?(Array) && is_a?(Array)
       x[i].to_s <=> y[i].to_s
     elsif x.is_a?(Array)
       x[i].to_s <=> y.to_s
     else y.is_a?(Array)
       x.to_s <=> y[i].to_s
     end
   end

   ...

end

The above code was part of what was required to get an aribitrary array to sort, which was in turn used by the extensions to the Hash class. Admittedly as much as a half of the code was written for symmetry and completeness and was not necessarily required for my immediate needs.

The code however will do the following, which I believe to be imperfect as to the consistency of its sorting as yet:

a = [[:b, 2], [:c, 4], :a, 45, "d", ["f"], [2], [:z, 1, 2, 3], {"s"=>"s"}, {:t=>"t"}, {}, {"v"=>"v", "u"=>"u"}]
=> [[:b, 2], [:c, 4], :a, 45, "d", ["f"], [2], [:z, 1, 2, 3], {"s"=>"s"}, {:t=>"t"}, {}, {"v"=>"v", "u"=>"u"}]

a.sort_by_element(0)
=> [{}, {"v"=>"v", "u"=>"u"}, [2], 45, :a, [:b, 2], [:c, 4], "d", {:t=>"t"}, ["f"], {"s"=>"s"}, [:z, 1, 2, 3]]

a.to_h
=> {:z=>[1, 2, 3], 0=>{}, 1=>{"v"=>"v", "u"=>"u"}, 7=>"d", :b=>2, 2=>[2], 8=>{:t=>"t"}, :c=>4, 3=>45, 9=>["f"], 4=>:a, 10=>{"s"=>"s"}}

a.to_h.sort_by_key
=> [[0, {}], [1, {"v"=>"v", "u"=>"u"}], [10, {"s"=>"s"}], [2, [2]], [3, 45], [4, :a], [7, "d"], [8, {:t=>"t"}], [9, ["f"]], [:b, 2], [:c, 4], [:z, [1, 2, 3]]]

a.as_h
=> {{"s"=>"s"}=>{:t=>"t"}, "d"=>["f"], [2]=>[:z, 1, 2, 3], {}=>{"v"=>"v", "u"=>"u"}, :a=>45, [:b, 2]=>[:c, 4]}

a.as_h.sort_by_key
=> [[{}, {"v"=>"v", "u"=>"u"}], [[2], [:z, 1, 2, 3]], [:a, 45], [[:b, 2], [:c, 4]], ["d", ["f"]], [{"s"=>"s"}, {:t=>"t"}]]

Yeah, it needs some tweaking!... It works fine for all but the most bizarre sets of objects.

And thanks to the discussion of that 55 lines of code I may implement something of the sort (pun only intended later) which implements an array to do ordering support as I go, rather than, or in addition to subsequent ordering by sorting.

Finally, to those who would take aim, I say "Piss off!', I'm quite capable of such of myself with respect to myself. Such attitudes will have a chiling effect on those who might be able to contribute given the opportunity and I refuse to cower to arrogance such as yours. Stupid and annoying people are best ignored. I'm happy to be ignored until I say something useful. Which means I myself should've written nothing of it, but anyway... Is it a deal?

Meanwhile, "I'm off to grow some hair on my tongue.", he says in an unconvincing attempt at a gruff voice...

<thoran@thoran.com> wrote in message
news:eff13236bdf3690ff2f43722eba7ddd0@shiny...

I doubt it would have helped very much with respect to those responses
which are bordering(?) on abusive

    I've been watching this thread intently and I don't recall anyone being
abusive or even close to it. Could you site an example?

(You know the ones that go like: "You're such a dickhead!", which is
meant by imputation to be understood as "I'm so smart.", which when given
this exposition of what is really being said, I merely ask "Who is the
dickhead?" Besides, aren't we supposed to be nice?)

    Again, I don't recall any insults or self posturing. To what are you
referring, specifically?

And while I do know how to search the mailing list, I went on to ask
about whether it was at all useful to have ordered hashes in spite of
lack of explicit support in Ruby. I wasn't asking for support for it,
just as to whether I was wanting for something that I might write myself
which might be useful and not ugly, or evil as I put it.

    Well, to be fair, you did more than this. You suggested that, perhaps,
hashes are actually ordered and that none of us really knows what a hash
is... You also accused it of not following the PoLS, which many Ruby
programmers feel strongly about. Considering people's knowledge of hashes,
even outside the context of Ruby, and your self proclaimed ignorance
(although this was not in your original post), these are bold statements
and are bound to illicit bold responses.
    Personally, I feel you are misunderstanding the PoLS but I've already
addressed that in another post.

Finally, to those who would take aim, I say "Piss off!', I'm quite
capable of such of myself with respect to myself. Such attitudes will
have a chiling effect on those who might be able to contribute given the
opportunity and I refuse to cower to arrogance such as yours. Stupid and
annoying people are best ignored. I'm happy to be ignored until I say
something useful. Which means I myself should've written nothing of it,
but anyway... Is it a deal?

    Again, who is taking aim? Perhaps you're looking for antagonism where
there is none?
    People are responding to you to help you and there has been no attack
that I'm aware of. I am interested in what you interpret as an attack,
which is why I'm asking for specific examples. If people are attacking
you, this would go a long way to quell that...

Hash doesn't reorder, though. The nature of a Hash is that it is an
unordered collection. There is a use case for an ordered associative
collection, but it's not a Hash as such. So, asking even the modified
question will present a similar problem -- you're wanting something
that isn't a floor wax or a dessert topping. Granted, I want the same
thing (sometimes), but I also recognise that it isn't (properly
speaking) a Hash at that point.

The only thing that really counts against you in all of this is that
there was a discussion about this not two weeks before, IIRC, and some
people reacted to that. It's not just a long-term discussion, it's
recent, too.

-austin

···

On 8/21/06, thoran @ thoran. com <thoran@thoran.com> wrote:

"Why Does Hash Apparently Reorder By Its Internal Representation And
Other Associated Ponderings"

--
Austin Ziegler * halostatue@gmail.com * http://www.halostatue.ca/
               * austin@halostatue.ca * http://www.halostatue.ca/feed/
               * austin@zieglers.ca

Sorry for the poor attempt at quoting and the ignorance of the convention, but my mail client seems to be crapping out at the size of the ruby-talk mailbox!?...

As to the following:

"Well, to be fair, you did more than this. You suggested that, perhaps,
hashes are actually ordered and that none of us really knows what a hash
is... You also accused it of not following the PoLS, which many Ruby
programmers feel strongly about. Considering people's knowledge of hashes,
even outside the context of Ruby, and your self proclaimed ignorance
(although this was not in your original post), these are bold statements
and are bound to illicit bold responses."

I wrote: "It doesn't seem very PoLS to have it reordered, although perhaps one shouldn't be surprised that a hash is unordered?"

This is not a bold statement. I don't understand how you could have understood that as a suggestion that "hashes are actually ordered"? It looks more like a question to me and reeks of doubt as to whether my (increasingly formerly held) expectation was correct or reasonable...

More generally:

I assume that something works as it should, then ask why I might be wrong first. That is what I was doing. If after having considered what design decisions are entailed, I might start to consider that something is wrong. I hadn't gotten to this point yet.

Perhaps I was expecting more of an ordered associative array as someone else suggested that it might be called if such a thing were to exist.

As to one's ignorance. I think that the beginner's mind should be one's default starting position at all times, since it allows one to critique one's self more readily. Such is imbued with a calm doubt.

As to the following:

"Personally, I feel you are misunderstanding the PoLS but I've already
addressed that in another post."

As you wrote, if I'm surprised that rand() produces different numbers, then I am still surprised. The question is as to whether it is reasonable to be surprised. What is the base of expectations? What is a reasonable expectation of what hashes will and won't do?

More generally:

Also, to whomever said that that I had said or implied as much, I never made the claim that Matz had used the term PoLS. I may have made that claim, given or having taken the opportunity to do so, but I haven't.

I am not inclined to 'dumb down' Ruby. If I wanted to be straight-jacketed or kept out of the drawer with all the sharp knives, then I'd be using Python. (That there IS a bold statement.)

So, if the use of the {} notation for Hash is not to include ordering because on balance it is preferred for reasons of speed/size not to include ordering and because it is reasonable to expect that a hash won't by default be ordered, then OK.

Ruby must balance power with simplicity, and elegance with complexity.

Just Another Victim of the Ambient Morality wrote:

I've been watching this thread intently and I don't recall anyone being
abusive or even close to it. Could you site an example?

Personally, I perceived the beginning of Philip's original terse
response as containing a little bit of the holier-than-thou attitude
the OP was referring to:

I was surprised to find the following...

Really? Take a comsci course at uni

That could be interpretted as:
"Are you so much of a dumbass that you don't even know what a hash is?
Try going to school, moron."
or far more kindly as:
"Interesting. What you find confusing actually makes perfect sense to
me. That's how I was taught hashes behave, anyhow."

Blame the impersonal nature of the written word.

(My intent here is not to attack Philip, but instead to provide an
example of how the original poster might have felt that some responses
had a bit of 'attitude' to them.)

<thoran@thoran.com> wrote in message
news:c65d5289beae381352039cc498d11116@shiny...

Sorry for the poor attempt at quoting and the ignorance of the
convention, but my mail client seems to be crapping out at the size of
the ruby-talk mailbox!?...

As to the following:

"Well, to be fair, you did more than this. You suggested that, perhaps,
hashes are actually ordered and that none of us really knows what a hash
is... You also accused it of not following the PoLS, which many Ruby
programmers feel strongly about. Considering people's knowledge of
hashes,
even outside the context of Ruby, and your self proclaimed ignorance
(although this was not in your original post), these are bold statements
and are bound to illicit bold responses."

I wrote: "It doesn't seem very PoLS to have it reordered, although
perhaps one shouldn't be surprised that a hash is unordered?"

This is not a bold statement. I don't understand how you could have
understood that as a suggestion that "hashes are actually ordered"? It
looks more like a question to me and reeks of doubt as to whether my
(increasingly formerly held) expectation was correct or reasonable...

    This is so dishonest of you. You take one sentence and remove all the
context around it and then proclaim "this is not a bold statement." Here's
what you said in it's entirety:

It doesn't seem very PoLS to have it reordered, although perhaps one
shouldn't be surprised that a hash is unordered? Perhaps Matz is
convincing us of this statement? Said Matz unto the flock in a loud,
Godly voice: "Make no assumptions about the order of hashes!"

    This is a bold statement, especially from a self proclaimed newbie.
You're suggesting that the only reason that people accept that hash
elements are unordered is because Matz says so and we're just blindly
believe him without checking up on these ideas, ourselves. All this, on
top of the (erroneous) assumption, that you made, that hashes are
inherently ordered. What gave you this idea, by the way?

As to one's ignorance. I think that the beginner's mind should be one's
default starting position at all times, since it allows one to critique
one's self more readily. Such is imbued with a calm doubt.

    I'm not sure what you're getting at, here. Are you saying we should
keep the beginner in mind when programming, or designin a programming
language, or when addressing questions about programming?

As to the following:

"Personally, I feel you are misunderstanding the PoLS but I've already
addressed that in another post."

As you wrote, if I'm surprised that rand() produces different numbers,
then I am still surprised. The question is as to whether it is
reasonable to be surprised. What is the base of expectations? What is a
reasonable expectation of what hashes will and won't do?

    That's exactly the problem. Because expectations are so subjective,
it's unreasonable to say "hey, I'm surprised!" and declare that the PoLS
was broken. Who's to say why you were surprised or objectively say if your
surprise was "reasonable" or not.
    Instead, it's more prudent to say whether something is consistent or
not. Personally, I interpret the PoLS as meaning this: if you know the
language well, then the language will cease to surprise you. At first,
this may seem like a tautology. How can a language surprise you if you
know it so well? The point is that there are ways a language can surprise
you even if you "know it well." For instance, if a language is highly
inconsistent, then even if you know most of the rules of the language, the
exceptions can still confuse you and cause you to make an error and, thus,
surprise you. Python has traits like this, for instance.

More generally:

Also, to whomever said that that I had said or implied as much, I never
made the claim that Matz had used the term PoLS. I may have made that
claim, given or having taken the opportunity to do so, but I haven't.

    No one said that you said this.
    I was saying that even Matz doesn't use this term to describe his own
language, so you might think twice about doing so...

I am not inclined to 'dumb down' Ruby. If I wanted to be
straight-jacketed or kept out of the drawer with all the sharp knives,
then I'd be using Python. (That there IS a bold statement.)

    I have no idea what this paragraph means.

Ruby must balance power with simplicity, and elegance with complexity.

    ...and it does...

Um. This is an overstatement. Hashes aren't ordered by default because
hashing is an order-ignorant operation.

Yes, you've heard people -- including me -- saying that having
something that knows its insertion order would be good if it's
natively in C-Ruby because then we could have a literal constructor (I
am inclined to agree with Hal at this point that [ a => b, b => c, c
=> d ] is a good choice) and we wouldn't have umpteen-dozen different
implementations of this which *is* needed from time to time, but not
necessary as a standard behaviour.

It would be ordered and have arbitrary key values, but it would not,
in fact, be a Hash. That's the point that some folks have tried to
make about this.

-austin

···

On 8/21/06, thoran @ thoran. com <thoran@thoran.com> wrote:

So, if the use of the {} notation for Hash is not to include ordering
because on balance it is preferred for reasons of speed/size not to
include ordering and because it is reasonable to expect that a hash
won't by default be ordered, then OK.

--
Austin Ziegler * halostatue@gmail.com * http://www.halostatue.ca/
               * austin@halostatue.ca * http://www.halostatue.ca/feed/
               * austin@zieglers.ca

Phrogz wrote:

Personally, I perceived the beginning of Philip's original terse

(My public apologies to Phillip for twice misspelling his name.)

"Phrogz" <gavin@refinery.com> wrote in message
news:1156189774.152645.230420@i3g2000cwc.googlegroups.com...

Just Another Victim of the Ambient Morality wrote:

I've been watching this thread intently and I don't recall anyone being
abusive or even close to it. Could you site an example?

Personally, I perceived the beginning of Philip's original terse
response as containing a little bit of the holier-than-thou attitude
the OP was referring to:

I was surprised to find the following...

Really? Take a comsci course at uni

That could be interpretted as:
"Are you so much of a dumbass that you don't even know what a hash is?
Try going to school, moron."
or far more kindly as:
"Interesting. What you find confusing actually makes perfect sense to
me. That's how I was taught hashes behave, anyhow."

Blame the impersonal nature of the written word.

(My intent here is not to attack Philip, but instead to provide an
example of how the original poster might have felt that some responses
had a bit of 'attitude' to them.)

    These are good examples and your point is well taken...

    Personally, I would hope that people won't take the pessimistic
interpretation of everything they read. For instance, I took that sentence
to mean "this is so common that it's standard teaching at anywhere that
would teach the subject," and I read absolutely no value judgements into it
but, then again, perhaps there was malice in that sentence and I just chose
not to see it. I'm unsure whether this is a bad thing or not...

I blame deadlines, insufficient caffeine and cold weather :stuck_out_tongue:

My intent was that the poster should find information about the
meaning of the word 'hash' in computer science, as it would explain
the entire issue they're having.

PHP has associative arrays, which are completely different from
hashes. As for JavaScript, objects appear to retain their keys in
insertion order, but objects aren't hashes.

I've spent the past two years hacking away with PHP and JavaScript. I
get to do Python next, yay!

···

On 8/22/06, Phrogz <gavin@refinery.com> wrote:

Just Another Victim of the Ambient Morality wrote:
> I've been watching this thread intently and I don't recall anyone being
> abusive or even close to it. Could you site an example?

Personally, I perceived the beginning of Philip's original terse
response as containing a little bit of the holier-than-thou attitude
the OP was referring to:

>> I was surprised to find the following...
> Really? Take a comsci course at uni

That could be interpretted as:
"Are you so much of a dumbass that you don't even know what a hash is?
Try going to school, moron."
or far more kindly as:
"Interesting. What you find confusing actually makes perfect sense to
me. That's how I was taught hashes behave, anyhow."

Blame the impersonal nature of the written word.

(My intent here is not to attack Philip, but instead to provide an
example of how the original poster might have felt that some responses
had a bit of 'attitude' to them.)

--
Phillip Hutchings
http://www.sitharus.com/

It is a Hash, since it provides it's interface and general performance
characteristics. It just supplies the new guarantee of insertion
ordering.

I've wanted one a few times, instead of nested arrays, mostly because
writing something like ['a' => 'b', 'c' => 'd'] would look better than
[['a','b'],['c','d']]. I'd still iterate both with somename.each{|key,
value> ...}.

I've written code where I needed both the order and the random access.
An example was a list of fields, each with an associated hash of
options. I ended up declaring an array for the fields and then a hash
of hashes to store the options. An ordered hash would have solved this
neatly.

A lot of people seem to want this so why not create a standard OHash?
A nice syntax like the [1=>2] one would be great as well.

Pedro.

···

On 8/22/06, Austin Ziegler <halostatue@gmail.com> wrote:

It would be ordered and have arbitrary key values, but it would not,
in fact, be a Hash. That's the point that some folks have tried to
make about this.

No, I'd say it's hash-like, but not a hash in the "proper" sense of
the term. From an interface perspective, you're right that it doesn't
matter to the Rubyist on the street. But Hashes are, as has been
repeated many times, an unordered collection. Imposing order on a Hash
(even insertion order) changes the type of collection that it is --
even if it's useful, which I have already granted. (Of course, I would
need to -- since I've implemented one myself for PDF::Writer.)

-austin

···

On 8/22/06, Pedro Côrte-Real <pedro@pedrocr.net> wrote:

It is a Hash, since it provides it's interface and general performance
characteristics. It just supplies the new guarantee of insertion
ordering.

--
Austin Ziegler * halostatue@gmail.com * http://www.halostatue.ca/
               * austin@halostatue.ca * http://www.halostatue.ca/feed/
               * austin@zieglers.ca

Pedro Côrte-Real wrote:

It would be ordered and have arbitrary key values, but it would not,
in fact, be a Hash. That's the point that some folks have tried to
make about this.

It is a Hash, since it provides it's interface and general performance
characteristics. It just supplies the new guarantee of insertion
ordering.

If you capitalize Hash (naming the Ruby class) that is arguably true.
But in the CS sense, a hash is not ordered.

A lot of people seem to want this so why not create a standard OHash?
A nice syntax like the [1=>2] one would be great as well.

I think I'll address a few more issues and then write this up as
an RCR.

If you don't see it in ten days, nag me. :wink:

Cheers,
Hal

···

On 8/22/06, Austin Ziegler <halostatue@gmail.com> wrote:

This syntax is already valid but with a different meaning:

class A
   def [](arg)
     arg
   end
end

p A.new[1] # 1
p A.new[1=>2] # {1 => 2} (a hash instance)

The [1=>2] syntax is a method call in disguise. Not sure what
ambiguities might be hidden in trying to interpret that as a method
call in some places and as an ordered hash literal in others.

Gary Wright

···

On Aug 22, 2006, at 6:22 AM, Pedro Côrte-Real wrote:

A lot of people seem to want this so why not create a standard OHash?
A nice syntax like the [1=>2] one would be great as well.

If you define hash like that, sure. But I would say hashes aren't
defined as being unordered it's just that no order is usually defined
or enforced. I'd define a hash as something that maps keys to values
using a hash function. An OrderedHash can still be a subclass of Hash
since it upholds the Liskov substitution principle and is thus still a
hash.

But this is just semantics and doesn't really matter.

Pedro.

···

On 8/22/06, Austin Ziegler <halostatue@gmail.com> wrote:

But Hashes are, as has been
repeated many times, an unordered collection. Imposing order on a Hash
(even insertion order) changes the type of collection that it is --
even if it's useful, which I have already granted. (Of course, I would
need to -- since I've implemented one myself for PDF::Writer.)