Trong OCaml, có thể xác định Bản đồ theo các điều khoản của Bộ không?

Question

Tôi đã thực hiện một đại diện của bộ (cây tìm kiếm cân bằng) trong OCaml. Nó thực sự là một functor Make ký

module Make : 
    functor (T : ORDERED_TYPE) -> 
sig 
    type elt = T.t 
    type t 
    val empty : t 
    val cons : elt -> t -> t 
    val delete : elt -> t -> t 
    val mem : elt -> t -> bool 
    val cardinal : t -> int 
end 

nơi

module type ORDERED_TYPE = sig type t val compare : t -> t -> int end 

Bây giờ tôi muốn thực hiện một cuốn từ điển như Map trong thư viện chuẩn. Nó phải có chữ ký như

module Make: functor (T : ORDERED_TYPE) -> sig 
    type key = T.t 
    type +'a t 
    ... 
end 

nơi t là loại từ điển.

Thực hiện các cây tìm kiếm cân bằng một lần nữa không thanh lịch, vì vậy tôi muốn xác định các từ điển về các tập hợp được triển khai như một hàm trên. Tôi có thể làm điều đó?

Answer 1

Dường như với tôi một bản đồ là một phần (một phần) chức năng, là một tập hợp các cặp đặt hàng. Nếu bạn xác định hàm so sánh của mình một cách chính xác, tôi nghĩ rằng nó có thể được thực hiện. Bạn có thể phải thêm một hàm vào giao diện Set để tính toán thực tế là hai giá trị có thể so sánh tương đương với các mục đích của tư cách thành viên nhưng không thực sự là các giá trị bằng nhau. Có vẻ như không thể xác định hàm tra cứu cho bản đồ bằng giao diện hiện tại.

Answer 2

Như Jeffrey đã lưu ý, giao diện Set của bạn không đủ biểu cảm để thực hiện thuận tiện Map trên đầu trang của nó. Sẽ đơn giản hơn khi triển khai Set từ Map, bằng cách xác định tập hợp làm bản đồ từ khóa thành giá trị đơn vị. Một khả năng khác, mà tôi muốn giới thiệu, là lần đầu tiên trưng ra một mô-đun cây tìm kiếm cân bằng mà không đóng gói, với mục đích duy nhất là cung cấp cấu trúc dữ liệu hiệu quả, hoàn toàn được tiết lộ bởi giao diện. Sau đó, bạn được tự do sử dụng lại nó cho bất kỳ cấu trúc dữ liệu nào bạn thích, bao gồm Map và Set, mà không phải chơi trò chơi để xác định cấu trúc dữ liệu theo cách khác. Điều này có thể không quá quan trọng trong trường hợp này (xác định Set từ Map là hợp lý cho hầu hết các mục đích), nhưng là một thiết kế tốt hơn trong trường hợp chung, theo ý kiến ​​của tôi.

Tóm lại: nếu bạn muốn sử dụng lại các triển khai, sau đó hiển thị "mô-đun triển khai" và xác định "mô-đun giao diện" của bạn ở đầu chúng.

Answer 3

Như những người khác đã chỉ ra, có ít nhất hai lý do khiến bạn không thể thực hiện các functor bản đồ yêu cầu trên đầu trang của các tập hợp:

1. Chữ ký thiết lập cung cấp không có cách nào để tìm một " bằng "phần tử trong một tập hợp nhất định.
2. Và ngay cả khi nó đã làm, bạn không thể lưu trữ các giá trị trong đó đa hình, như loại 'a map dường như yêu cầu.

Bạn có chắc chắn rằng tác vụ yêu cầu bạn triển khai bản đồ trên đầu trang của bộ? Có lẽ bạn chỉ cần triển khai chúng như bộ?

Answer 4

Vâng, có thực sự là một bằng hành ở đó - các so sánh chức năng từ loại ra lệnh.

Vì vậy, xác định mô-đun của riêng bạn cho một loại chìa khóa/giá trị mà chỉ đưa vào so sánh các phần chính:

module Keyvalue = struct 
    type t = ('a * 'b) 
    let compare x y = Pervasives.compare (fst x) (fst y) 
end 

và bạn đã làm xong. Vấn đề bây giờ là, Đặt của bạn không cho phép bạn nhận các giá trị của nó; không có nhận được cũng không phải chức năng - imho nào thực sự hạn chế cho cấu trúc dữ liệu như vậy. Nếu bạn được phép mò mẫm với Set thực hiện, bạn cần phải thêm một chức năng được:

module Set = sig 
    ... 
    get : t -> elt -> elt 
end 

rằng sẽ trả lại chỉ hỏi cho các phần tử. Nếu bạn lấy phần tử thứ hai của bộ trả về, bạn có giá trị của mình từ cặp khóa/giá trị gốc/giá trị.