Implementing custom comparison with CustomComparison and CustomEquality in F# tuple

Question

I'm here to ask a specific topic - I really found few info about this on the web. I'm implementing a F# version of Minimax algorithm. The problem I'm having now is that I want to compare Leaf of my tree (data structure below). Searching the erros the VS gave to me I arrived to something like this:

The tree type I used to have:

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

and the temptative for implementing the 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"

In the end, I just wanna get the max (and the min) of a list of LeafP by its static value (calculate in other function).

The code above compiles. However testing with this:

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

I got a System.StackOverflowException in the "| :? TreeOfPosition as y -> compare (x) (y)" line in the override of the GetHashCode.

I have a thread in the hubfs.net (http://cs.hubfs.net/forums/thread/15891.aspx) with I'm discussing my Minimax. Here you can find my lastest code (http://www.inf.ufrgs.br/~pmdusso/works/Functional_Implementation_Minimax_FSharp.htm)

Thanks in advance,

Pedro Dusso

Well, I understood very clearly the idea but I can’t make it work. Remembering that I want to get the leaf with the max static value from a list of leafs (“List.max” :P), I think implementing the CompareTo or Equals will let the List.max works on them, correct? I compose the things like this:

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" 

The problems I’m having arranging the functions this way is:

1) The pattern discriminator 'LeafP' is not defined (with LeafP red-underlined)

2) (77,39): error FS0039: The value or constructor 'mycompare' is not defined, when I try a ALT ENTER this message appear in my F# Interactive. The position {77,39} corresponds to the beginning of mycompare call (in GetHashCode).

What I’m doing wrong? What can I do better?

Thanks very much,

Pedro Dusso

EDIT 3 - Solved

Yes! I manage your answer to work finaly!

The final code is here:

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

Thanks for the feedback!

Pedro Dusso

Answer 1

First of all, you're getting the exception because the compare function calls the CompareTo method of the values you're comparing (that is x.ComaperTo(y)). The values you're comparing using compare in the custom implementation of CompareTo are the values that the you are asked to compare (by the runtime), so this causes the stack overflow.

The usual way to implement CompareTo or Equals is to compare only some values that you store in your type. For example, you could write something like this:

EDIT: You can write a helper function mycopare to do the comparison (or you could simply change the CompareTo implementation). However, if you want to use a function, you need to move it inside the type declaration (so that it knows about the type - note that in F#, the order of declaration matters!)

One way of writing it is this:

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

This would work, because every call to compare takes only some part of the data, so you're making some progress.