Shortest class to implement Perl hash-of-hashes

6

At some point, I bumped into an SO question asking how to implement Perl's trivial hash-of-hashes data structure in Java.

For those who don't know Perl, the hash value can be a scalar or another hash, or technically speaking hash reference. Arbitrary depth. Additional feature offered by Perl is autovivification - assigning an element 4 layers deep will automatically create correct hashes with proper keys 4 levels deep, without Java's need to assign hash object on level 1, then hash object on level 2 (being added to the first hash as a value) etc...

So, Perl code to assign a value to N-level hash at a known depth is

my $myHash; # initialization isn't required due to autovivification
$myHash->{$key1}->{$key2}->{$key3}->{$key4} = $value;

And to retrieve it

my $value = $myHash->{$key1}->{$key2}->{$key3}->{$key4};

The more generic code to assign a hash by arbitrary set of keys can be implemented by 5-10 line subroutine done properly; or 2-3 lines golf hack with eval.

Not being anywhere near a Java expert, my SO answer was ~30 lines of code that implemented a fixed-depth 3 level hash of hash of hashes.

Your mission, should you choose to accept it, is to produce the smallest code in a strongly typed language which implements Perl equivalent data structure which is a hashmap of hashmaps of ...; of arbitrary and non-uniform depth (basically, a tree); with hasmap keys being of String type; and leaf-level values String or Integer. The code should support 100% of what the Perl hash-of-hashes code does, including:

  • Retrieving a value based on a list of keys

  • Assigning a value based on a list of keys

    • As part of this, you should be able to replace a scalar leaf level node with an internal hashmap node, if your list of keys leads to that.

      E.g. set("val1","k1","k2");set("val2","k1","k2","k3") basically erases "val1" from existence after second call as it's replaced by a 3rd level hashmap.

The code should be resilient, e.g. no null exceptions etc... even for the bad input (simply return NULL)

You can use any strongly typed language other than Java, though I would personally prefer Java answers due to how/why this question originated.

Caveat: using some 3rd party library that implements equivalent of Perl hashes is NOT acceptable. 100% of the code must be using only the native core capabilities of the language.

DVK

Posted 2016-03-25T02:50:59.547

Reputation: 251

1Come to think of it, this would also be possible in Python and other weakly or dynamically typed languages that have a concept of classes. Would those be allowed as well? – Alex A. – 2016-03-25T03:32:36.973

@AlexA. - no, sorry. As I noted in my comment (now deleted), doing it in a language without strong typing (especially Perl-influenced ones like Python or Ruby) is too easy and basically defeats the purpose of the challenge. – DVK – 2016-03-25T03:45:58.603

Ah right, sorry. – Alex A. – 2016-03-25T03:54:01.917

Out of interest (since I wouldn't have used a strongly typed language) what's the result of get("k1", "k2") after the two set operations in the question? – Neil – 2016-03-25T09:15:50.237

You should add some test cases for people to ensure that their code works. – LegionMammal978 – 2016-03-25T10:55:57.167

"strongly typed" is not a term with a unanimous definition; I consider some dynamic languages to be strongly typed, for example. I suppose you want to say statically typed, but maybe you should give an explicit list of allowed languages. – coredump – 2016-03-25T13:58:35.547

@Neil - an instance of the class, containing the subtree under "k2" node. – DVK – 2016-03-25T15:26:33.247

@coredump - statically typed is probably a better choice. – DVK – 2016-03-25T15:27:27.300

Answers

2

Scala, 231 214 199 193 bytes

Immutability always wins! (turns out the long package name of collection.mutable.Map wasn't worth the hassle...)

class A{var a=Map[String,Any]()
def g(s:String*):Any={val y=s(0);if(s.size>1)g(y).asInstanceOf[A].g(s.drop(1):_*)else if(a.contains(y))a(y)else{a+=y->new A;a(y)}}
def s(s:String,v:Any)=a+=s->v}

Only thing that's problematic is the need to cast back to A... but having another method entirely that'd return a.type is actually longer (and with cannot be used).

Example:

val a = new A()
a.g("hey").asInstanceOf[A].s("foo", "bar")
a.g("hey").asInstanceOf[A].s("int", 3)
println(a.g("hey").asInstanceOf[A].g("foo"))
println(a.g("hey", "foo"))
println(a.g("hey", "int"))
a.s("hey", 42)
println(a.g("hey"))

Output:

bar
bar
3
42

Ven

Posted 2016-03-25T02:50:59.547

Reputation: 3 382

1

C#, 215 bytes

class A:System.Collections.Generic.Dictionary<string,object>{public void B(string a,object b){if(ContainsKey(a))this[a]=b;else Add(a,b);}public dynamic C(string a){if(!ContainsKey(a))Add(a,new A());return this[a];}}

The class is named A. Use hash.B("key", "val"); to set a value, and hash.C("key"); to get a value. Nested keys can be achieved through, e.g., hash.C("k1").C("k2").C("k3").B("k4", "value");.

LegionMammal978

Posted 2016-03-25T02:50:59.547

Reputation: 15 731

What is "dynamic" used for? I don't know C# enough to understand why it is required. – coredump – 2016-03-25T13:59:25.080

1@coredump It's (from a quick look) used here as a 'generic type' that isn't known until its resolved in the runtime. We don't know what the function return type is, so let's return an unknown type :D – Yytsi – 2016-03-25T20:50:47.690

@TuukkaX I just used it so that it could be easily chained without having to cast objects back to As. – LegionMammal978 – 2016-03-25T21:03:43.173

@LegionMammal978 Oh. I see. Thanks for clarifying! – Yytsi – 2016-03-25T21:12:52.687