F# equals operator complexity

Question

I have a question about default "=" (equals) operator in F#. It allows to compare user-defined union types. The question is: what's the complexity of it? For example, let's consider following type:

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

and following trees:

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))

It is obvious that this code:

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

produces this output:

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

I expect that the "a = b" and "a = c" comparsions takes the linear time. But what about "a = a"? If it is constant what about more complex structures, like that one:

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

Will it go through whole d and e structure or will it stop at "a = a" and "c = c"?

Answer 1

F# uses structural equality whereas the default Equals implementation in .NET uses reference equality. This means, in the typical case, equality comparisons are O(N) where N is the number of fields in the object graphs being compared.

If you want to ensure a = a is optimized, you can override Equals to check for reference equality first, and fall back on structural equality otherwise. You'll need to annotate your type with [<CustomEquality>].

You can see the rather lengthy implementation of structural equality in the F# source code on github. To follow the call hierarchy start with GenericEqualityObj on line 1412.

Answer 2

EDIT: The original answer was wrong.

The usual implementation of Equals() in .Net works like this:

• Compare the two instances by reference. If they both refer to the same object, return true.
• Compare the runtime types of the two instances. If they are different, return false.
• Compare each of the fields of the type pairwise for equality. If any are not equal, return false, else return true.

For some reason, F# skips the first step, which means the time complexity is always linear.

Since the compiler knows that a and b are the same and some subtrees of c are same as some subtrees of a, and it also knows that they are immutable, it could theoretically make a and b the same object and reuse some of their parts in c. The runtime does something similar with strings, called string interning. But (based on decompiled code) it seems the compiler currently doesn't do this.