No Keys, nor other hash methods on multidimensional hash

[Xeno Campanoli]

Okay, I'm taking the example I got last week for multi-dimensional hashes, and
I don't have access to any Hash methods:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call }
pHash['1']['a'] = "one"
p pHash.keys

I run this and get the result:

...undefined method `keys' for ... (NoMethodError)

Do I need to dereference or something, or is this just something that doesn't
work after all?

Sincerely, Xeno Campanoli, Ruby neophyte and general paraphernalian.

 

[David A. Black]

Hi --

Okay, I'm taking the example I got last week for multi-dimensional hashes, and
I don't have access to any Hash methods:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call }
pHash['1']['a'] = "one"
p pHash.keys

I run this and get the result:

...undefined method `keys' for ... (NoMethodError)

Do I need to dereference or something, or is this just something that doesn't
work after all?

Try this:

hash_lambda = lambda { Hash.new {|h,k| h[k] = hash_lambda.call } }
hash = hash_lambda[]
hash['1']['a'] = "one"
p hash.keys


David

 

[Martin DeMello]

Okay, I'm taking the example I got last week for multi-dimensional hashes, and
I don't have access to any Hash methods:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call }

lambda creates an anonymous function, which in this case returns a hash.
hash_factory might have been a better variable name:

hash_factory = lambda { Hash.new {|h,k| h[k] = hash_factory.call }}

How it works: Hash.new {|h,k| block} creates a new hash, and calls the
block whenever the hash is called with a nonexistent key. h and k, the
two parameters passed to the block, are the hash itself and the key you
tried to look up.

lambda {Hash.new} creates an anonymous function that returns a hash. The
clever part here is that we capture a reference to the function we're
defining, and pass that reference into the block we pass to the hash
(this all works because lambdas are lazily evaluated). So now every time
we call the hash with a missing key, the hash_factory is called again
and generates a new autovivifying hash to store as the value.

Here's how you use it:

hash = hash_factory.call
hash[1][2][3] #=> nil, but the hash will now have the keys

martin

 

[Bill Kelly]

Hi,

Okay, I'm taking the example I got last week for multi-dimensional hashes, and
I don't have access to any Hash methods:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call }
pHash['1']['a'] = "one"
p pHash.keys

I run this and get the result:

...undefined method `keys' for ... (NoMethodError)

Do I need to dereference or something, or is this just something that doesn't
work after all?

pHash isn't the hash-of-hashes itself, it's a Proc object
that knows how to create such a hash.

in irb:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call } }

pHash.class # we can see its class is Proc => Proc
pHash.call # if we call the Proc, it does its job and creates the hash => {}
pHash[] # this is just a synonym for pHash.call

=> {}

I guess one could look at "pHash" as a factory that creates
an auto-vivifying hash.


Regards,

Bill

 

[Phrogz]

To be clear, what Bill is saying is that you need to use pHash.call to
create your hash, and call the Hash methods on that. Like so:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call } }

uberhash = pHash.call

uberhash['L']['a'] = "one"
p uberhash.keys #=> ["L"]
p uberhash['L'].keys #=> ["a"]
p uberhash['L'].values #=> ["one"]

 

[William James]

To be clear, what Bill is saying is that you need to use pHash.call to
create your hash, and call the Hash methods on that. Like so:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call } }

uberhash = pHash.call

uberhash['L']['a'] = "one"
p uberhash.keys #=> ["L"]
p uberhash['L'].keys #=> ["a"]
p uberhash['L'].values #=> ["one"]

How would you test to see if this exists?

h[9][8][7][6][5][4][3][2][1]

 

[David A. Black]

Hi --

To be clear, what Bill is saying is that you need to use pHash.call to
create your hash, and call the Hash methods on that. Like so:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call } }

uberhash = pHash.call

uberhash['L']['a'] = "one"
p uberhash.keys #=> ["L"]
p uberhash['L'].keys #=> ["a"]
p uberhash['L'].values #=> ["one"]

How would you test to see if this exists?

h[9][8][7][6][5][4][3][2][1]

I think it exists as soon as you refer to it. (I thought that's the
whole point But if you didn't want that to happen I guess you
could do:

if h[9][8][7][6][5][4][3][2].has_key?(1) ...


David

 

[William James]

Hi --

To be clear, what Bill is saying is that you need to use pHash.call to
create your hash, and call the Hash methods on that. Like so:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call } }

uberhash = pHash.call

uberhash['L']['a'] = "one"
p uberhash.keys #=> ["L"]
p uberhash['L'].keys #=> ["a"]
p uberhash['L'].values #=> ["one"]

How would you test to see if this exists?

h[9][8][7][6][5][4][3][2][1]

I think it exists as soon as you refer to it. (I thought that's the
whole point But if you didn't want that to happen I guess you
could do:

if h[9][8][7][6][5][4][3][2].has_key?(1) ...

It's not the whole point. One needs to be able to check
to see if an entry exists without changing the hash.

irb(main):002:0> h=pHash.call
=> {}
irb(main):003:0> h['foo']=999
=> 999
irb(main):005:0> if h[9][8][7][6][5][4][3][2].has_key?(1) then puts
'ok';end
=> nil
irb(main):006:0> p h
{"foo"=>999, 9=>{8=>{7=>{6=>{5=>{4=>{3=>{2=>{}}}}}}}}}

Even lowly Awk can easily do this.
-------------------------------------------------
BEGIN {
a[9,8,7,6,5,4,3,2,1] = "yes"
if ( (9,8,7,6,5,4,3,2,1) in a )
print "o.k."
if ( (0,8,7,6,5,4,3,2,1) in a )
print "not o.k."
if ( (0,8,7,6,5,4,3,2) in a )
print "not o.k."
print length(a)
}

 

[David A. Black]

Hi --

Hi --

Phrogz wrote:
To be clear, what Bill is saying is that you need to use pHash.call to
create your hash, and call the Hash methods on that. Like so:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call } }

uberhash = pHash.call

uberhash['L']['a'] = "one"
p uberhash.keys #=> ["L"]
p uberhash['L'].keys #=> ["a"]
p uberhash['L'].values #=> ["one"]

How would you test to see if this exists?

h[9][8][7][6][5][4][3][2][1]

I think it exists as soon as you refer to it. (I thought that's the
whole point But if you didn't want that to happen I guess you
could do:

if h[9][8][7][6][5][4][3][2].has_key?(1) ...

It's not the whole point. One needs to be able to check
to see if an entry exists without changing the hash.

irb(main):002:0> h=pHash.call
=> {}
irb(main):003:0> h['foo']=999
=> 999
irb(main):005:0> if h[9][8][7][6][5][4][3][2].has_key?(1) then puts
'ok';end

I can't tell if you're saying the has_key? thing was the right
solution or that it wasn't The creation of the intermediate
hashes is desired, right?


David

 

[William James]

Hi --

Hi --

On Tue, 23 Aug 2005, William James wrote:

Phrogz wrote:
To be clear, what Bill is saying is that you need to use pHash.call to
create your hash, and call the Hash methods on that. Like so:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call } }

uberhash = pHash.call

uberhash['L']['a'] = "one"
p uberhash.keys #=> ["L"]
p uberhash['L'].keys #=> ["a"]
p uberhash['L'].values #=> ["one"]

How would you test to see if this exists?

h[9][8][7][6][5][4][3][2][1]

I think it exists as soon as you refer to it. (I thought that's the
whole point But if you didn't want that to happen I guess you
could do:

if h[9][8][7][6][5][4][3][2].has_key?(1) ...

It's not the whole point. One needs to be able to check
to see if an entry exists without changing the hash.

irb(main):002:0> h=pHash.call
=> {}
irb(main):003:0> h['foo']=999
=> 999
irb(main):005:0> if h[9][8][7][6][5][4][3][2].has_key?(1) then puts
'ok';end

I can't tell if you're saying the has_key? thing was the right
solution or that it wasn't The creation of the intermediate
hashes is desired, right?

Quote:
One needs to be able to check to see if an entry exists without
changing the hash.

Creating intermediate hashes changes the hash.

Therefore, it wasn't the right solution.

The Awk example shows that Awk can perform this check without
altering the hash in any way whatsoever, just as h.key?('foo')
doesn't alter the hash. Having to alter the hash whenever you
check for the existence of a key would be extremely crude and
ineffecient.

 

[Florian Groß]

Okay, I'm taking the example I got last week for multi-dimensional hashes, and
I don't have access to any Hash methods:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call }
pHash['1']['a'] = "one"
p pHash.keys

I run this and get the result:

...undefined method `keys' for ... (NoMethodError)

Try this one instead:

hash_proc = lambda { |hash, key| hash[key] = Hash.new(&hash_proc) }
hash = Hash.new(&hash_proc)

irb(main):003:0> hash[5][4][3][2][1] = 0
=> 0
irb(main):004:0> hash.keys
=> [5]
irb(main):005:0> hash
=> {5=>{4=>{3=>{2=>{1=>0}}}}}

Or if you're a fan of the y combinator:

class Proc
def self.y(&block)
result = lambda { |*args| block.call(result, *args) }
end
end

Hash.new(&Proc.y { |p, h, k| h[k] = Hash.new(&p) })

 

[James Edward Gray II]

It's not the whole point. One needs to be able to check
to see if an entry exists without changing the hash.

irb(main):002:0> h=pHash.call
=> {}
irb(main):003:0> h['foo']=999
=> 999
irb(main):005:0> if h[9][8][7][6][5][4][3][2].has_key?(1) then puts
'ok';end
=> nil
irb(main):006:0> p h
{"foo"=>999, 9=>{8=>{7=>{6=>{5=>{4=>{3=>{2=>{}}}}}}}}}

I'm not sure what you're trying to show here???

You called has_key?() on the last Hash. It did not add that key to
the Hash, just as you said it shouldn't. The other Hashes were
autovivified along the way, because you wrote code to make it so. I
would be disappointed if any of the above had behaved differently and
I know at least Perl has identical behavior.

That said, if you want an object that can check many levels deep
without creating the upper levels, you can surely code one up with
little effort.

James Edward Gray II

 

[David A. Black]

Hi --

David A. Black wrote:
Hi --

On Tue, 23 Aug 2005, William James wrote:

Phrogz wrote:
To be clear, what Bill is saying is that you need to use pHash.call to
create your hash, and call the Hash methods on that. Like so:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call } }

uberhash = pHash.call

uberhash['L']['a'] = "one"
p uberhash.keys #=> ["L"]
p uberhash['L'].keys #=> ["a"]
p uberhash['L'].values #=> ["one"]

How would you test to see if this exists?

h[9][8][7][6][5][4][3][2][1]

I think it exists as soon as you refer to it. (I thought that's the
whole point But if you didn't want that to happen I guess you
could do:

if h[9][8][7][6][5][4][3][2].has_key?(1) ...

It's not the whole point. One needs to be able to check
to see if an entry exists without changing the hash.

irb(main):002:0> h=pHash.call
=> {}
irb(main):003:0> h['foo']=999
=> 999
irb(main):005:0> if h[9][8][7][6][5][4][3][2].has_key?(1) then puts
'ok';end

I can't tell if you're saying the has_key? thing was the right
solution or that it wasn't The creation of the intermediate
hashes is desired, right?

Quote:
One needs to be able to check to see if an entry exists without
changing the hash.

Creating intermediate hashes changes the hash.

Therefore, it wasn't the right solution.

It wasn't clear to me which hash you meant. I interpreted it as
......[2], and checking its keys was a way of checking the existence
of the entry without changing the hash (i.e., *that* hash).

I do think the original impetus for this whole thing was the creation
of a hash that automatically filled in with hashes in the face of
h[1][2][3].... It's probably significantly harder to make a hash that
does that sometimes, but not always, as it were. I haven't tried it
yet though.


David

 

[William James]

To be clear, what Bill is saying is that you need to use pHash.call to
create your hash, and call the Hash methods on that. Like so:

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call } }

uberhash = pHash.call

uberhash['L']['a'] = "one"
p uberhash.keys #=> ["L"]
p uberhash['L'].keys #=> ["a"]
p uberhash['L'].values #=> ["one"]

How would you test to see if this exists?

h[9][8][7][6][5][4][3][2][1]

Here's one way, but it doesn't seem efficient:
------------------------------------------------------------------
class Hash
def has( *subs )
h=self
subs.each{|x|
return false unless h.key?(x)
h=h[x]
}
true
end
end

pHash = lambda { Hash.new {|h,k| h[k] = pHash.call } }

uberhash = pHash.call

uberhash['a']['b']['c']='The crux.'
p uberhash.has('a','b','c')
p uberhash.has('a','b','x')
p uberhash
------------------------------------------------------------------

Output:

true
false
{"a"=>{"b"=>{"c"=>"The crux."}}}

Note that the hash wasn't changed by the check for the
nonexistent key.

By the way, here's how Awk effortlessly handles multidimensional
associative arrays (hashes):
a['foo','bar']
is equivalent to
a['foo' SUBSEP 'bar']
The keys are merely joined using a character that won't be found
in the keys.

 

[David A. Black]

Hi --

By the way, here's how Awk effortlessly handles multidimensional
associative arrays (hashes):
a['foo','bar']
is equivalent to
a['foo' SUBSEP 'bar']
The keys are merely joined using a character that won't be found
in the keys.

Am I right that the keys can only be scalar values?


David

 

[William James]

Hi --

By the way, here's how Awk effortlessly handles multidimensional
associative arrays (hashes):
a['foo','bar']
is equivalent to
a['foo' SUBSEP 'bar']
The keys are merely joined using a character that won't be found
in the keys.

Am I right that the keys can only be scalar values?

Yes. The method is crude, but effective.

Getting back to checking for existence of a key in an
autovivifying hash; what if I check for a million keys
that don't exist:

1_000_000.times { |i|
if h[8][7][6][5][4][3][2].has_key?(1) ...
}

This causes the hash to grow to enormous size. Will the
garbage-collector
eventually remove the spurious entries?

 

[Martin DeMello]

Getting back to checking for existence of a key in an
autovivifying hash; what if I check for a million keys
that don't exist:

1_000_000.times { |i|
if h[8][7][6][5][4][3][2].has_key?(1) ...
}

This causes the hash to grow to enormous size. Will the
garbage-collector eventually remove the spurious entries?

How can it? There's nothing to distinguish 'spurious' entries from
'real' ones - that's the whole point of autovivification.

That would make a cute quiz/golf problem, though - given such an
autovivified hash, write a .cleanup! method that recursively deletes any
keys that point to nil.

martin