Haskell:`Map(a,b)c`对`map a(Map bc)`？

Question

将地图视为有限函数的表示,可以以咖喱或非曲线的形式给出两个或更多变量的映射; 也就是说,类型Map (a,b) c和Map a (Map b c)同构,或接近它的东西.

有哪些实际考虑 - 效率等 - 用于在两种表示之间进行选择？

Answer 1

Ord元组的实例使用字典顺序,因此无论如何Map (a, b) c都将a首先进行排序,因此整体顺序将是相同的.关于实际考虑:

• 因为Data.Map二进制搜索树在键处的分割与查找相当,所以a在未组合的表单中获取给定的子图将不会比在curried形式中更加昂贵.

• 咖喱形式可能会产生一个不太平衡的树,因为有多棵树而不是一棵树的明显原因.

• curried表单将有一些额外的开销来存储嵌套映射.

• 如果某些a值产生相同的结果,则可以共享表示"部分应用程序"的curried形式的嵌套映射.

• 类似地,咖喱表单的"部分应用"为您提供现有的内部地图,而未表达的表单必须构建新的地图.

因此,未经证实的形式通常显然更好,但如果您希望经常"部分应用"并且将从共享Map b c价值中受益,那么咖喱形式可能会更好.

请注意,需要一些注意,以确保您实际从这种潜在的共享中受益 ; 您需要显式定义任何共享内部映射,并在构造完整映射时重用单个值.

编辑: Tikhon Jelvis在评论中指出,元组构造函数的内存开销 - 我认为没有考虑到 - 根本不是微不足道的.咖喱形式肯定存在一些开销,但是开销与a有多少不同的值成比例.另一方面,未处理形式的元组构造函数开销与密钥总数成比例.

因此,如果平均而言,对于任何给定值,a有三个或更多使用它的不同键,您可能会使用咖喱版本来节省内存.当然,对不平衡树木的担忧仍然适用.我想的越多,我就越怀疑咖喱的形式是明确的更好,除非你的钥匙非常稀疏且分布不均匀.

请注意,因为定义的元素对GHC很重要,所以如果您希望共享子表达式,则在定义函数时需要同样小心; 这是您有时看到以这样的样式定义的函数的一个原因:

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