Tricky: converting path into a Hash

Hello!

I am wondering if the mighty ruby crowd has a brilliant idea for a tricky
problem I am solving.

I need to store a path as a tree in a hash.

Given:
a/b/c

I want the Hash:
{ 'a' => { 'b' => { 'c' => { } } } }
or written differently
hsh['a']['b']['c'] = {}

Is there an elegant solution to this, without maybe looping or eval'ing too
much?

Muchas Gracias Senoritas,
Robert Mannl

harp:~ > cat a.rb
require 'pathname'

class Pathname
   def to_hash
     ret = h = {}
     each_filename{|part| h[part] = (h={})}
     ret
   end
end

pn = Pathname.new 'a/b/c'

p pn.to_hash

harp:~ > ruby a.rb
{"a"=>{"b"=>{"c"=>{}}}}

-a

···

On Mon, 22 Jan 2007, Robert MannI wrote:

Hello!

I am wondering if the mighty ruby crowd has a brilliant idea for a tricky
problem I am solving.

I need to store a path as a tree in a hash.

Given:
a/b/c

I want the Hash:
{ 'a' => { 'b' => { 'c' => { } } } }
or written differently
hsh['a']['b']['c'] = {}

Is there an elegant solution to this, without maybe looping or eval'ing too
much?

--
we can deny everything, except that we have the possibility of being better.
simply reflect on that.
- the dalai lama

Robert MannI wrote:

Hello!

I am wondering if the mighty ruby crowd has a brilliant idea for a tricky
problem I am solving.

I need to store a path as a tree in a hash.

Given:
a/b/c

I want the Hash:
{ 'a' => { 'b' => { 'c' => { } } } }
or written differently
hsh['a']['b']['c'] = {}

This is a fairly standard idiom:

pr = proc {|h,k| h[k] = Hash.new(&pr)}

h = Hash.new(&pr)

h['a']['b']['c'] = {}

p h # ==> {"a"=>{"b"=>{"c"=>{}}}}

For more discussion, search for "autovivify hash" on the list...

···

--
        vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407

Hello!

I am wondering if the mighty ruby crowd has a brilliant idea for a tricky
problem I am solving.

I need to store a path as a tree in a hash.

Given:
a/b/c

I want the Hash:
{ 'a' => { 'b' => { 'c' => { } } } }
or written differently
hsh['a']['b']['c'] = {}

Is there an elegant solution to this, without maybe looping or eval'ing too
much?

path = "a/b/c"

def hashify_path( s )
  if s =~ %r{\A[^/]*\z}
    { s => {} }
  elsif s =~ %r{\A([^/]*)/(.*)\z}
    { $1 => hashify_path( $2 ) }
  else
    raise ArgumentError, "Invalid path"
  end
end

p hashify_path( path )
    
prints:
{"a"=>{"b"=>{"c"=>{}}}}

···

On Mon, Jan 22, 2007 at 10:15:09AM +0900, Robert MannI wrote:

Muchas Gracias Senoritas,
Robert Mannl

Robert MannI wrote:

Hello!

I am wondering if the mighty ruby crowd has a brilliant idea for a tricky
problem I am solving.

I need to store a path as a tree in a hash.

Given:
a/b/c

I want the Hash:
{ 'a' => { 'b' => { 'c' => { } } } }
or written differently
hsh['a']['b']['c'] = {}

Is there an elegant solution to this, without maybe looping or eval'ing too
much?

Muchas Gracias Senoritas,
Robert Mannl

There's a "natural" (tail) recursive solution to this if you've learned Lisp or Scheme, and an easy translation to a "while" loop should recursion be inefficient on your platform. I don't know of any "natural" way to do it without recursion or iteration/looping, nor do I see any need to introduce "eval" at all.

I would say the most "elegant" solution would be the obvious iterative "while" loop translated into Ruby's iterators, since Ruby does not to my knowledge support efficient tail recursion. But I'm not going to code it for you. :slight_smile:

···

--
M. Edward (Ed) Borasky, FBG, AB, PTA, PGS, MS, MNLP, NST, ACMC(P)
http://borasky-research.blogspot.com/

If God had meant for carrots to be eaten cooked, He would have given rabbits fire.

I suspect you are asking the wrong question.

My experience is that if you tell the Mighty Ruby Crowd why you wanted
to do that, they tend to come up with a surprisingly more elegant
thing to be doing, complete with a really quite simple way of doing it.

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

···

On Mon, 22 Jan 2007, Robert MannI wrote:

I am wondering if the mighty ruby crowd has a brilliant idea for a tricky
problem I am solving.
hsh['a']['b']['c'] = {}

Is there an elegant solution to this, without maybe looping or eval'ing too
much?

barf:~ > dog a.rb
s = "a/b/c"
p s.split("/").reverse.inject({}){|h,s| {s,h} }

barf:~ > ruby a.rb
{"a"=>{"b"=>{"c"=>{}}}}

···

On Mon, 22 Jan 2007, Robert MannI wrote:

> Hello!
>
>
> I am wondering if the mighty ruby crowd has a brilliant idea for a tricky
> problem I am solving.
>
> I need to store a path as a tree in a hash.
>
> Given:
> a/b/c
>
> I want the Hash:
> { 'a' => { 'b' => { 'c' => { } } } }
> or written differently
> hsh['a']['b']['c'] = {}
>
> Is there an elegant solution to this, without maybe looping or eval'ing too
> much?
>

harp:~ > cat a.rb
require 'pathname'

class Pathname
   def to_hash
     ret = h = {}
     each_filename{|part| h[part] = (h={})}
     ret
   end
end

pn = Pathname.new 'a/b/c'

p pn.to_hash

harp:~ > ruby a.rb
{"a"=>{"b"=>{"c"=>{}}}}

Robert MannI wrote:
>Hello!
>
>
>I am wondering if the mighty ruby crowd has a brilliant idea for a tricky
>problem I am solving.
>
>I need to store a path as a tree in a hash.
>
>Given:
>a/b/c
>
>I want the Hash:
>{ 'a' => { 'b' => { 'c' => { } } } }
>or written differently
>hsh['a']['b']['c'] = {}
>
>Is there an elegant solution to this, without maybe looping or
>eval'ing too
>much?
>
>
>
>Muchas Gracias Senoritas,
>Robert Mannl
>
There's a "natural" (tail) recursive solution to this if you've learned
Lisp or Scheme, and an easy translation to a "while" loop should
recursion be inefficient on your platform. I don't know of any "natural"
way to do it without recursion or iteration/looping, nor do I see any
need to introduce "eval" at all.

I would say the most "elegant" solution would be the obvious iterative
"while" loop translated into Ruby's iterators, since Ruby does not to my
knowledge support efficient tail recursion. But I'm not going to code it
for you. :slight_smile:

I was trying to think of fold-ish solution to it, you've stimulated my
brain enough to do it:

# I wish we had a foldr to go with our foldl
p "a/b/c".split("/").reverse.inject({}) { |h, v| {v => h} }
{"a"=>{"b"=>{"c"=>{}}}}

···

On Mon, Jan 22, 2007 at 10:59:44AM +0900, M. Edward (Ed) Borasky wrote:

--
M. Edward (Ed) Borasky, FBG, AB, PTA, PGS, MS, MNLP, NST, ACMC(P)
http://borasky-research.blogspot.com/

If God had meant for carrots to be eaten cooked, He would have given
rabbits fire.

Then the inject trick becomes

pr = lambda {|h,k| h[k] = Hash.new(&pr)}
z=Hash.new(&pr)
s = "a/b/c"
s.split("/").inject(z){|ha,co| ha[co]}
s = "a/b/d"
s.split("/").inject(z){|ha,co| ha[co]}
s = "a/d/e"
s.split("/").inject(z){|ha,co| ha[co]}
s = "c/a/t"
s.split("/").inject(z){|ha,co| ha[co]}
p z

For some reason you can't name the hash h, otherwise the parameter
assignment in the proc will override it. Why is that, and is there any way
to avoid it?

This is what you really wanted because you wanted a really easy way to
merge all of these paths together into one hash, whereas if you
constructed the hashes separately then merged them you'd be losing data.
Try the following to see what I mean.

h1={'a'=>{'b'=>{'c'=>{}}}}
h2={'a'=>{'b'=>{'d'=>{}}}}
h3={'a'=>{'c'=>{'e'=>{}}}}
h4={'c'=>{'a'=>{'t'=>{}}}}
p h1.merge(h2).merge(h3).merge(h4)

All of the a/b branches are overwritten when 'a'=>{'c'...} is merged over
it. (And the second 'a'=>{'b'...} hash overwrites the first completely).

--Ken Bloom

···

On Mon, 22 Jan 2007 10:46:00 +0900, Joel VanderWerf wrote:

Robert MannI wrote:

Hello!

I am wondering if the mighty ruby crowd has a brilliant idea for a tricky
problem I am solving.

I need to store a path as a tree in a hash.

Given:
a/b/c

I want the Hash:
{ 'a' => { 'b' => { 'c' => { } } } }
or written differently
hsh['a']['b']['c'] = {}

This is a fairly standard idiom:

pr = proc {|h,k| h[k] = Hash.new(&pr)}

h = Hash.new(&pr)

h['a']['b']['c'] = {}

p h # ==> {"a"=>{"b"=>{"c"=>{}}}}

For more discussion, search for "autovivify hash" on the list...

--
Ken Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/

I guess my question is....why?

Dan

···

ara.t.howard@noaa.gov wrote:

On Mon, 22 Jan 2007, Robert MannI wrote:

> Hello!
>
>
> I am wondering if the mighty ruby crowd has a brilliant idea for a tricky
> problem I am solving.
>
> I need to store a path as a tree in a hash.
>
> Given:
> a/b/c
>
> I want the Hash:
> { 'a' => { 'b' => { 'c' => { } } } }
> or written differently
> hsh['a']['b']['c'] = {}
>
> Is there an elegant solution to this, without maybe looping or eval'ing too
> much?
>

harp:~ > cat a.rb
require 'pathname'

class Pathname
   def to_hash
     ret = h = {}
     each_filename{|part| h[part] = (h={})}
     ret
   end
end

pn = Pathname.new 'a/b/c'

p pn.to_hash

harp:~ > ruby a.rb
{"a"=>{"b"=>{"c"=>{}}}}

Same reason as:

h = 3
lambda { h = "three" }.call
p h # prints "three"

Block arguments act like assignment. This can be seen in pathological
examples like lambda { |$a_global| ... } and lambda { |@an_ivar| ... }

···

On Mon, Jan 22, 2007 at 01:10:08PM +0900, Ken Bloom wrote:

Then the inject trick becomes

pr = lambda {|h,k| h[k] = Hash.new(&pr)}
z=Hash.new(&pr)
s = "a/b/c"
s.split("/").inject(z){|ha,co| ha[co]}
s = "a/b/d"
s.split("/").inject(z){|ha,co| ha[co]}
s = "a/d/e"
s.split("/").inject(z){|ha,co| ha[co]}
s = "c/a/t"
s.split("/").inject(z){|ha,co| ha[co]}
p z

For some reason you can't name the hash h, otherwise the parameter
assignment in the proc will override it. Why is that, and is there any way
to avoid it?

For more discussion, search for "autovivify hash" on the list...

Then the inject trick becomes

pr = lambda {|h,k| h[k] = Hash.new(&pr)}
z=Hash.new(&pr)
s = "a/b/c"
s.split("/").inject(z){|ha,co| ha[co]}
s = "a/b/d"
s.split("/").inject(z){|ha,co| ha[co]}
s = "a/d/e"
s.split("/").inject(z){|ha,co| ha[co]}
s = "c/a/t"
s.split("/").inject(z){|ha,co| ha[co]}
p z

For some reason you can't name the hash h, otherwise the parameter
assignment in the proc will override it. Why is that, and is there any way
to avoid it?

i think it's less overhead to simply name the top hash and return it

harp:~ > cat a.rb
p( 'a/b/c'.split('/').inject(r={}){|h,k| h[k] = h={}} && r )

harp:~ > ruby a.rb
{"a"=>{"b"=>{"c"=>{}}}}

This is what you really wanted because you wanted a really easy way to merge
all of these paths together into one hash, whereas if you constructed the
hashes separately then merged them you'd be losing data. Try the following
to see what I mean.

h1={'a'=>{'b'=>{'c'=>{}}}}
h2={'a'=>{'b'=>{'d'=>{}}}}
h3={'a'=>{'c'=>{'e'=>{}}}}
h4={'c'=>{'a'=>{'t'=>{}}}}
p h1.merge(h2).merge(h3).merge(h4)

All of the a/b branches are overwritten when 'a'=>{'c'...} is merged over
it. (And the second 'a'=>{'b'...} hash overwrites the first completely).

you are almost certainly right. good point!

-a

···

On Mon, 22 Jan 2007, Ken Bloom wrote:
--
we can deny everything, except that we have the possibility of being better.
simply reflect on that.
- the dalai lama

Gracias everyone!

I actually thought about the inject trick in bed at dawn but Ken Bloom's
solution is better for me, because it doesn't override any data once I add
paths to the tree.

Grateful for all the smart answers.

- Rob the rabbit

···

On 1/22/07, Logan Capaldo <logancapaldo@gmail.com> wrote:

On Mon, Jan 22, 2007 at 01:10:08PM +0900, Ken Bloom wrote:
>
> Then the inject trick becomes
>
> pr = lambda {|h,k| h[k] = Hash.new(&pr)}
> z=Hash.new(&pr)
> s = "a/b/c"
> s.split("/").inject(z){|ha,co| ha[co]}
> s = "a/b/d"
> s.split("/").inject(z){|ha,co| ha[co]}
> s = "a/d/e"
> s.split("/").inject(z){|ha,co| ha[co]}
> s = "c/a/t"
> s.split("/").inject(z){|ha,co| ha[co]}
> p z
>
> For some reason you can't name the hash h, otherwise the parameter
> assignment in the proc will override it. Why is that, and is there any
way
> to avoid it?
Same reason as:

h = 3
lambda { h = "three" }.call
p h # prints "three"

Block arguments act like assignment. This can be seen in pathological
examples like lambda { |$a_global| ... } and lambda { |@an_ivar| ... }