News for hackers. Stuff that matters.
Re:Show HN: a Lisp that uses JSON instead of S-expressions (... by lisper on Tuesday November 29, 2011 @02:21PM (#3291740)
You are conflating the abstract data type with its implementation. A hash-map is one implementation of an associative array. A tree is another implementation of an associative array. A tree happens to depend on an ordering of the keys in order to do efficient lookup and a hash-map doesn't, but this is an implementation detail. It's not part of the definition of an associative array. And this is a good thing because not all data types have well defined orderings but you still might want to use them as keys, with symbols being the most notable example.
Re:Show HN: a Lisp that uses JSON instead of S-expressions (... by wanorris on Tuesday November 29, 2011 @02:52PM (#3291873)
I think the mistake the parent post has made is conflating the kind of ordering you're referring to -- ordering in a tree implementation to allow for O(log n) resolution -- and ordering to preserve the position of each key-value pair as it was in the source structure. These are only the same thing if the source structure already happens to be sorted by some kind of ordering, something that obviously cannot be extended to the general case of preserving positionality.

AFAIK, the only two ways to preserve positionality as part of an associative array are (1) to store as a postional list of key-value pairs and use linear search to find matching keys, or (2) to use an additional data structure as an index, either by storing as a positional list and having a additional map from key value into the positions, or by storing as a map and having an additional list of keys stored in positional ordering.

Re:Show HN: a Lisp that uses JSON instead of S-expressions (... by ori_b on Tuesday November 29, 2011 @05:22PM (#3292528)
Or by having the map nodes have a "next" pointer.
Re:Show HN: a Lisp that uses JSON instead of S-expressions (... by wanorris on Tuesday November 29, 2011 @05:34PM (#3292600)
Duh, I should have thought of that. Thank you.