dictionary - 为什么 F#'s idiomatic dictionary collection (Map) needs the type K to implement comparable while C#' s Dictionary 没有？

Question

我知道这个问题与我之前问过的这个问题非常相似:Why F#'s default set collection is sorted while C#'s isn't?

但是，我想确认这里给出的原因是否与这种情况相同？我想知道是否有 F# 中不可变 Map 的实现，由某人编写，它不那么严格并且不需要 K 具有可比性？我很乐意使用它，因为我不太关心性能。

Answer 1

Why F#'s idiomatic dictionary collection Map<K,V> needs the type K to implement comparable while C#'s Dictionary<K,V> doesn't?

F# Map<Key, Value>要求键具有可比性，因为 map 是 implemented as a tree structure (你必须根据比较结果决定去哪个子树)。 C# Dictionary<Key, Value>被实现为一个链表桶。你通过键的哈希码得到一个桶，然后迭代列表直到你(不)找到相同的键。在这两种数据结构中，都会比较键。唯一的区别是字典相等比较就足够了。

所以，问题是为什么 F# Map具有显式 比较约束，但 C# Dictionary是否有隐式平等要求？

让我们从 C# 开始。如果字典有 IEquatable 会怎样？关键约束？那么，对于用作字典键的每个自定义数据类型，您将必须手动实现此接口(interface)。但是如果你想要平等的不同实现呢？例如。在某些词典中，您希望键字符串不区分大小写。当然可以传IEqualityComparer用于键比较的实现(不仅与字典，而且在需要比较的任何地方)。但是，如果将使用外部比较器，为什么还要强制 key 具有可比性呢？请注意，如果您不向字典传递任何内容，则始终使用默认比较器。默认比较器检查键是否实现 IComparable并使用该实现。

为什么 F# 对关键数据类型有明确的可比较约束？因为此约束不会强制您手动实现 IComparable对于用作映射键的每个自定义数据类型。 C# 和 F# 类型系统之间的一大区别是默认情况下 F# 类型可比较和等同。 F# 编译器生成 IComparable , IComparable<T> , 和 IStructuralComparable实现，除非你用 NoComparison 明确标记类型属性。因此，此约束不会强制您在使用 F# 数据类型时编写任何额外代码。

使用比较/相等约束的另一个好处 - F# 对实现比较或相等的类型有许多预定义的泛型操作(=、<、<=、>=、=、max、min)。这使得具有通用可比较/等同类型的代码更具可读性。