json - 违反mapKeysMonotonic前提条件

Question

我想发送一些 JSON，其中包含从 (Database.Persist.Sql) 键到值的映射。显而易见的解决方案是使用 Map (Key x) v ，但这不是 ToJSON 的实例.

一些替代方案是:

• 不要使用 JSON，使用更好的东西(例如 edn )
• 不要返回 Map k v ，返回Map Text v (但在这里我会丢失一些类型信息)
• type JsonKey = Text ，和Map JsonKey v ，但这并没有真正更好
• 定义我自己的ToJSON实例。

后者似乎是需要较少更改的一种，而且更干净。

另外，请注意，我只需要 ToJSON实例，而不是 FromJSON ，所以我不需要整个往返。

所以，这就是我想写的:

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

假设Key有一个友好的Show实例(事实并非如此，但这只是一个细节)...我正要写:

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

但我立即意识到这很糟糕(键就像整数):

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

这违反了 mapKeysMonotonic前提条件。

现在，与此同时，我可以使用 mapKeys ...但我试图思考，违反这一点有什么风险？ mapKeys显然效率较低。我明白这可能是不成熟的优化。

但我仍然想了解这会以何种方式崩溃......或者对于我有限的用例来说它是否确实安全。我唯一关心的是值(value)观是否丢失。我不在乎他们的顺序。

现在，this is instance (ToJSON v) => ToJSON (M.Map String v) 。它转换 Data.Map到 Data.HashMap

这依赖于 mapHashKeyVals ...使用 Data.Map.foldrWithKey

我还考虑过使用HashMap (Key x) v ，以避免 N*log(N)计算或mapKeysMonotonic 。但我仍然定义了 ToJSON 实例，显然没有 mapKeys对于 HashMap (可以理解，因为这需要重新计算所有哈希值，但我不确定这是否实际上比 mapKeys 更昂贵)

现在，我尝试了这个简单的示例:

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

自show以来返回不同的 String对于每个不同的 Int ，显然没有任何值丢失。现在的 map 可能已经不平衡了……但是后果是什么？我猜union , difference , intersection可能会行为不当……但是遍历和折叠呢？在所有情况下这些仍然保留所有元素吗？

PS:我刚刚意识到另一个可能的解决方案可能是定义 instance ToJSON (ToJSON v => [(Key x, v)])并将其转换为Map在里面......但我想这将是一个重叠的实例

Answer 1

您可以使用Map.showTree来检查 map 的二叉树结构。 mapKeysMonotonic 函数保持相同的树顺序，只是替换节点，因此任何涉及搜索树的访问器都会给出错误的结果。

不进行搜索的遍历很可能会起作用，但是使用这样的映射违反了数据结构的逻辑，这会导致困惑和错误。

要定义您的 ToJSON 实例，您不需要构建中间映射；您可以使用foldrWithKey直接构造一个Value。请注意，Aeson 中的 Object 构造函数只是 HashMap Text Value。折叠本身的时间复杂度为 O(n)，插入到 HashMap 中的时间(实际上)是常数。像这样的事情:

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