违反mapKeysMonotonic前提条件

Question

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

一些替代方案是:

• 不要使用JSON,使用更好的东西(比如edn)
• 不返回a Map k v,返回a 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显然效率低下.我理解这可能是过早的优化.

但我仍然想知道这可能会破坏...或者如果它对我的有限用例确实安全.我唯一关心的是没有价值丢失.我不关心他们的订单.

现在,这是instance (ToJSON v) => ToJSON (M.Map String v).它将a转换Data.Map为aData.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,显然没有值丢失.地图现在可能不平衡......但后果是什么？我猜union,difference,intersection可能胡作非为......但什么遍历和褶皱？在所有情况下,这些仍然会保留所有元素吗？

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

Answer 1

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

不搜索的遍历很可能会起作用,但使用这样的映射会违反数据结构的逻辑,这会导致混淆和错误.

要定义ToJSON实例,您不需要构建中间映射; 你可以用来直接foldrWithKey构造一个Value.请注意,ObjectAeson 中的构造函数就是HashMap Text Value.折叠本身是O(n)并插入a HashMap(实际上)恒定时间.像这样的东西:

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