Haskell：`Map（a，b）c`与`Map a（Map b c）`有何区别？

Question

Haskell：`Map（a，b）c`与`Map a（Map b c）`有何区别？

haskelldictionarycurrying

21

将地图视为有限函数的表示形式，两个或多个变量的地图可以以柯里化（Curried）或未柯里化（Uncurried）形式给出;即类型Map (a,b) c和Map a (Map b c)是同构的，或者非常接近。

在选择两种表示形式之间有哪些实际考虑因素 - 效率等等？

- PLL

2

我认为 Map (a, b) c 可能更加节省内存（也可能更快）。如果有一种方法（我不确定，因为我很少使用 maps）可以在前缀键范围上进行折叠，那么你仍然可以有效地使用这种表示来执行柯里化应用。 - user1020786

3个回答

4

元组在元素上都是懒惰的，因此元组版本引入了一点额外的惰性。这是好事还是坏事强烈取决于您的使用情况。（特别是，比较可能会强制执行元组元素，但仅当有大量重复的a值时。）

除此之外，我认为它将取决于您有多少个副本。如果每当b时a几乎总是不同，那么您将拥有很多小树，因此元组版本可能更好。另一方面，如果相反的情况，则非元组版本可能会节省一些时间（一旦找到适当的子树并查找b，就不会不断地重新比较a）。

我想起了trie，以及它们只存储公共前缀的方式。非元组版本似乎有点像这种方式。如果有许多常见前缀，则Trie可以比BST更有效，否则效率可能不如BST。

但最重要的是：进行基准测试！;-)

- MathematicalOrchid

1

+1 我和你想法一致。如果有很多搜索已经因为缺少 * 并且唯一的柯里化键（a，b）的数量远大于唯一的 a 的数量，则未柯里化的形式也可能更快。 - Ingo

它实际上不会是惰性的，因为一旦您将其放入树中并进行键比较，它就会被强制执行，并且通常情况下，“Map”组合器在键方面过于严格（有些不必要）。 - Edward Kmett

你将不得不支付额外的检查费用，因为 GHC 不够聪明，无法知道元组的两个元素已经在第一次比较中被强制执行，只有外部的 (,) 会在插入空 Map 时被强制执行。 - Edward Kmett

3

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

例如，你是否想要为给定类型 a 的值存储一个空映射？如果是这样，那么非柯里化版本可能更实用！

这里有一个简单的例子：假设我们想要存储人员的字符串值属性 - 比如该人员在 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”已知于系统中，但未填写任何信息的事实。由于Map在键上是严格的，人物/属性对“PLL”，undefined将导致运行时崩溃。

你可以将curriedMap的类型更改为Map（Person，Property）（Maybe String），并在其中存储Nothing，在这种情况下可能是最佳解决方案。但是，如果有未知/变化的属性数量（例如，根据人员类型），那么也会遇到困难。

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

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

在柯里化版本中写起来很困难（甚至是不可能的），但在非柯里化版本中很容易。

- yatima2975

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- C. A. McCann · Accepted Answer

Ord 的元组实例使用词典序，所以无论如何 Map (a, b) c 都会首先按照 a 进行排序，因此总体顺序将保持不变。关于实际考虑：

由于 Data.Map 是一个二叉搜索树，所以在键分割方面，非柯里化形式的子映射查找与柯里化形式相比不会显著更加昂贵。
柯里化形式可能会产生更不平衡的树，原因很明显，因为有多棵树而不是只有一棵。
柯里化形式将具有额外的开销来存储嵌套映射。
表示“部分应用程序”的柯里化形式的嵌套映射可以共享，如果某些 a 值产生相同的结果。
类似地，柯里化形式的“部分应用”会给你现有的内部映射，而非柯里化形式必须构造一个新映射。

因此，在一般情况下，非柯里化形式是~~明显更好的~~，但如果您希望经常进行“部分应用程序”并从共享 Map b c 值中受益，则柯里化形式可能更好。

请注意，必须小心确保您实际上从潜在的共享中获得了好处；您需要明确定义任何共享的内部映射，并在构造完整映射时重复使用单个值。

编辑：Tikhon Jelvis 在评论中指出，我没有考虑到元组构造函数的内存开销。当然，柯里化形式也有一些开销，但这种开销与有多少个不同的 a 值成比例。另一方面，非柯里化形式中的元组构造开销与总键数成比例。

因此，如果平均而言，对于任何给定的 a 值，有三个或更多不同的键使用它，则使用柯里化版本可能会节省内存。当然，不平衡树的问题仍然存在。我越想越觉得柯里化形式是无可争议的更好，除非您的键非常稀疏且分布不均匀。

请注意，因为 GHC 对定义的元数很敏感，因此在定义函数时需要注意同样的问题，如果您希望子表达式被共享。这就是为什么有时会看到像这样定义函数的方式之一：

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