Ordered JSON objects?

Tobias Dammers

15 Dec 2014 15 Dec '14

7:32 p.m.

I'm building a "thing" that is supposed to use JSON 'documents' as its building blocks, providing various (pluggable) storage backends and presentation frontends. Non-techie/semi-techie (frontend dev, web dev, etc.) compatibility is needed, which is why I want to keep the data model "simple" and dynamically typed. Anyway, one thing I'm running up against is that I am going to need ordered key/value collections, which I believe is something JSON does not support out-of-the-box: "objects" ({"foo":15, "bar":23}) are conceptually unordered key/value collections (and Aeson treats them as such, using hash maps as the intermediate storage format), so I lose ordering; OTOH, flat lists ([15, 23]) do not have keys, and lists of "pairs" (two-element lists) produce uglier syntax ([["foo",15], ["bar",23]]), but they are the "correct" solution. Ideally, someone is going to step up and tell me that both I and Aeson have misunderstood JSON, and objects are really supposed to be ordered after all, in which case I'd need an alternative to Aeson (or someone needs to patch it?). Or I could bite the bullet and go with [["foo",15], ["bar",23]]. Or I could ditch JSON as the canonical format and go with something custom, or, shudder, XML. Thoughts? Hints? Ideas? - Tobias (tdammers on freenode)

Show replies by date

Steve Schafer

15 Dec 15 Dec

7:54 p.m.

On Mon, 15 Dec 2014 20:32:20 +0100, you wrote:

...

Anyway, one thing I'm running up against is that I am going to need ordered key/value collections, which I believe is something JSON does not support out-of-the-box: "objects" ({"foo":15, "bar":23}) are conceptually unordered key/value collections (and Aeson treats them as such, using hash maps as the intermediate storage format), so I lose ordering; OTOH, flat lists ([15, 23]) do not have keys, and lists of "pairs" (two-element lists) produce uglier syntax ([["foo",15], ["bar",23]]), but they are the "correct" solution.

I think this: [{"foo":15}, {"bar":23}] makes more sense than this: [["foo", 15], ["bar", 23]] as it maintains the key vs. value distinction. But you are correct that in JSON, arrays are ordered but objects are not. -Steve Schafer

Manuel Gómez

9:45 p.m.

On Mon, Dec 15, 2014 at 3:02 PM, Tobias Dammers wrote:

...

Anyway, one thing I'm running up against is that I am going to need ordered key/value collections, which I believe is something JSON does not support out-of-the-box: "objects" ({"foo":15, "bar":23}) are conceptually unordered key/value collections (and Aeson treats them as such, using hash maps as the intermediate storage format)

This only works for pretty-printing unordered key/value collections with a consistent, value-independent ordering, so it doesn’t sound like it solves your problem, but it may be worth mentioning anyway: http://hackage.haskell.org/package/aeson-pretty-0.7.2/docs/Data-Aeson-Encode...

Wojtek Narczyński

10:01 p.m.

On 15.12.2014 20:32, Tobias Dammers wrote:

...

Anyway, one thing I'm running up against is that I am going to need ordered key/value collections, which I believe is something JSON does not support out-of-the-box: "objects" ({"foo":15, "bar":23}) are conceptually unordered key/value collections (and Aeson treats them as such, using hash maps as the intermediate storage format), so I lose ordering;

JSON does not forbid ordering of maps by key, I believe. But you'd need to create an OrderedMap and patch aeson. It would be very useful, the mixing of key order is nuisance for human JSON consumers.

Tobias Dammers

16 Dec 16 Dec

8:39 a.m.

On Mon, Dec 15, 2014 at 11:01:12PM +0100, Wojtek Narczyński wrote:

...

On 15.12.2014 20:32, Tobias Dammers wrote:

...
Anyway, one thing I'm running up against is that I am going to need ordered key/value collections, which I believe is something JSON does not support out-of-the-box: "objects" ({"foo":15, "bar":23}) are conceptually unordered key/value collections (and Aeson treats them as such, using hash maps as the intermediate storage format), so I lose ordering;

JSON does not forbid ordering of maps by key, I believe. But you'd need to create an OrderedMap and patch aeson. It would be very useful, the mixing of key order is nuisance for human JSON consumers.

No, that's not what I meant. By "ordered", I meant that the in-memory representation of the document should maintain file order. Aeson uses a HashMap to store key/value objects, which is an unordered container; what you suggest would be something like Map (storing elements by key order), but what I'm talking about is more like [(Key, Value)], i.e., keeping file order intact.

Michael Snoyman

8:43 a.m.

On Tue Dec 16 2014 at 10:39:32 AM Tobias Dammers wrote:

...

On Mon, Dec 15, 2014 at 11:01:12PM +0100, Wojtek Narczyński wrote:

...
On 15.12.2014 20:32, Tobias Dammers wrote:

...
Anyway, one thing I'm running up against is that I am going to need ordered key/value collections, which I believe is something JSON does not support out-of-the-box: "objects" ({"foo":15, "bar":23}) are conceptually unordered key/value collections (and Aeson treats them as such, using hash maps as the intermediate storage format), so I lose ordering;

JSON does not forbid ordering of maps by key, I believe. But you'd need to create an OrderedMap and patch aeson. It would be very useful, the mixing of key order is nuisance for human JSON consumers.

No, that's not what I meant. By "ordered", I meant that the in-memory representation of the document should maintain file order. Aeson uses a HashMap to store key/value objects, which is an unordered container; what you suggest would be something like Map (storing elements by key order), but what I'm talking about is more like [(Key, Value)], i.e., keeping file order intact.

I think your best bet is to bite the bullet and just deal with an array, forgetting the object entirely (at least at the top level). Any time I've needed to implement some kind of ordered data in JSON, I've used an array. Michael

Tobias Dammers

9:10 a.m.

On Tue, Dec 16, 2014 at 08:43:08AM +0000, Michael Snoyman wrote:

...

On Tue Dec 16 2014 at 10:39:32 AM Tobias Dammers wrote:

...
On Mon, Dec 15, 2014 at 11:01:12PM +0100, Wojtek Narczyński wrote:

...
On 15.12.2014 20:32, Tobias Dammers wrote:

...
Anyway, one thing I'm running up against is that I am going to need ordered key/value collections, which I believe is something JSON does not support out-of-the-box: "objects" ({"foo":15, "bar":23}) are conceptually unordered key/value collections (and Aeson treats them as such, using hash maps as the intermediate storage format), so I lose ordering;

JSON does not forbid ordering of maps by key, I believe. But you'd need to create an OrderedMap and patch aeson. It would be very useful, the mixing of key order is nuisance for human JSON consumers.

No, that's not what I meant. By "ordered", I meant that the in-memory representation of the document should maintain file order. Aeson uses a HashMap to store key/value objects, which is an unordered container; what you suggest would be something like Map (storing elements by key order), but what I'm talking about is more like [(Key, Value)], i.e., keeping file order intact.

I think your best bet is to bite the bullet and just deal with an array, forgetting the object entirely (at least at the top level). Any time I've needed to implement some kind of ordered data in JSON, I've used an array.

Yes, that's what I was thinking myself. I absolutely don't want to use "looks like JSON but isn't", I really want to stick with standard JSON, for so many reasons. My tentative design so far is to use an array of "anything"; each element can be a scalar (which generates an unnamed field), an object with the magic properties "_name" and "_value", which generates a named field, or something else, which generates an unnamed field containing that something else. So I'd have this: [ "foobar" , { "baz": "quux", "boink": "blip" } , { "_name": "foobar", "_value": "oink" } , { "_name": "quuux", "_value": { "apples": "oranges" } } ] ...which would map to something like (in pseudo-Show notation): [ ("_field_1", String "foobar") , ("_field_2", Object (fromList [ ("baz", "quux"), ("boink", "blip") ])) , ("foobar", String "boink") , ("quuux", Object (fromList [ ("apples": "oranges") ])) ] This would meet the requirement of providing ordered properties, and it would allow for arbitrary JSON (i.e., the mapping would be total over all valid JSON arrays); the downside is that the ToJSON and FromJSON instances for my Record type would be a bit more complex than what I have now, but I guess that would be OK. Another downside would be that if an element specifies both "_value" *and* non-magic fields, I would have to decide whether I want to treat "_value" as non-magic, or throw away the non-magical fields.

Wojtek Narczyński

10:08 p.m.

On 16.12.2014 09:39, Tobias Dammers wrote:

...

On Mon, Dec 15, 2014 at 11:01:12PM +0100, Wojtek Narczyński wrote:

...
On 15.12.2014 20:32, Tobias Dammers wrote:

...
Anyway, one thing I'm running up against is that I am going to need ordered key/value collections, which I believe is something JSON does not support out-of-the-box: "objects" ({"foo":15, "bar":23}) are conceptually unordered key/value collections (and Aeson treats them as such, using hash maps as the intermediate storage format), so I lose ordering; JSON does not forbid ordering of maps by key, I believe. But you'd need to create an OrderedMap and patch aeson. It would be very useful, the mixing of key order is nuisance for human JSON consumers. No, that's not what I meant. By "ordered", I meant that the in-memory representation of the document should maintain file order. Aeson uses a HashMap to store key/value objects, which is an unordered container; what you suggest would be something like Map (storing elements by key order), but what I'm talking about is more like [(Key, Value)], i.e., keeping file order intact.

I meant a container maintaining order of additions. Indeed, it's not an OrderedMap, rather InOrderOfArrivalMap.

...

I absolutely don't want to use "looks like JSON but isn't", I really want to stick with standard JSON, for so many reasons.

As long as the keys are unique, it is JSON, order of keys does not matter. Caveat emptor.

Tobias Dammers

17 Dec 17 Dec

8:23 a.m.

On Tue, Dec 16, 2014 at 11:08:34PM +0100, Wojtek Narczyński wrote:

...

As long as the keys are unique, it is JSON, order of keys does not matter.

The thing is, yes, it is syntactically valid JSON, which suggests that the order of keys do not matter, but for my application, I need a key/value collection where order *does* matter, which means that while my syntactic representation would be exactly JSON, my program would be semantically incorrect.

...

Caveat emptor. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Tobias Dammers - tobias@twokings.nl - 070-3457628 - www.twokings.nl Maandag t/m donderdag van 9.00 tot 17.30 Voor dringende vragen, mail naar support@twokings.nl

Richard A. O'Keefe

16 Dec 16 Dec

11:12 p.m.

On 16/12/2014, at 9:39 pm, Tobias Dammers wrote:

...

No, that's not what I meant. By "ordered", I meant that the in-memory representation of the document should maintain file order.

You did consult RFC 4627, right? Page 1: "An object is an UNORDERED collection of zero or more name/value pairs”. Or www.json.org? Just above the railroad diagram for objects, “An object is an UNORDERED SET of name/value pairs.” Or RFC 7159? Section 1: “An object is an UNORDERED collection of zero or more name/value pairs”. The new thing in RFC 7159 is "JSON parsing libraries have been observed to differ as to whether or not they make the ordering of object members visible to calling software. Implementations whose behavior does not depend on member ordering will be interoperable in the sense that they will not be affected by these differences.” That is, the file order is WITHOUT SIGNIFICANCE. If you happen to use a library that preserves that order in memory, NOTHING SHOULD DEPEND ON THAT if you want your software to be interoperable. Recall that JSON is explicitly derived from Javascript and that a JSON “object” is explicitly (www.json.org) "an object, record, struct, dictionary, hash table, keyed list, or associative array” so that the *intended* in-memory representation for a JSON object is an *unordered* data structure. So if you depend on the order of the name/value pairs in a JSON object, you doing something surpassing strange and risky.

Wojtek Narczyński

17 Dec 17 Dec

8:26 a.m.

On 17.12.2014 00:12, Richard A. O'Keefe wrote:

...

On 16/12/2014, at 9:39 pm, Tobias Dammers wrote:

...
No, that's not what I meant. By "ordered", I meant that the in-memory representation of the document should maintain file order. You did consult RFC 4627, right?

Page 1: "An object is an UNORDERED collection of zero or more name/value pairs”.

Okay, I was plain wrong.

Wojtek Narczyński

8:59 a.m.

On 17.12.2014 00:12, Richard A. O'Keefe wrote:

...

So if you depend on the order of the name/value pairs in a JSON object, you doing something surpassing strange and risky. All I wanted to do was to keep the order of key-value pairs in accordance with the order of fields in their corresponding haskell records, during serialization. I guess that would be okay.

Tobias Dammers

9:06 a.m.

On Wed, Dec 17, 2014 at 09:59:10AM +0100, Wojtek Narczyński wrote:

...

On 17.12.2014 00:12, Richard A. O'Keefe wrote:

...
So if you depend on the order of the name/value pairs in a JSON object, you doing something surpassing strange and risky. All I wanted to do was to keep the order of key-value pairs in accordance with the order of fields in their corresponding haskell records, during serialization. I guess that would be okay.

It would still be problematic if you rely on this order to come back unchanged after putting your JSON through any processing. For example, if you have a JSON document like this: { "foo":23, "bar":"$quux" } ...and you pipe it through a Ruby script that walks through it and substitutes some value (say 42) wherever you have "$quux", you must be prepared to receive it back as: { "bar":42, "foo":23 } It is perfectly acceptable for your own processor to keep the ordering intact, but you cannot expect anything else to do the same for you. It also means that you cannot use Aeson to parse or represent your JSON, because it uses HashMaps to store objects, and those are by definition unordered containers.

...

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Tobias Dammers - tobias@twokings.nl - 070-3457628 - www.twokings.nl Maandag t/m donderdag van 9.00 tot 17.30 Voor dringende vragen, mail naar support@twokings.nl

Richard A. O'Keefe

18 Dec 18 Dec

2:12 a.m.

On 17/12/2014, at 9:59 pm, Wojtek Narczyński wrote:

...

On 17.12.2014 00:12, Richard A. O'Keefe wrote:

...
So if you depend on the order of the name/value pairs in a JSON object, you doing something surpassing strange and risky. All I wanted to do was to keep the order of key-value pairs in accordance with the order of fields in their corresponding haskell records, during serialization. I guess that would be okay.

At some point, you convert an internal value to a “JSON” form, x. You hand that over to some other JSON-handling software, and eventually get the “same” value back, x’. The other JSON-handling software could be something as simple as [StdIn skipSeparators] whileFalse: [ StdOut printJson: StdIn nextJson; cr]. Now x’ may *legitimately* be different from x, both in the amount and location of white space, the presence or absence of leading and trailing zeros in numbers, the use or non-use of \u escapes in strings, *and the order of key/value pairs in objects*. So if your program depends on the order of key/value pairs, you cannot trust JSON-handling software you have not writtern yourself to preserve your extra semantics. That’s what I mean by “risky”. For reasons having to to with compressibility, I’d probably use {“fields” : [“f1”,..,”fn”], “values” : [v1, .., vn ] } if I wanted safe interoperability with 3rd-party JSON support.

...

Tobias Dammers

17 Dec 17 Dec

9:01 a.m.

On Wed, Dec 17, 2014 at 12:12:00PM +1300, Richard A. O'Keefe wrote:

...

On 16/12/2014, at 9:39 pm, Tobias Dammers wrote:

...
No, that's not what I meant. By "ordered", I meant that the in-memory representation of the document should maintain file order.

You did consult RFC 4627, right?

So if you depend on the order of the name/value pairs in a JSON object, you doing something surpassing strange and risky.

No need to go all RTFM on me; "JSON objects are unordered" is exactly what I was basing my reasoning on. I am not planning on depending on the order of something that is unordered by definition. However, my requirements are: 1. File format must be valid JSON (or occasionally YAML, or at least the JSON-isomorphic subset) 2. I need to represent ordered key/value collections 3. Conversion from JSON to the internal data type must be total (i.e., any valid JSON document must be accepted and converted to the most reasonable internal representation). Since JSON objects are (semantically) unordered, and the only way to get an ordered collection in JSON is through an array, my choices are: a) Use something that looks like JSON but defines objects as ordered key/value collections; this is something I *really* don't want, because it can break so many assumptions, and I would have to write my own JSON (and YAML) parsers for no good reason. b) Use an array of one-element objects. c) Use an array of keys and a key/value object side-by side. d) Use an array of objects, with a 'magic' property providing a tag name, and another magic property providing the payload value. e) Exactly like d), but gracefully accept other array elements, treating them as unnamed values. What I have implemented now is option e), with "_name" and "_value" for the magic properties; if neither is given, the element itself becomes an unnamed value, and can only be looked up by position; if a name is given but no value, it becomes a named null entry; if both are given, a proper name/value pair is generated. I'm still working out the details of if and what to throw away when an entry has both a "_value" and other properties, but other than that, I think this is as good as it gets. -- Tobias Dammers - tobias@twokings.nl - 070-3457628 - www.twokings.nl Maandag t/m donderdag van 9.00 tot 17.30 Voor dringende vragen, mail naar support@twokings.nl

Kyle Marek-Spartz

3:19 p.m.

That's pedantic and beside the point. The question is not what JSON supports, but rather how to best represent data which consists of ordered key-value pairs using JSON. I'll second the solution of [{"key1": "value"}, {"key2": "value"}]. Richard A. O'Keefe writes:

...

On 16/12/2014, at 9:39 pm, Tobias Dammers wrote:

...
No, that's not what I meant. By "ordered", I meant that the in-memory representation of the document should maintain file order.

You did consult RFC 4627, right?

Page 1: "An object is an UNORDERED collection of zero or more name/value pairs”.

Or www.json.org?

Just above the railroad diagram for objects, “An object is an UNORDERED SET of name/value pairs.”

Or RFC 7159? Section 1: “An object is an UNORDERED collection of zero or more name/value pairs”. The new thing in RFC 7159 is "JSON parsing libraries have been observed to differ as to whether or not they make the ordering of object members visible to calling software. Implementations whose behavior does not depend on member ordering will be interoperable in the sense that they will not be affected by these differences.”

That is, the file order is WITHOUT SIGNIFICANCE. If you happen to use a library that preserves that order in memory, NOTHING SHOULD DEPEND ON THAT if you want your software to be interoperable.

Recall that JSON is explicitly derived from Javascript and that a JSON “object” is explicitly (www.json.org) "an object, record, struct, dictionary, hash table, keyed list, or associative array” so that the *intended* in-memory representation for a JSON object is an *unordered* data structure.

So if you depend on the order of the name/value pairs in a JSON object, you doing something surpassing strange and risky.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Kyle Marek-Spartz

3855

Age (days ago)

3858

Last active (days ago)

List overview

Download

15 comments

7 participants

participants (7)

Kyle Marek-Spartz
Manuel Gómez
Michael Snoyman
Richard A. O'Keefe
Steve Schafer
Tobias Dammers
Wojtek Narczyński