violating mapKeysMonotonic precondition

Question

I want to send some JSON that will contain a mapping from (Database.Persist.Sql) Keys to values. The obvious solution would be to use a Map (Key x) v, but this is not an instance of ToJSON.

Some alternatives are:

• don't use JSON, use something better (like edn)
• don't return a Map k v, return a Map Text v (but here I'd lose some type information)
• type JsonKey = Text, and Map JsonKey v, but this is not really any better
• define my own ToJSON instance.

The latter seems to be the one that will require less changes, and the cleaner one.

Also, be aware that I only need the ToJSON instance, not the FromJSON, so I don't need the whole roundtripping.

So, this is what I want to write:

import Database.Persist.Sql (Key)
instance ToJSON (ToJSON v => (Map (Key a) v))

Assuming that Key has a friendly Show instance (it doesn't, but this is just a detail)... I was about to write:

instance ToJSON (ToJSON v => (Map (Key a) v)) where
  toJSON m = toJSON $ mapKeysMonotonic show m

but I immeditately realized that this is bad (Keys are just like integers):

> 9 < 10
True
> "9" < "10"
False

This violates the mapKeysMonotonic precondition.

Now, in the meanwhile, I can just use mapKeys... but I tried to think, what's the risk in violating this? mapKeys is obviously less efficient. And I understand how this might be premature optimization.

But I'd still like to understand in which way this could break down... or if it's indeed safe for my limited use case. The only thing I care about is if no values are lost. I don't care about their order.

Now, this is instance (ToJSON v) => ToJSON (M.Map String v). It converts a Data.Map to a Data.HashMap

Which relies on mapHashKeyVals... which uses Data.Map.foldrWithKey

I also thought of using an HashMap (Key x) v, to avoid either a N*log(N) computation or mapKeysMonotonic. But I'd have the define the ToJSON instance nonetheless, and apparently there's no mapKeys for HashMap (understandably, since this would require to recompute all the hashes, but I'm not sure if this would actually be more expensive than a mapKeys)

Now, I tried this simple example:

> mapKeysMonotonic show $ fromList [(10,"a"), (9, "b"), (99, "c"), (100, "d")]
fromList [("9","b"),("10","a"),("99","c"),("100","d")]

and since show returns a distinct String for each distinct Int, obviously no values are lost. The Map now is probably unbalanced... but what are the consequences? I guess that union, difference, intersection might misbehave... but what about traversal and folds? Would these still retain all the elements in all cases?

PS: I just realized that another possible solution maybe could be to define instance ToJSON (ToJSON v => [(Key x, v)]) and convert it to Map on the inside... but I guess this would be an overlapping instance

Answer 1

You can use Map.showTree to inspect the binary tree structure of the maps. The mapKeysMonotonic function keeps the same tree order and just replaces the nodes, and so any accessor that involves searching the tree will give wrong results.

Traversals that don't search will quite possibly work, but using maps like this violates the logic of the data structure which is a recipe for confusion and bugs.

To define your ToJSON instance, you don't need to build an intermediate map; you can use foldrWithKey to construct a Value directly. Note that the Object constructor in Aeson is just HashMap Text Value. The fold itself is O(n) and inserting into a HashMap is (practically) constant time. Something like this:

instance ToJSON v => ToJSON (Map (Key a) v) where
  toJSON = Object . Map.foldrWithKey f mempty
    where f = HashMap.insert . Text.pack . show