Реализация пользовательского сравнения с CustomComparison и CustomEquality в F # кортеже - PullRequest
Новая
       47

Реализация пользовательского сравнения с CustomComparison и CustomEquality в F # кортеже

9 голосов
/ 22 июня 2010

Я здесь, чтобы задать конкретную тему - я действительно нашел немного информации об этом в Интернете. Я реализую 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.StackOverflowException в строке "|:? TreeOfPosition как y -> сравнить (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 Ответ

7 голосов
/ 22 июня 2010

Прежде всего, вы получаете исключение, потому что функция compare вызывает метод CompareTo значений, которые вы сравниваете (то есть x.ComaperTo(y)).Значения, которые вы сравниваете с помощью compare в пользовательской реализации CompareTo, являются значениями, которые вас просят сравнить (по времени выполнения), поэтому это вызывает переполнение стека.

Обычный способДля реализации CompareTo или Equals нужно сравнить только некоторые значения, которые вы храните в своем типе.Например, вы можете написать что-то вроде этого:

EDIT : вы можете написать вспомогательную функцию 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 занимает только некоторую часть данных, поэтому вы добиваетесь некоторого прогресса.

...