Haskell: `Map (a,b) c` 与 `Map a (Map b c)` 对比？

Question

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

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

Answer 1

Ord元组的实例使用字典顺序，所以 Map (a, b) c将按 a 排序首先无论如何，所以整体顺序将是相同的。关于实际考虑:

因为Data.Map是一个二叉搜索树在一个键处拆分类似于查找，因此获取给定 a 的子图非 curry 形式不会比 curry 形式贵得多。

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

柯里化(Currying)形式将有一些额外的开销来存储嵌套 map 。

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

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

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

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

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

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

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

foo x = go
  where z = expensiveComputation x
        go y = doStuff y z