Part of the beauty of this article was that I wasn’t sure that it was satire until ⅔ of the way through it! A satire tag would have been a spoiler. (And I guess now these comments are spoilering the article.)

supremely entertaining troll, it reminded me of jenn schiffer’s stuff :) here’s one clear tell:

Second, hashes are fast. Hashes are always O(1) reads, inserts and writes. Why try to understand logarithms when “1” is not only much easier but also faster. (Note: there’s something about amortized complexity, but that’s a rare anomaly over billions of hits).

God, you’re making me have nervous ticks. hashes of arrays of hashes of hashes etc… the number of %{}/@{}’s are too damn high. If there is one thing perl doesn’t make easy, its bolting together basic data structures.

Sigils were not a great idea. Also this article is a great troll.

Did someone say hashes of arrays of hashes of hashes?? Heck, throw another array in there too!

$foo{bar}[42]{baz}{quux} = [4, 3, 2, 1];
print "$_\n" for @{ $foo{bar}[42]{baz}{quux} };
use experimental 'postderef';
print "$_\n" for $foo{bar}[42]{baz}{quux}->@*;

Admittedly sometimes that deep autovivification is exactly what you don’t want, but it can be turned off. I stumble more over map {block} list requiring me to read from the end to the start when chained, after using stuff like Ruby and Elixir regularly where you can generally read those sorts of transformations from beginning to end.

Of the issues with this post, the one that bugs me most is that their proof is wrong. Here is a contradiction:

Suppose we have a data structure which cannot be implemented in main memory (I don’t know off any that have been proven to non-representable in memory, but given the polynomial hierarchy if P =/= NP one is likely to exist). Then this data structure can’t be represented with Hash Int String as the post postulates. Given infinite main memory, any hash can be represented as Hash Int String via pointers. Since the structure cannot be represented in memory, it cannot be represented with a hash. QED

They are correct in saying that anything that can be represented in memory can be represented with a hash. However, this isn’t universal.

I don’t believe I quite agree with your contradiction…it somewhat hinges on the existence of one of these–let’s call them eldritch structures–unstorable data structures.

Under what circumstances would such a structure exist? What data would it model?

A simple example of a dataset that might take up all known memory would be, say, the set of all primes, right? But even then we can specify a predicate function which can fit into finite memory and be used to test for membership.

A trivial datastructure that requires infinite symbols is the Constant-Time Prime Label structure (that I totally didn’t make up just now). It maps every integer to a boolean true or false (true if prime, false otherwise). It is constant time because you can provide an integer and get an immediate answer. In order for this to be constant, each integer must be a tape symbol (if it weren’t, it’d be linear in bit length, not constant). But Turing machines aren’t defined with infinite tape symbols, so this structure can’t be represented on a turing machine (and thus not in main memory).

That’s a pretty useful in theory but also a trivial and useless example. Yes, we can define a predicate computing the mapping, but we lose the data structure’s most useful property (being constant time) when we do. So the data structure and predicate aren’t equivalent data structures in my mind (in the same sense that complexity theorists define algorithmic equivalence in terms of the complexity of a transformation from one algorithm to another; eg an algorithm is said to be polynomially equivalent, not merely equivalent).

Alternately, consider a (infinite or finite) stochastic sequence/array on the language L. Let A and B be disjoint subsets of L. When an element e is read from the sequence, either an a in A is seen or a b in B is seen. Subsequent reads may not see the same thing. This structure could be used to efficiently perform random computations (which are important for many crypto applications), but is only defined on a probabalistic multi-tape turing machine (which would make it in theory equivalent to a non-deterministic turing machine, giving exponential blowup in the naïve transformation of the algorithm; if P = BPP then this one would be polynomially equivalent). This structure can be simulated reasonably well by stuff like /dev/rand (which includes main memory as a component, but requires other pieces to generate entropy for it to be actually random) that give what amounts to a buffer of random bytes.

So there are (theoretically) useful structures that can’t reasonably be represented in just main memory. Practically, we could represent any finite structure as a hash, but that pretty much boils down to representing everything as a string and if javascript has taught me anything, it’s that that is a terrible idea.

If symbols could be used as ordinary hash keys I’d be on board with them, because at that point they’re basically internalized strings for which we can do equality by reference equality (so…just faster strings).

My comment about JS was mostly poking fun at some idioms/conventions in the language that are ‘stringly typed’ and really difficult to scale to a large code base. For example: if(x.type === "foo" && y === "bar")

Are you stretching the definition of data structure a bit too far? Basically you’ve said that any arbitrary set could be a unique data structure. This is the “prime number structure”, this is the “odd numbers structure”, etc.

This reminds me of Lua’s table data structure, which is effectively the language’s only composite data structure. (Errrm, OK, so maybe closures count too.)

There was a time, and this may still be the case, that arrays in Lua were implemented via this same table structure, using what essentially amounts to the strategy in the linked post (or at least the interface is like that). Since Closures are really just a tuple of captured data (or pointers thereto), and Lua bytecode is just an array of integers, Closures are representable exclusively via tables. It’d be interesting if Lua did this, but they don’t. :)

Sarcasm is a cheap rhetorical trick to avoid having to defend your position properly. I love strong typing but the case for it needs to be made on its merits. (And much as I hate it, Javascript has been quite successful).

it made me think of http://learnyouahaskell.com/starting-out (search for “If we think of a list as a monster, here’s what’s what.”) but I don’t know what it’s actually referencing

Can we get a satire tag?

Part of the beauty of this article was that I wasn’t sure that it was satire until ⅔ of the way through it! A satire tag would have been a spoiler. (And I guess now these comments are spoilering the article.)

I genuinely can’t tell if this is a supremely artful troll or not.

Like, with a bit of thinking…yeah, it kinda works, I guess? And yet…gyah…

supremely entertaining troll, it reminded me of jenn schiffer’s stuff :) here’s one clear tell:

Either troll or a Perl programmer :-D

Sometimes hard to tell the difference…. :-D

Sigh! I remember my days of doing Perl….. Code flowed from my hands… I built hashes of arrays of hashes of….

….and then I needed to debug.

Or modify.

Sigh.

Write Only Code lies this way.

God, you’re making me have nervous ticks. hashes of arrays of hashes of hashes etc… the number of %{}/@{}’s are too damn high. If there is one thing perl doesn’t make easy, its bolting together basic data structures.

Sigils were not a great idea. Also this article is a great troll.

Oh it makes it

veryveryeasy to bolt them together. The problem it ends up looking like, and behaving like, a KatamariDid someone say hashes of arrays of hashes of hashes?? Heck, throw another array in there too!

Admittedly sometimes that deep autovivification is exactly what you

don’twant, but it can be turned off. I stumble more over`map {block} list`

requiring me to read from the end to the start when chained, after using stuff like Ruby and Elixir regularly where you can generally read those sorts of transformations from beginning to end.Look at the very top of the page, right below the title:

Seems like a troll.

Of the issues with this post, the one that bugs me most is that their proof is wrong. Here is a contradiction:

Suppose we have a data structure which cannot be implemented in main memory (I don’t know off any that have been proven to non-representable in memory, but given the polynomial hierarchy if P =/= NP one is likely to exist). Then this data structure can’t be represented with

`Hash Int String`

as the post postulates. Given infinite main memory, any hash can be represented as`Hash Int String`

via pointers. Since the structure cannot be represented in memory, it cannot be represented with a hash. QEDThey are correct in saying that anything that can be represented in memory can be represented with a hash. However, this isn’t universal.

I don’t believe I quite agree with your contradiction…it somewhat hinges on the existence of one of these–let’s call them eldritch structures–unstorable data structures.

Under what circumstances would such a structure exist? What data would it model?

A simple example of a dataset that might take up all known memory would be, say, the set of all primes, right? But even then we can specify a predicate function which

canfit into finite memory and be used to test for membership.A trivial datastructure that requires infinite symbols is the Constant-Time Prime Label structure (that I totally didn’t make up just now). It maps every integer to a boolean true or false (true if prime, false otherwise). It is constant time because you can provide an integer and get an immediate answer. In order for this to be constant, each integer must be a tape symbol (if it weren’t, it’d be linear in bit length, not constant). But Turing machines aren’t defined with infinite tape symbols, so this structure can’t be represented on a turing machine (and thus not in main memory).

That’s a pretty useful in theory but also a trivial and useless example. Yes, we can define a predicate computing the mapping, but we lose the data structure’s most useful property (being constant time) when we do. So the data structure and predicate aren’t equivalent data structures in my mind (in the same sense that complexity theorists define algorithmic equivalence in terms of the complexity of a transformation from one algorithm to another; eg an algorithm is said to be

polynomiallyequivalent, not merely equivalent).Alternately, consider a (infinite or finite) stochastic sequence/array on the language L. Let A and B be disjoint subsets of L. When an element e is read from the sequence, either an

`a`

in A is seen or a`b`

in B is seen. Subsequent reads may not see the same thing. This structure could be used to efficiently perform random computations (which are important for many crypto applications), but is only defined on a probabalistic multi-tape turing machine (which would make it in theory equivalent to a non-deterministic turing machine, giving exponential blowup in the naïve transformation of the algorithm; if P = BPP then this one would be polynomially equivalent). This structure can be simulated reasonably well by stuff like /dev/rand (which includes main memory as a component, but requires other pieces to generate entropy for it to be actually random) that give what amounts to a buffer of random bytes.So there are (theoretically) useful structures that can’t reasonably be represented in just main memory. Practically, we could represent any finite structure as a hash, but that pretty much boils down to representing everything as a string and if javascript has taught me anything, it’s that that is a

terribleidea.That was a really great explanation–glad to see I wasn’t totally silly in my intuition that the prime classifier might be a good starting point.

if javascript has taught me anything, it’s that that is a terrible idea.Why would you say that? :3

For what it’s worth, the proposed symbol stuff is even sillier.

If symbols could be used as ordinary hash keys I’d be on board with them, because at that point they’re basically internalized strings for which we can do equality by reference equality (so…just faster strings).

My comment about JS was mostly poking fun at some idioms/conventions in the language that are ‘stringly typed’ and really difficult to scale to a large code base. For example:

`if(x.type === "foo" && y === "bar")`

Are you stretching the definition of data structure a bit too far? Basically you’ve said that any arbitrary set could be a unique data structure. This is the “prime number structure”, this is the “odd numbers structure”, etc.

This reminds me of Lua’s table data structure, which is effectively the language’s only composite data structure. (Errrm, OK, so maybe closures count too.)

There was a time, and this may still be the case, that arrays in Lua were implemented via this same table structure, using what essentially amounts to the strategy in the linked post (or at least the interface is like that). Since Closures are really just a tuple of captured data (or pointers thereto), and Lua bytecode is just an array of integers, Closures are representable exclusively via tables. It’d be interesting if Lua did this, but they don’t. :)

Sarcasm is a cheap rhetorical trick to avoid having to defend your position properly. I love strong typing but the case for it needs to be made on its merits. (And much as I hate it, Javascript has been quite successful).

Is the bit about the caterpillar a reference to something?

it made me think of http://learnyouahaskell.com/starting-out (search for “If we think of a list as a monster, here’s what’s what.”) but I don’t know what it’s actually referencing