Implementación de una comparación personalizada con CustomComparison y CustomEquality en F # tuple

Question

Estoy aquí para preguntar un tema específico: realmente encontré poca información sobre esto en la web. Estoy implementando una versión F # del algoritmo Minimax. El problema que estoy teniendo ahora es que quiero comparar Leaf of my tree (estructura de datos a continuación). Búsqueda de los erros el VS me dio a mí llegué a algo como esto:

El tipo de árbol que solía tener:

type TreeOfPosition = 
    | LeafP of Position 
    | BranchP of Position * TreeOfPosition list 

y la temptative para la realización del 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" 

En el fin, solo quiero obtener el máximo (y el mínimo) de una lista de LeafP por su valor estático (calcular en otra función).

El código anterior compila. Sin embargo la prueba con esto:

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 

tengo un System.StackOverflowException en el "|:? TreeOfPosition como Y -> comparar (x) (y)" línea en la anulación de la GetHashCode.

Tengo un hilo en el hubfs.net (http://cs.hubfs.net/forums/thread/15891.aspx) con Estoy hablando de mi Minimax. Aquí puede encontrar el código de lastest (http://www.inf.ufrgs.br/~pmdusso/works/Functional_Implementation_Minimax_FSharp.htm)

Gracias de antemano,

Pedro Dusso

Bueno, he entendido muy claramente la idea, pero no puedo hacer que funcione. Recordando que quiero obtener la hoja con el máximo valor estático de una lista de hojas ("List.max": P), creo que la implementación de CompareTo o Equals permitirá que List.max funcione en ellas, ¿correcto? compongo las cosas como esto:

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" 

Los problemas que tengo la organización de las funciones de esta manera es:

1) El patrón de discriminador 'LeafP' no está definido (con LeafP rojo subrayado)

2) (77,39): error FS0039: El valor o el constructor 'mycompare' no está definido, cuando intento un ALT ENTER este mensaje aparece en mi F # Interactive. La posición {77,39} corresponde al comienzo de la llamada mycompare (en GetHashCode).

¿Qué estoy haciendo mal? ¿Qué puedo hacer mejor?

Muchas gracias,

Pedro DUSSO

EDITAR 3 - Resuelto

Sí! ¡Administro tu respuesta para trabajar finalmente!

El código final está aquí:

[<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" 

Gracias por los comentarios!

Pedro Dusso

Answer 1

En primer lugar, que está recibiendo la excepción ya que la función compare llama al método de los valores que se está comparando (es decir x.ComaperTo(y)) CompareTo. Los valores que está comparando con compare en la implementación personalizada de CompareTo son los valores que se le pide que compare (por el tiempo de ejecución), por lo que esto provoca el desbordamiento de la pila.

La forma habitual de implementar CompareTo o Equals es comparar solo algunos valores que almacene en su tipo. Por ejemplo, podría escribir algo como esto:

EDITAR: Se puede escribir una función auxiliar mycopare hacer la comparación (o simplemente podría cambiar la implementación CompareTo). Sin embargo, si desea utilizar una función, debe moverla dentro de la declaración de tipo (para que sepa sobre el tipo; tenga en cuenta que en F #, importa el orden de la declaración)

Una forma de escribirlo es esto:

[<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" 

esto funcionaría, ya que cada llamada a compare toma sólo una parte de los datos, por lo que estamos haciendo algunos progresos.