在F#元组中使用CustomComparison和CustomEquality实现自定义比较

Question

我在这里问一个特定的话题 - 我在网上找到了很少有关于此的信息.我正在实现一个F#版本的Minimax算法.我现在遇到的问题是我要比较我的树叶(下面的数据结构).搜索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

我在GetHashCode的覆盖中的"|:？TreeOfPosition as y - > compare(x)(y)"行中得到了System.StackOverflowException.

我在hubfs.net(http://cs.hubfs.net/forums/thread/15891.aspx)中有一个帖子,我正在讨论我的Minimax.在这里你可以找到我最新的代码(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" 

感谢您的反馈!

佩德罗杜索

Answer 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只占用部分数据,所以你正在取得一些进展.