Реализация пользовательского сравнения с CustomComparison и CustomEquality в F# кортеже
Я здесь, чтобы задать конкретную тему - я действительно нашел мало информации об этом в Интернете. Я реализую F# версию алгоритма Minimax. Сейчас у меня проблема в том, что я хочу сравнить Leaf моего дерева (структура данных ниже). В поисках ошибок, которые дала мне VS, я пришел к чему-то вроде этого:
Тип дерева, который у меня был:
type TreeOfPosition =
| LeafP of Position
| BranchP of Position * TreeOfPosition list
и соблазн для реализации IComparable
type staticValue = int
[<CustomEquality;CustomComparison>]
type TreeOfPosition =
| LeafP of Position * staticValue
| BranchP of Position * TreeOfPosition list
override x.Equals(yobj) =
match yobj with
| :? TreeOfPosition as y -> (x = y)
| _ -> false
override x.GetHashCode() = hash (x)
interface System.IComparable with
member x.CompareTo yobj =
match yobj with
| :? TreeOfPosition as y -> compare (x) (y)
| _ -> invalidArg "yobj" "cannot compare value of different types"
В конце, я просто хочу получить максимум (и минимум) списка LeafP по его статическому значению (вычислить в другой функции).
Код выше компилируется. Однако тестирование с этим:
let p = new Position()
p.Add(1,BLACK)
let a = LeafP(p,1)
let b = LeafP(p,2)
let biger = compare a b
printf "%d" biger
Я получил System.StackruException в строке "|:? TreeOfPosition как y -> compare (x) (y)" в переопределении GetHashCode.
У меня есть тема в hubfs.net ( http://cs.hubfs.net/forums/thread/15891.aspx), где я обсуждаю свой минимакс. Здесь вы можете найти мой последний код ( http://www.inf.ufrgs.br/~pmdusso/works/Functional_Implementation_Minimax_FSharp.htm)
Заранее спасибо,
Педро Дуссо
Ну, я очень ясно понял идею, но не могу заставить ее работать. Помня, что я хочу получить лист с максимальным статическим значением из списка листьев ("List.max":P), я думаю, что реализация CompareTo или же Equals пусть List.max работает на них, правильно? Я сочиняю такие вещи:
let mycompare x y =
match x, y with
// Compare values stored as part of your type
| LeafP(_, n1), LeafP(_, n2) -> compare n1 n2
//| BranchP(_, l1), BranchP(_, l2) -> compare l1 l2 //I do not need Branch lists comparison
| _ -> 0 // or 1 depending on which is list...
[< CustomEquality;CustomComparison >]
type TreeOfPosition =
| LeafP of Position * int
| BranchP of Position * TreeOfPosition list
override x.Equals(yobj) =
match yobj with
| :? TreeOfPosition as y -> (x = y)
| _ -> false
override x.GetHashCode() = hash (x)
interface System.IComparable with
member x.CompareTo yobj =
match yobj with
| :? TreeOfPosition as y -> mycompare x y
| _ -> invalidArg "yobj" "cannot compare value of different types"
Проблемы, которые у меня возникают при организации функций таким образом:
1) Дискриминатор шаблона 'LeafP' не определен (с красной линией LeafP)
2) (77,39): ошибка FS0039: значение или конструктор 'mycompare' не определены, когда я пытаюсь выполнить команду ALT ENTER, это сообщение появляется в моем F# Interactive. Позиция {77,39} соответствует началу вызова mycompare (в GetHashCode).
Что я делаю не так? Что я могу сделать лучше?
Спасибо большое,
Педро Дуссо
РЕДАКТИРОВАТЬ 3 - Решено
Да! Я управляю твоим ответом на работу окончательно!
Окончательный код здесь:
[<CustomEquality;CustomComparison>]
type TreeOfPosition =
| LeafP of Position * int
| BranchP of Position * TreeOfPosition list
//Func: compare
//Retu: -1: first parameter is less than the second
// 0: first parameter is equal to the second
// 1: first parameter is greater than the second
static member mycompare (x, y) =
match x, y with
// Compare values stored as part of your type
| LeafP(_, n1), LeafP(_, n2) -> compare n1 n2
| _ -> 0 // or 1 depending on which is list...
override x.Equals(yobj) =
match yobj with
| :? TreeOfPosition as y -> (x = y)
| _ -> false
override x.GetHashCode() = hash (x)
interface System.IComparable with
member x.CompareTo yobj =
match yobj with
| :? TreeOfPosition as y -> TreeOfPosition.mycompare(x, y)
| _ -> invalidArg "yobj" "cannot compare value of different types"
Спасибо за ответ!
Педро Дуссо
1 ответ
Прежде всего, вы получаете исключение, потому что compare функция вызывает CompareTo метод значений, которые вы сравниваете (то есть x.ComaperTo(y)). Значения, которые вы сравниваете, используя compare в пользовательской реализации CompareTo это значения, которые вас просят сравнить (по времени выполнения), поэтому это вызывает переполнение стека.
Обычный способ реализации CompareTo или же Equals это сравнить только некоторые значения, которые вы храните в вашем типе. Например, вы можете написать что-то вроде этого:
РЕДАКТИРОВАТЬ: Вы можете написать вспомогательную функцию mycopare сделать сравнение (или вы могли бы просто изменить CompareTo реализация). Однако, если вы хотите использовать функцию, вам нужно переместить ее в объявление типа (чтобы она знала о типе - обратите внимание, что в F# порядок объявления имеет значение!)
Один из способов написать это так:
[<CustomEquality; CustomComparison >]
type TreeOfPosition =
| LeafP of Position * int
| BranchP of Position * TreeOfPosition list
override x.Equals(yobj) =
match yobj with
| :? TreeOfPosition as y ->
// TODO: Check whether both y and x are leafs/branches
// and compare their content (not them directly)
| _ -> false
override x.GetHashCode() = // TODO: hash values stored in leaf/branch
interface System.IComparable with
member x.CompareTo yobj =
// Declare helper function inside the 'CompareTo' member
let mycompare x y =
match x, y with
// Compare values stored as part of your type
| LeafP(_, n1), LeafP(_, n2) -> compare n1 n2
| BranchP(_, l1), BranchP(_, l2) -> compare l1 l2
| _ -> -1 // or 1 depending on which is list...
// Actual implementation of the member
match yobj with
| :? TreeOfPosition as y -> mycompare x y
| _ -> invalidArg "yobj" "cannot compare value of different types"
Это будет работать, потому что каждый звонок compare занимает только некоторую часть данных, так что вы делаете некоторые успехи.