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) 

Будет ли она пройти через весь д и е структуры или она остановится «а =» и "с = c "?

Answer 1

F # использует структурное равенство, тогда как реализация по умолчанию Equals в .NET использует ссылочное равенство. Это означает, что в типичном случае сравнения равен O (N) где N - количество полей в сравниваемых объектных графах.

Если вы хотите, чтобы оптимизировался a = a, вы можете переопределить Equals, чтобы сначала проверить ссылочное равенство и в противном случае вернуться к структурному равенству. Вам нужно будет аннотировать свой тип [<CustomEquality>].

Вы можете увидеть довольно длительную реализацию структурного равенства в the F# source code on github. Чтобы выполнить иерархию вызовов, начинайте с GenericEqualityObj on line 1412.

Answer 2

EDIT: Оригинальный ответ был неправильным.

Обычная реализация Equals() в .NET работает следующим образом:

• Сравните два экземпляра по ссылке. Если оба они относятся к одному и тому же объекту, верните true.
• Сравните типы времени выполнения двух экземпляров. Если они разные, верните false.
• Сравните каждое из полей типа попарно для равенства. Если они не равны, верните false, иначе верните true.

По какой-то причине F # пропускает первый шаг, что означает, что временная сложность всегда линейна.

Поскольку компилятор знает, что a и b одинаковы и некоторые поддеревья c такие же, как некоторые поддеревьев a, и он также знает, что они неизменны, он теоретически может сделать a и b тот же объект и использовать некоторые их частей в c. Среда выполнения делает что-то похожее на строки, называемые string interning. Но (на основе декомпилированного кода) кажется, что компилятор в настоящее время этого не делает.