21

将映射视为有限函数的表示，两个或多个变量的映射可以以柯里化或非柯里化形式给出；也就是说，类型Map (a,b) c和Map a (Map b c)是同构的，或者接近它的东西。

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

4

3 回答 3

17

元组的Ord实例使用字典顺序，所以无论如何Map (a, b) c都要先排序a，所以整体顺序是一样的。关于实际考虑：

  • 因为Data.Map在键处拆分二叉搜索树与查找相当，所以以非柯里化形式获取给定的子图a不会比柯里化形式贵得多。

  • 柯里化形式可能会产生整体上不太平衡的树，原因很明显，有多个树而不是只有一个。

  • 柯里化形式将有一些额外的开销来存储嵌套地图。

  • a如果某些值产生相同的结果，则表示“部分应用程序”的柯里化形式的嵌套映射可以共享。

  • 类似地，柯里化形式的“部分应用”为您提供了现有的内部映射，而非柯里化形式必须构造一个新映射。

所以一般来说非柯里化形式显然更好，但如果你希望经常做“部分应用”并且会从Map b c价值共享中受益，柯里化形式可能会更好。

请注意，需要小心谨慎，以确保您真正从潜在的共享中受益；您需要显式定义任何共享的内部映射并在构建完整映射时重用单个值。

编辑： Tikhon Jelvis 在评论中指出，元组构造函数的内存开销——我认为没有考虑到这一点——根本不能忽略不计。柯里化形式肯定有一些开销，但开销与有多少不同的a值成正比。另一方面，非柯里化形式的元组构造函数开销与键的总数成正比。

因此，如果平均而言，对于任何给定的值，a有三个或更多不同的键使用它，您可能会使用 curried 版本节省内存。当然，对不平衡树的担忧仍然存在。我想得越多，我就越怀疑咖喱形式无疑更好，除非您的密钥非常稀疏且分布不均匀。

请注意，由于定义的数量对 GHC 很重要，如果您希望共享子表达式，则在定义函数时需要同样小心；这是您有时会看到以如下样式定义的函数的原因之一：

foo x = go
  where z = expensiveComputation x
        go y = doStuff y z
于 2013-05-17T16:02:39.403 回答
4

元组在这两个元素中都是惰性的，因此元组版本引入了一些额外的惰性。这是好是坏很大程度上取决于您的使用情况。（特别是，比较可能会强制使用元组元素，但前提是存在大量重复a值。）

除此之外，我认为这将取决于你有多少重复。如果a几乎总是不同b，那么您将拥有很多小树，因此元组版本可能会更好。另一方面，如果相反，非元组版本可能会为您节省一点时间（a一旦您找到合适的子树并且您正在寻找，就不会不断地重新比较b）。

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

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

于 2013-05-17T18:34:52.307 回答
3

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

例如，您是否希望能够为 type 的给定值存储一个空映射a？如果是这样，那么 uncurried 版本可能更实用！

这是一个简单的示例：假设我们要存储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") ]

使用柯里化版本，没有很好的方法来记录用户"PLL"对系统已知但没有填写任何信息的事实。一个人/财产对("PLL",undefined)将导致运行时崩溃，因为Map键是严格的。

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

所以，我想这也取决于你是否需要这样的查询函数：

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

这在 curried 版本中很难写（如果不是不可能的话），但在 uncurried 版本中很容易。

于 2013-05-21T09:24:38.140 回答