Haskell：`Map (a，b) c`与`Map a (Map B c)`？

Question

将映射看作是有限函数的表示，一个包含两个或更多变量的映射既可以是curried形式，也可以是uncurried形式；也就是说，类型Map (a,b) c和Map a (Map b c)是同构的，或者是类似的。

在两种表示之间进行选择时，有哪些实际考虑因素-效率等？

Answer 1

元组在这两个元素中都是惰性的，所以元组版本引入了一些额外的惰性。这是好是坏很大程度上取决于你的使用情况。(特别是，比较可能会强制元组元素，但仅当存在大量重复的a值时。)

除此之外，我认为这将取决于你有多少副本。如果无论b如何变化，a几乎总是不同的，那么您将拥有许多小树，因此元组版本可能更好。另一方面，如果情况正好相反，那么非元组版本可能会为您节省一点时间(在找到合适的子树并且正在寻找a时，不需要不断地重新比较b)。

我想起了尝试，以及它们如何存储公共前缀一次。非元组版本看起来有点像这样。如果有很多常见的前缀，trie可能比BST更有效，如果没有，则效率较低。

但底线是：基准测试！！ ;-)

Answer 2

除了效率方面，这个问题还有一个实用的方面:你想用这个结构做什么？

例如，您是否希望能够为类型为a的给定值存储一个空映射？如果是这样的话，那么不加奶酪的版本可能会更实用！

下面是一个简单的例子:假设我们想要存储person的String-valued属性--比如这个人的stackoverflow配置文件页面上某些字段的值。

type Person = String
type Property = String

uncurriedMap :: Map Person (Map Property String)
uncurriedMap = fromList [
                   ("yatima2975", fromList [("location","Utrecht"),("age","37")]),
                   ("PLL", fromList []) ]
curriedMap :: Map (Person,Property) String
curriedMap = fromList [
                 (("yatima2975","location"), "Utrecht"),
                 (("yatima2975","age"), "37") ]

在curried版本中，没有很好的方法来记录系统知道用户"PLL"的事实，但是没有填写任何信息。由于Map在键上是严格的，所以人/属性对("PLL",undefined)将导致运行时崩溃。

您可以将curriedMap的类型更改为Map (Person,Property) (Maybe String)并将Nothing存储在其中，在这种情况下，这可能是最好的解决方案；但是，如果存在未知/不同数量的属性(例如，取决于类型的人)，也会遇到困难。

data QueryResult = PersonUnknown | PropertyUnknownForPerson | Value String
query :: Person -> Property -> Map (Person, Property) String -> QueryResult

这在curried版本中很难编写(如果不是不可能的话)，但在非curried版本中很容易。