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"?
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.