Preserve record key order in JSON from Map or JSON types

[bch29]

I am trying to use dhall to generate JSON config for an application in which key order actually matters. It is a GUI program for visualizing tabular data, and the columns are configured like

{
    "schema": {
        "foo": {"Type" : "System.Int32"},
        "bar": {"Type": "System.Double", "DisplayFormat": "{0:F2}" }
    }
}

where the order of the keys in the "schema" object determines the order of the columns in the GUI.

My dhall representation of this JSON object is

{ schema =
  [ { mapKey = "foo", mapValue = { Type = "System.Int32", DisplayFormat = None Text } }
  , { mapKey = "bar", mapValue = { Type = "System.Double", DisplayFormat = Some "{0:F2}" } }
  ]
}

however, dhall-to-json reorders the fields in the map because "bar" sorts before "foo". Is it possible to have dhall-to-json preserve key order in this case? I understand from #1187 that it would be very difficult to preserve key order from dhall records, but I am hoping that since the dhall normal form of a map is an ordered list, this case would be easier to handle.

[sjakobi]

Thanks for the report!

I understand from #1187 that it would be very difficult to preserve key order from dhall records, but I am hoping that since the dhall normal form of a map is an ordered list, this case would be easier to handle.

Normalization of Dhall expressions, which sorts the record fields, is one issue, but as you correctly point out, it's not the problem in this case.

After normalization, we translate the normalized expressions to the JSON Value format of the JSON library we use, aeson. aeson uses a hash map for storing objects, and I think it is at this stage that the order of keys is lost in your example.

[bch29]

Thank you for responding quickly!

It does not seem like the reordering is caused by hashing because it is always sorted in the output of dhall-to-json.

[bch29]

However, if aeson stored objects as a ordered Map rather than a HashMap, that would explain this behaviour.

[sjakobi]

We use aeson-pretty for the Value -> ByteString conversion. Apparently that uses lexicographic sorting.

Apparently we could customize the field order in that step, but I don't see how to use that to solve this issue.

[sjakobi]

Oh, so what you could do is encode your schema with the Prelude.JSON type, and then use Prelude.JSON.render to convert to Text:

[german1608]

@sjakobi Do we lose value ordering after processing dhall expression?

I think that we could enumerate every key from the dhall expression and use that enumeration to sort. In @bch29 example:

• "foo" comes first in dhall expression, we number it 1
• "bar" comes last, we number it 2

That goes on a Map Text Int and we could aim sort using that. That could be an option for the CLI

[sjakobi]

@german1608 We translate these Prelude.Maps to RecordLits in convertToHomogenousMaps:

dhall-haskell/dhall-json/src/Dhall/JSON.hs

Lines 877 to 926 in b9cbc63

	Core.ListLit a b ->
	case transform of
	Just c -> loop c
	Nothing -> Core.ListLit a' b'
	where
	elements = Foldable.toList b
	toKeyValue :: Expr s Void -> Maybe (Text, Expr s Void)
	toKeyValue (Core.RecordLit m) = do
	guard (Foldable.length m == 2)
	key <- Dhall.Map.lookup mapKey m
	value <- Dhall.Map.lookup mapValue m
	keyText <- case key of
	Core.TextLit (Core.Chunks [] keyText) ->
	return keyText
	Core.Field (Core.Union _) keyText ->
	return keyText
	_ ->
	empty
	return (keyText, value)
	toKeyValue _ = do
	empty
	transform =
	case elements of
	[] ->
	case a of
	Just (Core.App Core.List (Core.Record m)) -> do
	guard (Foldable.length m == 2)
	guard (Dhall.Map.member mapKey m)
	guard (Dhall.Map.member mapValue m)
	return (Core.RecordLit mempty)
	_ -> do
	empty
	_ -> do
	keyValues <- traverse toKeyValue elements
	let recordLiteral =
	Dhall.Map.fromList keyValues
	return (Core.RecordLit recordLiteral)
	a' = fmap loop a
	b' = fmap loop b

The translation from RecordLit to Value then happens here:

dhall-haskell/dhall-json/src/Dhall/JSON.hs

Lines 435 to 502 in b9cbc63

	Core.RecordLit a ->
	case toOrderedList a of
	[ ( "contents"
	, contents
	)
	, ( "field"
	, Core.TextLit
	(Core.Chunks [] field)
	)
	, ( "nesting"
	, Core.App
	(Core.Field
	(Core.Union
	[ ("Inline", mInlineType)
	, ("Nested", Just Core.Text)
	]
	)
	"Nested"
	)
	(Core.TextLit
	(Core.Chunks [] nestedField)
	)
	)
	] | all (== Core.Record []) mInlineType
	, Just (alternativeName, mExpr) <- getContents contents -> do
	contents' <- case mExpr of
	Just expr -> loop expr
	Nothing -> return Aeson.Null
	let taggedValue =
	Data.Map.fromList
	[ ( field
	, toJSON alternativeName
	)
	, ( nestedField
	, contents'
	)
	]
	return (Aeson.toJSON taggedValue)
	[ ( "contents"
	, contents
	)
	, ( "field"
	, Core.TextLit
	(Core.Chunks [] field)
	)
	, ( "nesting"
	, nesting
	)
	] | isInlineNesting nesting
	, Just (alternativeName, mExpr) <- getContents contents -> do
	kvs0 <- case mExpr of
	Just (Core.RecordLit kvs) -> return kvs
	Just alternativeContents ->
	Left (InvalidInlineContents e alternativeContents)
	Nothing -> return mempty
	let name = Core.TextLit (Core.Chunks [] alternativeName)
	let kvs1 = Dhall.Map.insert field name kvs0
	loop (Core.RecordLit kvs1)
	_ -> do
	a' <- traverse loop a
	return (Aeson.toJSON (Dhall.Map.toMap a'))

I think that we could enumerate every key from the dhall expression and use that enumeration to sort.

Yeah, that could work, but I think it would be tricky to make it reliable. I think we should rather use a JSON or YAML encoding that preserves key order. So encode Expr -> OrderPreservingYAML, and then translate OrderPreservingYAML -> Aeson.Value if needed. HsYAML should be a good fit, but its GPL licence is a problem: haskell-hvr/HsYAML#45

[sjakobi]

Maybe we should just create our own YAML type. Better leave parsing and encoding to other libraries though. It's a huge mess.

EDIT: I made a question about available libraries on r/haskell.

[Gabriella439]

@sjakobi: The Data.Aeson.Value type is so simple that it probably wouldn't be that much code to define our own inline variation on that type, except replacing HashMap with Dhall.Map.Map. Then we could provide a conversion from our type to Data.Aeson.Value that discards the order by converting to the HashMap

[sjakobi]

Indeed. We could consider allowing some non-Text key types too, as requested in #1379.

[bch29]

Oh, so what you could do is encode your schema with the Prelude.JSON type, and then use Prelude.JSON.render to convert to Text:

That is quite awkward for my use case because I have a few more layers of records around what I gave in the example, and those work just fine being left as dhall records. I would have to convert them all to the JSON type, which is a lot of boilerplate.