F#等于运营商的复杂性

Question

我对F#中的默认" = "(等于)运算符有疑问.它允许比较用户定义的联合类型.问题是:它的复杂性是什么？例如,让我们考虑以下类型:

type Tree<'a> =
  | Nil
  | Leaf of 'a
  | Node of Tree<'a> * Tree<'a>

以及树木:

let a : Tree<int> = Node (Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf 5))), Node (Leaf 6, Nil))
let b : Tree<int> = Node (Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf 5))), Node (Leaf 6, Nil))
let c : Tree<int> = Node (Node (Node (Leaf 1, Leaf 2), Nil), Node (Node (Leaf 3, Node (Leaf 4, Leaf 5)), Leaf 6))

很明显这段代码:

printfn "a = b: %b" (a = b)
printfn "a = c: %b" (a = c)
printfn "a = a: %b" (a = a)

产生这个输出:

a = b: true
a = c: false
a = a: true

我希望" a = b "和" a = c "比较采用线性时间.但是" a = a "呢？如果它是不变的更复杂的结构,如下那样:

let d : Tree<int> = Node (a, c)
let e : Tree<int> = Node (a, c)

它会通过整个d和e结构还是会停在" a = a "和" c = c "？

Answer 1

F# 使用结构相等，而 .NET 中的默认Equals实现使用引用相等。这意味着，在典型情况下，相等比较的时间复杂度为O(N)，其中N是要比较的对象图中的字段数。

如果您想确保a = a优化，您可以覆盖Equals以首先检查引用相等性，否则再依靠结构相等性。您需要用 注释您的类型[<CustomEquality>]。

您可以在github 上的 F# 源代码中看到相当冗长的结构相等实现。要遵循调用层次结构，请从GenericEqualityObj第 1412 行开始。