No Keys, nor other hash methods on multidimensional hash

Discussion in 'Ruby' started by Xeno Campanoli, Aug 22, 2005.

  1. 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.
     
    Xeno Campanoli, Aug 22, 2005
    #1
    1. Advertising

  2. Hi --

    On Tue, 23 Aug 2005, Xeno Campanoli wrote:

    > 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

    --
    David A. Black
     
    David A. Black, Aug 22, 2005
    #2
    1. Advertising

  3. Xeno Campanoli <> wrote:
    > 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
     
    Martin DeMello, Aug 22, 2005
    #3
  4. Xeno Campanoli

    Bill Kelly Guest

    Hi,

    From: "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?


    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 } }

    => #<Proc:0x02dc4960@(irb):1>
    >> 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
     
    Bill Kelly, Aug 22, 2005
    #4
  5. Xeno Campanoli

    Phrogz Guest

    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"]
     
    Phrogz, Aug 22, 2005
    #5
  6. 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]
     
    William James, Aug 22, 2005
    #6
  7. 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) ...


    David

    --
    David A. Black
     
    David A. Black, Aug 22, 2005
    #7
  8. 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
    => 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)
    }
    -------------------------------------------------
    Output:

    o.k.
    1
     
    William James, Aug 22, 2005
    #8
  9. Hi --

    On Tue, 23 Aug 2005, William James wrote:

    > 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?


    David

    --
    David A. Black
     
    David A. Black, Aug 22, 2005
    #9
  10. David A. Black wrote:
    > Hi --
    >
    > On Tue, 23 Aug 2005, William James wrote:
    >
    > > 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.

    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.
     
    William James, Aug 23, 2005
    #10
  11. Xeno Campanoli wrote:

    > 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) })
     
    Florian Groß, Aug 23, 2005
    #11
  12. On Aug 22, 2005, at 5:26 PM, William James wrote:

    > 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
     
    James Edward Gray II, Aug 23, 2005
    #12
  13. On Tue, 23 Aug 2005, William James wrote:

    > David A. Black wrote:
    >> Hi --
    >>
    >> On Tue, 23 Aug 2005, William James wrote:
    >>
    >>> 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

    --
    David A. Black
     
    David A. Black, Aug 23, 2005
    #13
  14. 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]


    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.
     
    William James, Aug 23, 2005
    #14
  15. Hi --

    On Tue, 23 Aug 2005, William James wrote:

    > 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

    --
    David A. Black
     
    David A. Black, Aug 23, 2005
    #15
  16. David A. Black wrote:
    > Hi --
    >
    > On Tue, 23 Aug 2005, William James wrote:
    >
    > > 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?
     
    William James, Aug 24, 2005
    #16
  17. William James <> wrote:
    >
    > 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
     
    Martin DeMello, Aug 25, 2005
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Rehceb Rotkiv
    Replies:
    16
    Views:
    901
    Alex Martelli
    Apr 2, 2007
  2. rp
    Replies:
    1
    Views:
    555
    red floyd
    Nov 10, 2011
  3. Alex Fenton

    Hash#values and Hash#keys order

    Alex Fenton, Apr 7, 2006, in forum: Ruby
    Replies:
    1
    Views:
    151
    George Ogata
    Apr 15, 2006
  4. Michael ..
    Replies:
    12
    Views:
    218
    Julian Leviston
    Feb 16, 2009
  5. dt
    Replies:
    4
    Views:
    160
    Mirco Wahab
    Feb 18, 2007
Loading...

Share This Page