A use case for an ordered hash

ruby-talk
1

There have been numerous occasions when I wanted an
ordered hash, but usually I can't remember to write
them down.

Here's just one.

Once I wanted a "dynamic case statement" of sorts.
I wanted to use procs as values in a hash. Something
like:

    actions = { /abcd/ => lambda { do_this },
                /xyz/ => lambda { do_that },
                /abc/ => lambda { other }}

Then I could just iterate through the keys looking
for a match, then use that key to find the associated
proc and call it.

However, I quickly noticed that this is no good. The
order of iteration is unpredictable. So I couldn't
guarantee that (for example) /abcd/ would be tested
before /abc/, and so on.

So yeah, I ended up using an array of arrays. But it
just felt wrong.

Hal

2

Hal Fulton wrote:

There have been numerous occasions when I wanted an
ordered hash, but usually I can't remember to write
them down.

Here's just one.

Once I wanted a "dynamic case statement" of sorts.
I wanted to use procs as values in a hash. Something
like:

   actions = { /abcd/ => lambda { do_this },
               /xyz/ => lambda { do_that },
               /abc/ => lambda { other }}

Then I could just iterate through the keys looking
for a match, then use that key to find the associated
proc and call it.

However, I quickly noticed that this is no good. The
order of iteration is unpredictable. So I couldn't
guarantee that (for example) /abcd/ would be tested
before /abc/, and so on.

So yeah, I ended up using an array of arrays. But it
just felt wrong.

Hal

That sort of code is what Chuck Moore evolved into Forth. :slight_smile: Seriously, though, isn't there a way to do this with a single array? Store the patterns followed by the lambdas in sequence. Find the first index that matches the pattern and take the lambda at [index+1]? Or two parallel arrays? I use two parallel arrays for this sort of thing a lot -- it's easy for me to read, given my FORTRAN background. :slight_smile:

3

actions.keys.sort {|a,b| b.to_s <=> a.to_s}.each {|k|
  if k =~ your_string
    actions[k].call
    break
  end
}

A more-greedy regex sorts lexicographically behind a head-matching
less-greedy one.

···

On 8/13/06, Hal Fulton <hal9000@hypermetrics.com> wrote:

    actions = { /abcd/ => lambda { do_this },
                /xyz/ => lambda { do_that },
                /abc/ => lambda { other }}

4

Hal Fulton wrote:

There have been numerous occasions when I wanted an
ordered hash, but usually I can't remember to write
them down.

Here's just one.

Once I wanted a "dynamic case statement" of sorts.
I wanted to use procs as values in a hash. Something
like:

   actions = { /abcd/ => lambda { do_this },
               /xyz/ => lambda { do_that },
               /abc/ => lambda { other }}

Then I could just iterate through the keys looking
for a match, then use that key to find the associated
proc and call it.

However, I quickly noticed that this is no good. The
order of iteration is unpredictable. So I couldn't
guarantee that (for example) /abcd/ would be tested
before /abc/, and so on.

So yeah, I ended up using an array of arrays. But it
just felt wrong.

To me a Hash feels wrong. Why? Because you don't make any use of hash properties for fast lookup. You just iterate in plain order.

Kind regards

  robert

5

I'm in the habit of automagically writing...

   hash.keys.sort

or sometimes

   hash.keys.sort_by{|k| hash[k]}.each{|k| value=hash[k]; ... }

It's just such a common idiom in my code I think I should push it into
my little collection of standard extensions to standard objects.

Why is it so common? Nobody wants a script that does very things in a
very different order depending on very small changes.

* You just spend too long explaining to people why this happens.
* Makes sporadic bugs even harder to find (it works for me, but customer is whinging)
* The results tend not to be comparable (can't diff) or repeatable.

John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@tait.co.nz
New Zealand

Carter's Clarification of Murphy's Law.

"Things only ever go right so that they may go more spectacularly wrong later."

From this principle, all of life and physics may be deduced.

···

On Sun, 13 Aug 2006, Hal Fulton wrote:

There have been numerous occasions when I wanted an
ordered hash, but usually I can't remember to write
them down.

6

Hal Fulton wrote:

There have been numerous occasions when I wanted an
ordered hash, but usually I can't remember to write
them down.

Here's my latest one[1]:

I had a string with a bunch of tagged "tolerance fields",
e.g., >>1+/-10% 'tag'<< (a mini DSL?). Based on some sort
of distribution function, e.g., uniform or Gaussian,
I generated an array of samples for each tagged field.
A regular hash was a perfect fit,

   samples[tag] = [ sample1, sample2, .. ]

*until* another requirement came up: to present the tags
in order of appearance.

Later,

···

--
Bil
http://fun3d.larc.nasa.gov

[1] Part of a CEV (Crew Exploration Vehicle) task

7

Hal Fulton wrote:

There have been numerous occasions when I wanted an
ordered hash, but usually I can't remember to write
them down.

Here's just one.

Once I wanted a "dynamic case statement" of sorts.
I wanted to use procs as values in a hash. Something
like:

    actions = { /abcd/ => lambda { do_this },
                /xyz/ => lambda { do_that },
                /abc/ => lambda { other }}

Then I could just iterate through the keys looking
for a match, then use that key to find the associated
proc and call it.

However, I quickly noticed that this is no good. The
order of iteration is unpredictable. So I couldn't
guarantee that (for example) /abcd/ would be tested
before /abc/, and so on.

So yeah, I ended up using an array of arrays. But it
just felt wrong.

Hal

Can't you create your own using mixins and including enumerable or
something like that ?

8

M. Edward (Ed) Borasky wrote:

That sort of code is what Chuck Moore evolved into Forth. :slight_smile: Seriously, though, isn't there a way to do this with a single array? Store the patterns followed by the lambdas in sequence. Find the first index that matches the pattern and take the lambda at [index+1]? Or two parallel arrays? I use two parallel arrays for this sort of thing a lot -- it's easy for me to read, given my FORTRAN background. :slight_smile:

Yes, I could use a single flat array... I could also program
in FORTRAN... :wink:

Hal

9

Francis Cianfrocca wrote:

···

On 8/13/06, Hal Fulton <hal9000@hypermetrics.com> wrote:

    actions = { /abcd/ => lambda { do_this },
                /xyz/ => lambda { do_that },
                /abc/ => lambda { other }}

actions.keys.sort {|a,b| b.to_s <=> a.to_s}.each {|k|
if k =~ your_string
   actions[k].call
   break
end
}

A more-greedy regex sorts lexicographically behind a head-matching
less-greedy one.

Clever workaround. Thanks for that.

There are all kinds of workarounds for situations like these.

I don't *need* an ordered hash. I don't even *need* a case
statement, as I could do the same thing with a bunch of ifs.
And so on.

Hal

10

Absolutely... an Array is perfect for ordered information.

actions = [
  { /abcd/ => lambda { do_this } },
  { /xyz/ => lambda { do_that } },
  { /abc/ => lambda { other } }
]

Then, all you do is...

actions.select { |action| action[input] }

where input = /xyz/ you will receive the appropriate hash (key and
Proc) in an array. So, to do something with that, you could...

actions.select { |action| action[input] }.first[input].call

which calls the Proc associated with the matching element.

I'm not too thrilled with its convolutedness, and I'm sure there's a
better way, but I'm pretty sleepy, so this is the best I'm coming up
with right now. :slight_smile: As always, you can write a method to hide the gory
details.

def exec_route input
  actions.select { |action| action[input] }.first[input].call
end

and just call:

exec_route /xyz/

and blam! do_that is executed!

Hope this helps.

M.T.

11

He *is* making use of a Hash property. He wants the keys to be unique. None of the other solutions shown in this thread have addressed that.

James Edward Gray II

···

On Aug 13, 2006, at 3:25 AM, Robert Klemme wrote:

Hal Fulton wrote:

There have been numerous occasions when I wanted an
ordered hash, but usually I can't remember to write
them down.
Here's just one.
Once I wanted a "dynamic case statement" of sorts.
I wanted to use procs as values in a hash. Something
like:
   actions = { /abcd/ => lambda { do_this },
               /xyz/ => lambda { do_that },
               /abc/ => lambda { other }}
Then I could just iterate through the keys looking
for a match, then use that key to find the associated
proc and call it.
However, I quickly noticed that this is no good. The
order of iteration is unpredictable. So I couldn't
guarantee that (for example) /abcd/ would be tested
before /abc/, and so on.
So yeah, I ended up using an array of arrays. But it
just felt wrong.

To me a Hash feels wrong. Why? Because you don't make any use of hash properties for fast lookup. You just iterate in plain order.

12

Robert Klemme wrote:

So yeah, I ended up using an array of arrays. But it
just felt wrong.

To me a Hash feels wrong. Why? Because you don't make any use of hash properties for fast lookup. You just iterate in plain order.

I never use a hash for fast lookup. I use it because it
allows me easily to associate an arbitrary key with a
value.

Hal

13

. . . but if you want them in a *specific* order (other than that
provided by .sort), you'll have to write your own method, of course.

···

On Mon, Aug 14, 2006 at 06:17:34AM +0900, John Carter wrote:

I'm in the habit of automagically writing...

  hash.keys.sort

--
CCD CopyWrite Chad Perrin [ http://ccd.apotheon.org ]
This sig for rent: a Signify v1.14 production from http://www.debian.org/

14

In the case that Hal is talking about, and in the case where
PDF::Writer uses an ordered hash, this would be inappropriate.
Insertion-ordered associations are generally better. I will probably
be modifying PDF::Writer a bit to make it clear that it's using an
ordered association, not an ordered "hash", but it would be useful to
have an ordered association. Maybe we *could* take advantage of a
literal for this:

  ordered_assoc = ( 1 => 2, 2 => 3, 'a' => 5 )

Maybe. For Ruby 2.0.

-austin

···

On 8/13/06, John Carter <john.carter@tait.co.nz> wrote:

I'm in the habit of automagically writing...

   hash.keys.sort

or sometimes

   hash.keys.sort_by{|k| hash[k]}.each{|k| value=hash[k]; ... }

--
Austin Ziegler * halostatue@gmail.com * http://www.halostatue.ca/
               * austin@halostatue.ca * You are in a maze of twisty little passages, all alike. // halo • statue
               * austin@zieglers.ca

15

I've had to deal with this (interestingly, in something that was
*intended* as a DSL). Just add another field to the structure you
store in the hash and have it increment a global sequence number when
you create it. A little clunky but later you can say:

hash.values.sort {|a,b| a.seq <=> b.seq}.each {|v|
  # whatever
}

···

On 8/14/06, Bil Kleb <Bil.Kleb@nasa.gov> wrote:

Here's my latest one[1]:

I had a string with a bunch of tagged "tolerance fields",
e.g., >>1+/-10% 'tag'<< (a mini DSL?). Based on some sort
of distribution function, e.g., uniform or Gaussian,
I generated an array of samples for each tagged field.
A regular hash was a perfect fit,

   samples[tag] = [ sample1, sample2, .. ]

*until* another requirement came up: to present the tags
in order of appearance.

16

Bil Kleb wrote:

Here's my latest one[1]:

I had a string with a bunch of tagged "tolerance fields",
e.g., >>1+/-10% 'tag'<< (a mini DSL?). Based on some sort
of distribution function, e.g., uniform or Gaussian,
I generated an array of samples for each tagged field.
A regular hash was a perfect fit,

  samples[tag] = [ sample1, sample2, .. ]

*until* another requirement came up: to present the tags
in order of appearance.

Later,
--
Bil
http://fun3d.larc.nasa.gov

[1] Part of a CEV (Crew Exploration Vehicle) task

See, guys? An ordered hash in Ruby would help support
human space exploration! :slight_smile:

/me ponders and RCR and a Dyson sphere design

Hal

17

surf wrote:

Can't you create your own using mixins and including enumerable or
something like that ?

Yes, but I would lose the convenient literal notation.

Hal

18

That's not what he wants though (the point is matching against the Regexp ---
Hash# doesn't buy you anything there).

Maybe

require 'enumerator'
def ASSOC(x); x.enum_for(:each_slice, 2).to_a end

actions = ASSOC [
  /abcd/, lambda{ 1 },
  /xyz/, lambda{ 2 },
  /abc/, lambda{ 3 }
]

# Then he's got to

def run(command, actions)
  actions.each{|re, action| return action[command] if re =~ command}
  nil
end

run("abcdef", actions) # => 1
run("abcf", actions) # => 3

# But this would be nicer
class Array
  def cassoc(x) # "case assoc"
    each{|arr| return arr if arr[0] === x}
    nil
  end
end

re, action = actions.cassoc("abcdef")
action and action.call # => 1
re, action = actions.cassoc("abcx")
action and action.call # => 3

···

On Sun, Aug 13, 2006 at 06:31:07PM +0900, Matt Todd wrote:

Absolutely... an Array is perfect for ordered information.

actions = [
{ /abcd/ => lambda { do_this } },
{ /xyz/ => lambda { do_that } },
{ /abc/ => lambda { other } }
]

Then, all you do is...

actions.select { |action| action[input] }

where input = /xyz/ you will receive the appropriate hash (key and
Proc) in an array. So, to do something with that, you could...

actions.select { |action| action[input] }.first[input].call

which calls the Proc associated with the matching element.

--
Mauricio Fernandez - http://eigenclass.org - singular Ruby

19

>Hal Fulton wrote:
>>Once I wanted a "dynamic case statement" of sorts.
>>I wanted to use procs as values in a hash. Something
>>like:
>> actions = { /abcd/ => lambda { do_this },
>> /xyz/ => lambda { do_that },
>> /abc/ => lambda { other }}

[...]

>To me a Hash feels wrong. Why? Because you don't make any use of
>hash properties for fast lookup. You just iterate in plain order.

He *is* making use of a Hash property. He wants the keys to be
unique. None of the other solutions shown in this thread have
addressed that.

Hal is making the case for *literal* "ordered hashes". The keys will be
unique because he's writing them himself manually. I don't think he wants to
make use of this:

actions = { /a/ => 1, # <--
            /b/ => 2, # \
      /a/ => 4 # <--+-- why do this in the first place.
    }
actions[/a/] # => 4

The way he uses the structure is reminiscent of Array#assoc. The only thing
a Hash has going for it in this case is the cleaner notation and the arrow.
But
    actions = ASSOC [/abcd/, lambda{ ... },
         /abc/, lambda{ ... } ]
(using parentheses if you want) looks good enough for me, and something like
the Array#cassoc I showed before would do fine in this case.

···

On Mon, Aug 14, 2006 at 12:27:07AM +0900, James Edward Gray II wrote:

On Aug 13, 2006, at 3:25 AM, Robert Klemme wrote:

--
Mauricio Fernandez - http://eigenclass.org - singular Ruby

20

Hal Fulton wrote:

Robert Klemme wrote:

So yeah, I ended up using an array of arrays. But it
just felt wrong.

To me a Hash feels wrong. Why? Because you don't make any use of hash properties for fast lookup. You just iterate in plain order.

I never use a hash for fast lookup. I use it because it
allows me easily to associate an arbitrary key with a
value.

Um... So you're saying that you wouldn't bother if lookups were O(n)? Wow!

Kind regards

  robert