Thực hiện so sánh tùy chỉnh với CustomComparison và CustomEquality trong F # tuple

Question

Tôi đang ở đây để hỏi một chủ đề cụ thể - Tôi thực sự tìm thấy vài thông tin về điều này trên web. Tôi đang triển khai phiên bản F # của thuật toán Minimax. Vấn đề tôi đang gặp bây giờ là tôi muốn so sánh Leaf of my tree (cấu trúc dữ liệu bên dưới). Tìm kiếm trên erros VS đã cung cấp cho tôi, tôi đến một cái gì đó như thế này:

Các loại cây tôi đã từng có:

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

và temptative để thực hiện các 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" 

Trong cuối cùng, tôi chỉ muốn có được tối đa (và min) của một danh sách của LeafP bởi giá trị tĩnh của nó (tính toán trong chức năng khác).

Mã trên biên dịch. Tuy nhiên thử nghiệm với điều này:

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 

tôi nhận được một System.StackOverflowException trong "|: TreeOfPosition như y -> so sánh (x) (y)" dòng trong ghi đè GetHashCode.

Tôi có một chủ đề trong hubfs.net (http://cs.hubfs.net/forums/thread/15891.aspx) khi tôi đang thảo luận về Minimax của mình. Ở đây bạn có thể tìm mã mới nhất của tôi (http://www.inf.ufrgs.br/~pmdusso/works/Functional_Implementation_Minimax_FSharp.htm)

Cảm ơn trước,

Pedro Dusso

Vâng, tôi hiểu rất rõ ý tưởng nhưng tôi không thể làm cho nó làm việc. Nhớ rằng tôi muốn lấy lá với giá trị tĩnh tối đa từ danh sách các lá (“List.max”: P), tôi nghĩ việc triển khai CompareTo hoặc Equals sẽ cho phép List.max hoạt động trên chúng, đúng không? tôi soạn những điều như thế này:

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" 

Những vấn đề tôi đang gặp sắp xếp các chức năng theo cách này là:

1) Các mô hình phân biệt 'LeafP' không được định nghĩa (với LeafP đỏ gạch dưới)

2) (77,39): lỗi FS0039: Giá trị hoặc hàm tạo 'mycompare' không được xác định, khi tôi thử ALT ENTER thông báo này xuất hiện trong F # Interactive của tôi. Vị trí {77,39} tương ứng với phần đầu của cuộc gọi mycompare (trong GetHashCode).

Tôi đang làm gì sai? Tôi có thể làm gì tốt hơn?

Cảm ơn rất nhiều,

Pedro Dusso

EDIT 3 - Giải Quyết

Có! Tôi quản lý câu trả lời của bạn để làm việc chung kết!

Mã cuối cùng là ở đây:

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

Cảm ơn đã phản hồi!

Pedro Dusso

Answer 1

Trước hết, bạn đang nhận được ngoại lệ vì compare chức năng gọi phương thức CompareTo trong những giá trị bạn đang so sánh (có nghĩa là x.ComaperTo(y)). Các giá trị bạn so sánh bằng cách sử dụng compare trong triển khai tùy chỉnh CompareTo là các giá trị mà bạn được yêu cầu so sánh (theo thời gian chạy), do đó điều này gây ra tràn ngăn xếp.

Cách thông thường để triển khai CompareTo hoặc Equals là chỉ so sánh một số giá trị mà bạn lưu trữ trong loại của mình. Ví dụ, bạn có thể viết một cái gì đó như thế này:

EDIT: Bạn có thể viết một hàm helper mycopare để làm so sánh (hoặc bạn chỉ đơn giản là có thể thay đổi việc thực hiện CompareTo). Tuy nhiên, nếu bạn muốn sử dụng một hàm, bạn cần di chuyển nó bên trong khai báo kiểu (để nó biết về loại - lưu ý rằng trong F #, thứ tự khai báo quan trọng!)

Một cách để viết nó là này:

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

Điều này sẽ hiệu quả, bởi vì mọi cuộc gọi đến compare chỉ mất một phần dữ liệu, vì vậy bạn đang thực hiện một số tiến bộ.